当前位置：首页 > news >正文

位运算题目：或运算的最小翻转次数

news 来源：原创 2025/8/7 21:35:36

文章目录

题目
- 标题和出处
- 难度
- 题目描述
- - 要求
  - 示例
  - 数据范围
解法
- 思路和算法
- 代码
- 复杂度分析

题目

标题和出处

标题：或运算的最小翻转次数

出处：1318. 或运算的最小翻转次数

难度

4 级

题目描述

要求

给定三个正整数 $\texttt{a}$ 、 $\texttt{b}$ 和 $\texttt{c}$ 。可以对 $\texttt{a}$ 和 $\texttt{b}$ 的二进制表示进行位翻转操作，返回能够使按位或运算 $\texttt{a OR b = c}$ 成立的最小翻转次数。

位翻转操作是指将一个数的二进制表示的任何一个位上的 $\texttt{1}$ 变成 $\texttt{0}$ 或者 $\texttt{0}$ 变成 $\texttt{1}$ 。

示例

示例 1：

示例 1

输入： $\texttt{a = 2, b = 6, c = 5}$
输出： $\texttt{3}$
解释：翻转后 $\texttt{a = 1, b = 4, c = 5}$ 使得 $\texttt{a OR b = c}$ 。

示例 2：

输入： $\texttt{a = 4, b = 2, c = 7}$
输出： $\texttt{1}$

示例 3：

输入： $\texttt{a = 1, b = 2, c = 3}$
输出： $\texttt{0}$

数据范围

$\texttt{1} \le \texttt{a} \le \texttt{10}^\texttt{9}$
$\texttt{1} \le \texttt{b} \le \texttt{10}^\texttt{9}$
$\texttt{1} \le \texttt{c} \le \texttt{10}^\texttt{9}$

解法

思路和算法

正整数 $a$ 、 $b$ 和 $c$ 满足 $a ∣ b = c$ ，等价于每个二进制位都满足 $a$ 和 $b$ 的按位或运算结果等于 $c$ 。只有当一个二进制位不满足按位或运算规则时，才需要将 $a$ 和 $b$ 在该位的值翻转。

可以同时遍历 $a$ 、 $b$ 和 $c$ 的二进制表示，计算最小翻转次数。由于 $a$ 、 $b$ 和 $c$ 都是正整数，因此二进制表示的最高位即符号位是 $0$ ，可以通过右移运算的方式遍历二进制表示的每一位。

每次分别取 $a$ 、 $b$ 和 $c$ 的二进制表示的最低位，记为 $\textit{aBit}$ 、 $\textit{bBit}$ 和 $\textit{cBit}$ ，如果 $\textit{aBit} ~|~ \textit{bBit} \ne \textit{cBit}$ ，则当前位不满足按位或运算规则，当前位的翻转次数计算如下。

如果 $\textit{cBit} = 1$ ，则 $\textit{aBit}$ 和 $\textit{bBit}$ 都是 $0$ ，只要将其中一个值翻转即可使当前位满足按位或运算规则，因此当前位的翻转次数是 $1$ 。
如果 $\textit{cBit} = 0$ ，则 $\textit{aBit}$ 和 $\textit{bBit}$ 当中至少有一个是 $1$ ，需要将每个 $1$ 翻转才能使当前位满足按位或运算规则，因此当前位的翻转次数是 $\textit{aBit} + \textit{bBit}$ 。

更新翻转次数之后，将 $a$ 、 $b$ 和 $c$ 分别右移一位，继续计算其余位的翻转次数。当 $a$ 、 $b$ 和 $c$ 都变成 $0$ 时，其余位一定满足按位或运算规则，因此结束遍历，此时即可得到使 $a ∣ b = c$ 成立的最小翻转次数。

上述翻转次数是使 $a ∣ b = c$ 成立的最小翻转次数，如果翻转次数更少，则一定无法使 $a ∣ b = c$ 成立。

代码

class Solution {public int minFlips(int a, int b, int c) {int flips = 0;while (a > 0 || b > 0 || c > 0) {int aBit = a & 1, bBit = b & 1, cBit = c & 1;if ((aBit | bBit) != cBit) {if (cBit == 1) {flips++;} else {flips += aBit + bBit;}}a >>= 1;b >>= 1;c >>= 1;}return flips;}
}

复杂度分析

时间复杂度： $O(\log \max(a, b, c))$ ，其中 $a$ 、 $b$ 和 $c$ 是给定的正整数。时间复杂度主要取决于需要遍历的二进制表示的位数，需要遍历的二进制表示的位数取决于 $a$ 、 $b$ 和 $c$ 中的最大值。
空间复杂度： $O (1)$ 。

位运算题目：或运算的最小翻转次数

文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题：或运算的最小翻转次数出处：1318. 或运算的最小翻转次数难度 4 级题目描述要求给定三个正整数 a \texttt{a} a、 b \texttt{b} b…...

编程日记 2025/8/7 21:35:36

Java 实现排序算法 TopK 问题

1. 低级排序 （1）冒泡排序（Bubble Sort） 思路： 每次从左到右冒泡，把最大的数推到最后。 public class BubbleSort {public static void bubbleSort(int[] arr) {int n arr.length;for (int i 0; i <…...

编程日记 2025/8/7 11:40:17

【JavaEE】网络编程socket

1.❤️❤️前言~🥳🎉🎉🎉 Hello, Hello~ 亲爱的朋友们👋👋，这里是E绵绵呀✍️✍️。如果你喜欢这篇文章，请别吝啬你的点赞❤️❤️和收藏📖📖。如果你对我的…...

编程日记 2025/8/6 8:09:59

第J3周：DenseNet121算法实现01（Pytorch版）

🍨 本文为🔗365天深度学习训练营中的学习记录博客🍖 原作者：K同学啊目标具体实现 （一）环境语言环境：Python 3.10 编译器: PyCharm 框架: Pytorch （二）具体步骤…...

编程日记 2025/8/7 21:31:12

在Ubuntu20.04上交叉编译能在Windows上运行的Qt5应用

参考链接： https://blog.csdn.net/Interview_TC/article/details/146050419 https://bugreports.qt.io/browse/QTBUG-82592 重要设置 sudo update-alternatives --config x86_64-w64-mingw32-g 选择后缀带posix的，（/usr/bin/x86_64-w64-min…...

编程日记 2025/8/7 1:46:41

C语言中，memmove和memcpy的区别？

文章目录 1. 内存重叠处理memcpy：memmove： 2. 性能差异总结在C语言中，memmove和memcpy均用于内存块的复制，但关键区别在于对内存重叠的处理： 1. 内存重叠处理 memcpy： 假设源（src&#xff0…...

编程日记 2025/8/4 17:26:54

小程序API —— 54 路由与通信 - 编程式导航

在小程序中实现页面的跳转，有两种方式： 声明式导航：navigator 组件编程式导航：使用小程序提供的 API 编程式导航 API 提供了五个常用的 API 方法： wx.navigateTo()：保留当前页面，跳转到应用内…...

编程日记 2025/8/7 21:28:02

2025 使用docker部署centos7容器并且需要centos7容器能通过ssh登录SSH 登录的CentOS7容器

以下是使用 Docker 部署可 SSH 登录的 CentOS7 容器的步骤： 1.创建 Dockerfile（保存为 Dockerfile.centos7）： vim Dockerfile.centos7 #复制如下内容 FROM centos:7# 备份原有的 yum 源配置文件 RUN mv /etc/yum.repos.d/CentO…...

编程日记 2025/8/7 21:26:46

docker安装向量数据库Milvus及可视化工具 Attu

前置条件 1.安装了docker 2.服务器网络正常，可以连接到容器下载地址 3.服务器磁盘空间正常，docker磁盘占用过大，请参考docker容量占用过大解决办法一、下载yml文件可在文章资源下载或者自行下载：下载yml 下载这个单机版本的…...

编程日记 2025/8/6 22:19:29

从模拟到现实：Sensodrive高精度力反馈技术赋能物流运输的高效与安全

在现代物流行业中，司机短缺、二氧化碳排放增加和利润空间紧张等问题日益凸显。为应对这些挑战，Sensodrive的SensoWheel和SensoPedals产品在自驾卡车中的应用，提供了更为高效的运输解决方案，有效缓解了这些问题。 Fernride公司利用…...

编程日记 2025/8/7 20:01:39

无需qt-creator,使用Trae从0到1生成qt的开发、构建、调试环境

一、安装 Qt 开发环境确保已经安装了 Qt，没有安装的可以自己在网上搜索怎么安装，安装时可选择不安装qt creator，但是qt开发库和编译器要安装，这里我选择的编译器是MinGW， 安装好以后，记录下qt开发库和Min…...

编程日记 2025/8/7 13:59:12

整理和总结微信小程序的高频知识点

前言近期萌生了一些想法，感觉可以做一个小程序作为产出。但小程序做得比较少，因此边做边复习。整理和总结了一些高频知识点和大家一起分享。一、模板和组件 1.1模板（Template） 优势简单灵活：模板定义和使用都较…...

编程日记 2025/8/5 20:39:53

VMware主机换到高配电脑，高版本系统的问题

原来主机是i3 ,windows7系统，vmware 14.0,虚机系统是ubuntu 14.04。目标新机是i7 14700KF,windows11系统。原以为安装虚拟机，将磁盘文件，虚拟机配置文件拷贝过去可以直接用。新目标主机先安装了vmware 15，运行原理虚机&#xff0…...

编程日记 2025/8/5 9:19:28

“锈化”Python：用Rust重塑Python生态的六大工具深度解析

前言：为何“锈化”Python？ Python以其简洁的语法和强大的生态系统成为数据科学、Web开发和自动化领域的首选语言。然而，随着项目规模和性能需求的增长，Python的一些传统工具在速度、内存效率和安全性上面临瓶颈。近年来&#xff…...

编程日记 2025/8/4 11:24:31

6.3考研408数据结构中BFS与DFS的易错点及难点解析

一、广度优先算法（BFS）易错点队列操作失误未正确处理节点入队顺序（如未按层序逐层扩展），导致结果混乱。在出队后未立即标记节点为已访问，可能引发重复访问（尤其在存在环的图中）。示…...

编程日记 2025/8/1 5:25:33

在Ubuntu上安装MEAN Stack的4个步骤

在Ubuntu上安装MEAN Stack的4个步骤为：1.安装MEAN；2.安装MongoDB；3.安装NodeJS，Git和NPM；4.安装剩余的依赖项。什么是MEAN Stack？ 平均堆栈一直在很大程度上升高为基于稳健的基于JavaScript的开发堆栈。…...

编程日记 2025/8/7 5:19:12

如何通过Odoo 18创建与配置服务器操作

如何通过Odoo 18创建与配置服务器操作服务器操作是Odoo实现业务流程自动化的核心工具，允许你在服务器端执行自动化任务，通常由按钮点击或自动化工作流等事件触发。这些操作使用 Python 编写，能够执行复杂的业务逻辑，从而增强 Od…...

编程日记 2025/8/3 19:18:17

【QGIS_Python】在QGIS的Python控制台生成SHP格式点数据并显示标注

参考文章： 「GIS教程」使用DeepSeek辅助QGIS快速制图 | 麻辣GIS 示例代码说明：使用参考文章中的省会城市坐标点，左侧增加一列城市序号code, 图层标注显示 code 城市名称，同时在指定路径下生成对应SHP格式点数据。 import os fr…...

编程日记 2025/8/2 13:25:25

torcharrow gflags版本问题

问题描述其实仍然是很简单的编译问题，但是又弄了一整个下午加几乎整个晚上，进度缓慢，又吸取了教训，因而还是来记录一下。在试图使用torcharrow进行推荐系统模拟的时候，撰写的python程序报错：ERROR: flag…...

编程日记 2025/8/5 5:14:22

Spring IoC DI入门

一、Spring，Spring Boot和Spring MVC的联系及区别 Spring是另外两个框架的基础，是Java生态系统的核心框架，而SpringMVC是Spring 的子模块，专注于 Web 层开发，基于 MVC 设计模式（模型-视图-控制器&#xff…...

编程日记 2025/8/5 5:44:08

Vala编程语言教程-语言元素

语言元素方法在Vala中，函数无论是否定义在类内部均称为方法。下文将统一使用“方法”这一术语。 int method_name(int arg1, Object arg2) {return 1; } 此代码定义了一个名为 method_name 的方法，接受两个参数（一个整数值，一…...

编程日记 2025/8/2 13:30:54

数据可信安全流通实战，隐语开源社区Meetup武汉站开放报名

隐语开源社区 Meetup 系列再出发！2025 年将以武汉为始发站，聚焦"技术赋能场景驱动"，希望将先进技术深度融入数据要素流转的各个环节，推动其在实际应用场景中落地生根，助力释放数据要素的最大潜能&#xff01…...

编程日记 2025/8/5 22:17:26

windows 10 系统配置Node

目录什么是Node.js 什么是Npm Node.js环境搭建下载解压配置环境变量 npm配置如何运行下载的Node.js项目什么是Node.js 在 Node.js 之前，JavaScript 只能运行在浏览器中，作为网页脚本使用，为网页添加一些特效，或者和…...

编程日记 2025/8/6 17:56:24

2025年Postman的五大替代工具

虽然Postman是一个广泛使用的API测试工具，但许多用户在使用过程中会遇到各种限制和不便。因此，可能需要探索替代解决方案。本文介绍了10款强大的替代工具，它们能够有效替代Postman，成为你API测试工具箱的一部分。什么是Postman&…...

编程日记 2025/8/2 13:42:27

城市街拍人像自拍电影风格Lr调色教程，手机滤镜PS+Lightroom预设下载！

调色教程城市街拍人像自拍的电影风格 Lr 调色，是利用 Adobe Lightroom 软件，对在城市街景中拍摄的人像自拍照片进行后期处理，使其呈现出电影画面般独特的视觉质感与艺术氛围。通过一系列调色操作，改变照片的色彩、明暗、对比等元…...

编程日记 2025/8/5 16:48:53

HTML图像标签的详细介绍

1. 常用图像格式格式特点适用场景JPEG有损压缩，文件小，不支持透明适合照片、复杂图像PNG无损压缩，支持透明（Alpha通道）适合图标、需要透明背景的图片GIF支持动画，最多256色简单动画、低色彩图标WebP谷歌开…...

编程日记 2025/8/1 14:43:48

C++进阶——红黑树的实现

目录 1、红黑树的概念 1.1 红黑树的定义 1.2 红黑树的规则 1.3 为什么没有一条路径会比其他路径长出两倍 1.4 红黑树的性能 2、红黑树的实现 2.1 红黑树的结构 2.2 红黑树的插入 2.2.1 红黑树插入一个值的大概过程 2.2.2 情况1：变色 2.2.3 情况2&#xff…...

编程日记 2025/8/1 23:00:13

Linux 文件操作-标准IO函数1-文件指针、文件缓冲区(行缓冲、全缓冲、无缓冲)的验证

目录 1.文件指针 2.文件缓冲区 2.1 行缓冲 2.2. 全缓冲 2.3. 无缓冲 3. 程序验证： （1）main.c执行test1(),打印hello world，不加 \n 换行符 （2）刷新缓冲区方法1：使用\n （3&am…...

编程日记 2025/8/5 8:13:55

中国历史文化名城分布矢量数据

中国，这片古老而厚重的土地，承载着上下五千年的文明，从北国的冰天雪地到南疆的热带雨林，从东海之滨的波涛汹涌到西域大漠的风沙漫天，无数的历史文化名城如繁星般散布其间。它们是岁月长河中沉淀下来的瑰宝&#xff0…...

编程日记 2025/8/3 7:57:55

蓝桥杯十天冲刺-day1（日期问题）

日期问题基础循环遍历模板对于蓝桥杯所有的日期问题遍历，都可以使用的上 for(year2000;year<2022;year) for(month1;month<12;month) for(day1;day<31;day) {if(month1||month3||month5||month7||month8||month10||month12);else if(month2){if((year…...

编程日记 2025/7/31 23:57:52

漏洞知识点《Tornado框架中RequestHandler的对象》

Tornado框架中RequestHandler的所有对象 [SUPPORTED_METHODS, _INVALID_HEADER_CHAR_RE, __class__, __delattr__, __dict__, __dir__, __doc__, __eq__, __format__, __ge__, __getattribute__, __gt__, __hash__, __init__, __init_subclass__, __le__, __lt__, __module__,…...

编程日记 2025/8/7 14:41:02