位运算的奇技淫巧

2024-01-20 19:20
文章标签 运算 奇技淫巧

本文主要是介绍位运算的奇技淫巧,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

常见位运算总结:

1、基础位运算

左移<<运算

将二进制数向左移位操作,高位溢出则丢弃,低位补0。

右移>>运算

右移位运算中,无符号数和有符号数的运算并不相同。对于无符号数,右移之后高位补0;对于有符号数,符号位一起移动,正数高位补0,负数高位补1

按位与&运算

有0就是0,巧计:&这个符号像是有两个0组合而成。

按位或 | 运算

有1就是1,巧计:|本身就像一个1

按位异或^运算(两种解释方法)

相同为0,相异为1,或者解释成无进位相加

2、给一个数n,确定它的二进制表示中的第x位是0还是1

(n >> x) & 1

&1后的结果就是0/1,因为1的二进制位除了最后一位,其他都是0,&0就是0

3、将一个数n的二进制位的第x位改成1

n =(1 << x)|  n

4、将一个数n的二进制位的第x位改成0

n = n & (~(1 << x))

5、位图的思想

本质上就是一个哈希表

6、提取一个数(n)二进制表示中最右侧的1(lowbit

n & -n

解释:-n的操作就是先取反,然后再+1,这样造成的影响是最右边的1前面都是n的相反数,这样再跟原先的n&,因为是相反数,所以有一方肯定是0,这样最右边的1前面的数字都变成了0,最右边1右边本身就是0。

7、干掉一个数(n)最右边的1

n &(n - 1)

8、位运算的优先级

为了避免记住闲杂的公式,我们只需要记住能加括号就加括号。

9、异或运算的运算规律

  • a ^ 0 = a
  • a ^ a = 0(消消乐)
  • a ^ b ^ c = a ^ (b ^ c)

上面的指示是位运算的基础知识,下面就带着上面的指示开始实操啦

第一题:
191. 位1的个数

编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为 '1' 的个数(也被称为汉明重量)。

解析:

只需要每次右移&1判断是否为1。

原码:

class Solution {
public:int hammingWeight(uint32_t n) {int sum = 0;int ret = n;for(int i = 0;i<32;i++){if(ret & 1 == 1) sum++;ret = ret >> 1;}return sum;}
};

第二题、461. 汉明距离

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 x 和 y,计算并返回它们之间的汉明距离。

解析:

根据题目来看,可能最先想到的就是异或操作,相同为 0,不同为 1。异或操作后结果为 0101,然后我们只需要统计出来二进制结果中 1 的个数就可以计算出来汉明距离啦。

原码:

class Solution {
public:int hammingDistance(int x, int y) {int ret = x ^ y;int sum = 0;//计算1的个数for(int i = 0;i<32;i++){if(ret & 1 == 1) sum++;ret = ret >> 1;} return sum;}
};

第三题、136. 只出现一次的数字

给你一个 非空 整数数组 nums ,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。

解析:

这是一道很典型的运用^的题目,我们只需要理解异或运算符,这题就迎刃而解啦。

原码:

class Solution {
public:int singleNumber(vector<int>& nums) {int ret = 0;for(int i = 0;i<nums.size();i++){ret = ret ^ nums[i];}return ret;}
};

第四题、260. 只出现一次的数字 III

给你一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

解析:

本题是上一题的升级版,

把nums中的元素全部异或起来的结果eor就是那两个只出现一次的数字的异或结果。而这两个数不相同,意味着eor至少有一位是1,我们可以用lowbit运算拿到最低位的1,然后遍历nums数组,将所有数nums[i]按照这一位是不是1分成两类,初始化num1=num2=0

  1. 如果当前位是1,就将nums[i]异或到num1​上。

  2. 如果当前位是0,就将nums[i]异或到num2​上。

这样一来,两个只出现一次的数就会被分别异或到num1​和num2​上,而其他数也会被分别异或到这两个数上。而由于其他数都出现了两次,所以最终它们就会被异或成0,num1​和num2​就是那两个只出现一次的数。

注意进行位运算的优先级,直接加上括号就好!!!

原码:

class Solution {
public:vector<int> singleNumber(vector<int>& nums) {int a = 0, b = 0;//记录两个不同的数int ret = 0;for(int i = 0;i<nums.size();i++)ret ^= nums[i];//进行lowbit运算,两者不同,二进制肯定有1int tmp = ret & (-(long long)ret);//防止数据溢出for(int i = 0;i<nums.size();i++){if((tmp & nums[i]) == 0)//注意优先级! a ^= nums[i];else b ^= nums[i];}return {a,b};}
};

第五题、面试题 01.01. 判定字符是否唯一

解析:

本题第一思想直接用哈希表解决,但题目中用说尽量不用数据结构,我们可以尝试用位图解决!

用位图解决,需要熟练掌握位运算技巧,对巩固位运算有很大帮助!

原码:

class Solution {
public:bool isUnique(string astr) {int bitmap = 0;//用位图思想解决int tmp = 0;int n = astr.size();//利用鸽巢原理优化if(n > 26) return false;for(int i = 0;i<astr.size();i++){tmp = astr[i] - 'a';//判断字符是否已经出现过if(((bitmap >> tmp) & 1) == 1) return false;//把当前字符加入位图中bitmap = bitmap | (1 << tmp);}return true;}
};

第六题、371. 两整数之和

给你两个整数 a 和 b ,不使用 运算符 + 和 - ,计算并返回两整数之和。

思路:

我们前面介绍了^运算的另一个功能是不进位相加,因此我们可以利用这个特性去解决这道题。

因为是不进位,所以我们要想办法去解决进位的问题,^运算是相同为0,相异为1,相异不可能进位,只有相同并且都是1的情况下,才会进位,因此我们直接&,查找出都是1,因为是进位,所以还要左移一位,(a & b)<< 1,然后分别重制a,b的值。

原码:

class Solution {
public:int getSum(int a, int b) {while(b){int tmp = a;a = a ^ b;b = ((tmp&b) << 1);}return a;}
};

第七题、137. 只出现一次的数字 II

给你一个整数数组 nums ,除某个元素仅出现 一次 外,其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

解析:

本题有点难度,两层嵌套循环,根据32位int,把每个数位相加再对3取的余数即可,将每个数想象成32位的二进制,对于每一位的二进制的1和0累加起来必然是3N或者3N+1, 为3N代表目标值在这一位没贡献,3N+1代表目标值在这一位有贡献(=1),然后将所有有贡献的位|起来就是结果。这样做的好处是如果题目改成K个一样,只需要把代码改成cnt%k,很通用~

原码:

class Solution {
public:int singleNumber(vector<int>& nums) {int ans = 0;int n = nums.size();for(int i = 0;i<32;i++)//依次去修改ans的每一位{int sum = 0;for(int j = 0;j<n;j++){//计算nums中所有数的第i位的和sum += (nums[j] >> i) & 1;}//把第i位修改if(sum % 3)   ans ^= (1 << i); }return ans;}
};

第八题、面试题 17.19. 消失的两个数字

给定一个数组,包含从 1 到 N 所有的整数,但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗?

以任意顺序返回这两个数字均可。

解析:

本题是两道题的融合版。

  • 将所有的数异或在一起,记为tmp
  • 找到tmp中,比特位上为1的那一位
  • 根据不同的那一位,划分为两类异或

原码

class Solution {
public:vector<int> missingTwo(vector<int>& nums) {int a = 0,b = 0;int n = nums.size();int ret = 0;//先将所有数异或for(int i = 1;i<=n+2;i++)ret ^= i;for(int i = 0;i<n;i++)ret ^= nums[i];//lowbit运算找到最右边的1int tmp = ret & (-(long long)ret);//防止溢出for(int i = 0;i<n;i++){if((nums[i] & tmp) == 0) a ^= nums[i];else b ^= nums[i];}for(int i = 1;i<=n+2;i++){if((i & tmp) == 0) a ^= i;else b ^= i; }return {a,b};}
};

这篇关于位运算的奇技淫巧的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/627069

相关文章

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

uva 575 Skew Binary(位运算)

求第一个以(2^(k+1)-1)为进制的数。 数据不大,可以直接搞。 代码: #include <stdio.h>#include <string.h>const int maxn = 100 + 5;int main(){char num[maxn];while (scanf("%s", num) == 1){if (num[0] == '0')break;int len =

【Java中的位运算和逻辑运算详解及其区别】

Java中的位运算和逻辑运算详解及其区别 在 Java 编程中,位运算和逻辑运算是常见的两种操作类型。位运算用于操作整数的二进制位,而逻辑运算则是处理布尔值 (boolean) 的运算。本文将详细讲解这两种运算及其主要区别,并给出相应示例。 应用场景了解 位运算和逻辑运算的设计初衷源自计算机底层硬件和逻辑运算的需求,它们分别针对不同的处理对象和场景。以下是它们设计的初始目的简介:

位运算:带带孩子吧,孩子很强的!

快速进制 在聊到位运算之前,不妨先简单过一遍二进制的东西。熟悉二进制和十进制的快速转换确实是掌握位运算的基础,因为位运算直接在二进制位上进行操作。如果不熟悉二进制表示,很难直观理解位运算的效果。 这里主要涉及二进制和十进制之间的互相转换。 十进制转二进制 十进制转二进制可以使用常见的 除2取余法 进行。每次将十进制除以2并记录所得余数,直到商为0,然后再将记录的余数 从下往上排列即

快速幂运算的一些模板

这里用递归和循环两种做法来做。 简单来说,快速幂就是把底数扩大,指数缩小,比如2*2=4;计算2的幂时,就可以转换成4的幂来运算,这样可以避免在计算大的数据时爆int的现象  //递归int power(int a,int n){int ans;if(n==2) ans=1;else{ans=power(a*a,n/2);if(n%2==1) ans*=a;}return ans;}

高精度计算----减法运算(浮点型)

基于上一贴,修改减法运算适合于高精度浮点型计算。 因为减法比加法难度大一点,考虑的地方也要多一些,可能代码有欠缺,欢迎指出。 运算说明: 1、相减函数依旧没改变,包括上一贴的判断被减数与减数的大小函数也没变。 2、增加两个函数,取小数位数函数和结果处理(回归小数点)函数 3、与加法浮点高精度运算相比,这里改变较多的是结果处理函数,加法加完后,位数不减反增,而且最多增一位。减法会消失掉好多

高精度计算----减法运算

处理大数减法运算: 1、首先要判断被减数与减数哪个更大,再相应的带入减法函数去处理。具体的比较可以使用字符串的相关知识去比较。 2、相减要先对齐数组,依照减数的长度,执行相应的减法运算次数。 3、不需要借位相减的话,直接减去;需要的话,向前借一位,若前一位是0,则再前借(此时前一位的0变为10)。 测试程序效果如下:   以下代码包括相减函数,比较被减数减数函数,若有错误,请指出:

Python中的位运算-从入门到精通

你是否曾经好奇过计算机是如何在底层处理数据的?或者,你是否想知道为什么有些程序员总是津津乐道于位运算的强大?如果是,那么你来对地方了!今天,我们将深入探讨Python中的位运算,揭示它们的神奇之处,以及如何利用它们来优化你的代码。 目录 位运算:计算机的秘密语言为什么位运算重要? Python中的位运算操作符1. 按位与 (&)2. 按位或 (|)3. 按位异或 (^)4. 按位取反 (~

CSS 有什么奇技淫巧

不是什么奇技淫巧,但是一行css代码可能让你省下js代码 ,作为前端的你变得更加专业: 1. 阻止鼠标选择文本 .no-select { user-select: none } 阻止用户在页面上选择文本。 2. 响应式文字大小 /* Fixed minimum value below the minimum breakpoint */.fluid {font-size

【OpenCV2.2】图像的算术与位运算(图像的加法运算、图像的减法运算、图像的融合)、OpenCV的位运算(非操作、与运算、或和异或)

1 图像的算术运算 1.1 图像的加法运算 1.2 图像的减法运算 1.3 图像的融合 2 OpenCV的位运算 2.1 非操作 2.2 与运算 2.3 或和异或 1 图像的算术运算 1.1 图像的加法运算 add opencv使用add来执行图像的加法运算 图片就是矩阵, 图片的加法运算就是矩阵的加法运算, 这就要求加法运算的两张图shape必须是相同的. # 图片加法imp