大家好,我是LvZi,今天带来
位运算算法系列|概念讲解|例题讲解
一,位运算基本概念
1.基础位运算
- <<:左移操作,相当于 *2
- >>:右移操作,相当于 /2
- ~:按位取反
&:按位与操作,有0则0|:按位或操作,有1则1^:按位异或操作,相同为0,相异为1/无进位相加
注:对于
^操作,无进位相加值得是在相加的过程中不产生进位操作(出现进位也不相/2加)
- 需要注意的是尽管通过
>>1或者<<1来替代/2和*2,会使得程序的运行速度加快,但是由于优先级的问题,会经常出错,其实也不需要考虑优先级的高低,按照自己的逻辑运算先后添加()即可
如何理解^运算的本质是无进位加法呢
- 两个二进制正常相加的结果和十进制相加的结果相同
- 二进制相加只可能是三种情况
0+0,1+0,1+1 - 对于前两种情况:
0+0 = 0^0 = 0,0+1 = 0^1 = 1,异或的结果和正常相加的结果相同 - 对于最后一种情况,虽然
1+1 = 1^1 = 0,但是对于正常的二进制相加,会存在进位,对于^操作,不存在进位,也不会向前进位 - 综上,
^被称为无进位加法
2.位图
给一个数n,判断 第
x位数字是0/1
核心公式:n &= (1 << x),设最后的结果为ret
- ret == 0 则x == 0
- ret == 1 则 x == 1
注意:对于一个32位的数字,最右边的下标我们设为0,这样方便进行移位操作
给一个数n,将第x位修改为1,其余位保持不变
核心公式:n |= (1 << x)
可以这么想,既然要出现1,想想哪个位运算操作容易出现1?当然是|操作,因为按位或是有1则1,特别容易出现1,所以使用|操作,将第x位设置为1,就让1 << x位
给一个数n,将第x位修改为0
核心公式:n &= ~(1 << x)
和上述想法一致,&操作出现0的概率更大,所以使用&操作,让第x位和0 &操作,一定能出现0,其余位都设置为1
让二进制位不发生改变的算法:&1或者|0
位图
对于一个整数来说,其本质上是一个32位的二进制数,位图思想就是利用这32个0,1数字来存储信息的一种方式
给定一个数n,提取最右侧的1(Lowbit)
核心公式:n & (-n)
n -> (-n),分为两步:
- 按位取反 ~
- 加一
-n的操作实际上是把n中最右侧的1的左边区域全部取反,右侧保持不变(全是0),1仍是1
所以让(-n)和n进行&,左侧全部变为0右侧也全是0
给定一个数n,将最右侧的1变为0
核心公式:n & (n - 1)
最右侧的1的右边全为0,如果进行 - 1操作,一定会向前要位,直到要位到最右侧的1,最右侧的1变为0,左侧区域不变,右侧区域全部变为1,这就是 n - 1的最终结果
再进行&操作,左侧区域由于相同,最终的结果不变,右侧区域不同,变为0
3.异或运算规律
a ^ 0 = a
a ^ a = 0
a ^ b ^ c = a ^ (b ^ c)
第三个运算规律非常好用!
二.例题讲解
01.只出现一次的数字
链接:https://leetcode.cn/problems/single-number/description/
分析
- 经典的位运算问题,使用
^操作的运算性质求单身狗问题 a^a = 0; a ^ 0 = a- 如果数字出现次数为两次,那么^的结果一定是0,最后只会保存
只出现一次的那个数字
class Solution {public int singleNumber(int[] nums) {int x = 0;for(int n : nums)x ^= n;return x;}
}
02.只出现一次的数字(III)
链接:https://leetcode.cn/problems/single-number-iii/description/
分析
- 本题有两个数字出现的次数均为1,将数组中的每一个元素遍历完毕的结果是这两个数字的异或结果,即
a^b,想办法将这两个数字分离,找这两个数字的不同点 - 找ret的
lowbit,a和b两个数字在此位置一定是一个为0,一个为1,根据这个性质可以将整个数组分为两类 - 如何分离?如果nums在lowbit位置为0,则
^lowbit的结果一定是0;
代码:
public int[] singleNumber(int[] nums) {// 1.获得异或结果int ret = 0;for(int x : nums) {ret ^= x;}// 2.得到最右边的1int bitmask = ret & (-ret);// 3.分组int a = 0, b= 0;for(int x : nums) {if((x & bitmask) != 0) a ^= x;else b ^= x;}return new int[]{a,b};}
03.位1的个数(经典)
链接:https://leetcode.cn/problems/number-of-1-bits/
分析
本题可以看做一个母题了,核心是利用 & 操作统计一个整数的二进制中有多少1
n &= (n-1)这个运算是将n的最右侧的1变为0,每运算一次,n的二进制中的1的个数就少1- 最终n会变为0,经过几次
n &= (n-1)运算,就有多少个1
public int hammingWeight(int n) {// 本题是经典的统计一个整数的二进制中1的个数问题int cnt = 0;while(n != 0) {n &= (n-1);// 这个操作每次都把n的最右侧的1变为0 一共变了几次就有多少个1cnt++;}return cnt;}
相似题:
比特位计数:https://leetcode.cn/problems/counting-bits/
说明:
- 对于java来说,在Integer包装类内部内置了
bitCount方法,专门统计一个整数n的二进制位中1的数目
04.汉明距离(重点)
链接:https://leetcode.cn/problems/hamming-distance/description/
分析
-
本题其实是上一题的
拓展,在上题中是统计二进制中1的个数,此题也可以进行转化 -
如果两个数字对应的二进制位不同,只可能是一个为0,一个为1,异或结果一定是1,相同位置异或的结果就是0(设得到的结果为ret)
-
则ret的二进制中
1的数目就是两个数字二进制位不同的位置的数目,这样就转化为求一个整数对应二进制位中1的个数的问题 -
^操作相同为0,相异为1
代码:
// 先异或--结果中的1的个数就是x,y中不同的二进制位的个数// 转化为判断n中有多少个1int n = x ^ y, ret = 0;while(n != 0) {n &= (n - 1);ret ++;}return ret;
补充:Java中内置了一个求二进制中1的个数的函数
// Java中内置的统计1的个数的函数return Integer.bitCount(x ^ y);
相似题:
汉明距离总和:https://leetcode.cn/problems/total-hamming-distance/
05.判定字符是否唯一(面试题)
链接:https://leetcode.cn/problems/is-unique-lcci/
分析
-
此题的常规做法很简单,;利用HashMap或/Set来处理重复情况
-
进阶是不使用任何的数据结构,但是我们需要
使用集合来保存字符,在不使用数组的情况下,有一个特别巧妙的方法位图 -
对于一个整数来说,其本质上是一个
32位的二进制数,可以看做是一个长度为32整形数组,数组中只能存储0或1 -
我们可以使用0和1来作为
一种标识,在本题中每遍历到一个字符,就将对应的下标设置为1,代表该字符已经出现,在添加之前先判断该位置是否为1,如果为1,就代表重复出现
public boolean isUnique(String astr) {// 位运算解决// 使用位图的思想 因为一共只有26中情况(全为小写)// 通过这种标记的方式避免使用额外的数据结构// 使用一个32位的二进制数// 如果字符出现 就将对应的位置标记为1int x = 0;for(int i = 0; i < astr.length(); i++) {char ch = astr.charAt(i);int charIndex = ch - 'a';// 判断if((x & (1 << charIndex)) != 0) return false;x |= (1 << charIndex);}return true;}
方法二
- 还有一种经典的做法使用
^1更改奇偶性 - 尤其是对于二进制压缩问题,数字要么是0,要么是1,假设0代表出现的次数为偶数,1代表出现的次数为奇数
- 如果原先是0,^1之后成为1,
偶数->奇数 - 如果原先是1,^1之后成为0,
奇数->偶数 - 如果某个字符出现的次数为偶数次,^1的结果一定是0,根据这个条件判断
代码:
class Solution {public boolean isUnique(String astr) {int x = 0;// 位图数字for(char ch : astr.toCharArray()) {int charIndex = ch - 'a';// 找到字符对应的位置(下标从0开始)x ^= (1 << charIndex);// 异或操作 0->1 1->0if((x & (1 << charIndex)) == 0) return false;// 如果有0 证明出现次数为偶数次}return true;}
}
06.消失的两个数字
链接:https://leetcode.cn/problems/missing-two-lcci/description/
分析
- 本题是只出现一次的数字III和丢失的数字的综合应用
代码:
class Solution {public int[] missingTwo(int[] nums) {int n = nums.length;int tmp = 0;for(int i = 1; i <= n+2; i++) tmp ^= i;for(int i = 0; i < n; i++) tmp ^= nums[i];// 2.得到最右边的1int bitmask = tmp & (-tmp);// 3.分组int a = 0, b= 0;for(int x : nums) {if((x & bitmask) != 0) a ^= x;else b ^= x;}for(int i = 1; i <= n + 2; i++) {if((i & bitmask) != 0) a ^= i;else b ^= i;}return new int[]{a,b};}
}
07.两整数之和
链接:https://leetcode.cn/problems/sum-of-two-integers/
分析
- 题目要求不能使用
+,-等运算符 - 最经典的做法就是利用
^运算的本质是无进位相加的特点 - ^运算是无进位加法,那么如何产生进位,使其变成正确的结果呢?要进位的地方是
两个数字最右边全是1的两个比特位的最近的左边一位,这个位置的计算结果相较于正确结果少了1,需要在这个位置加上1(注意加上之后可能有存在进位,应该重复执行上述操作,直到进位为0)
代码:
循环解法
class Solution {public int getSum(int a, int b) {while (b != 0) {int x = a ^ b;// 无进位加法int carry = ((a & b) << 1);// 计算进位a = x;b = carry;}return a;}
}
递归解法
class Solution {public int getSum(int a, int b) {if(b == 0) return a;return getSum(a ^ b, ((a & b) << 1));}
}
09.2的幂
链接:https://leetcode.cn/problems/power-of-two/submissions/542332234/
分析
- 2的幂的二进制位中,
只有一个1
代码
方法一:统计二进制位中1的个数
class Solution {public boolean isPowerOfTwo(int n) {if(n < 0) return false;return Integer.bitCount(n) == 1;}
}
方法二:利用n&(n - 1)
n&(n-1):将n中最右侧的1更改为0- 由于2的幂只有一个1,更改为0之后一定为0
class Solution {public boolean isPowerOfTwo(int n) {if(n <= 0) return false;return ((n & (n - 1)) == 0);}
}
10.位运算其他技巧总结
1.不用临时变量交换两个数
int a = 0, b = 0;
a ^= b; // a = a ^ b
b ^= a; // b = b ^ a ^ b = a
a ^= b; // a = a ^ b ^ a = b
2.求绝对值
使用位运算来求整数的绝对值的表达式是 (x ^ (x >> 31)) - (x >> 31)。这是如何工作的：
-
x >> 31：- 这一步将
x右移31位，如果x是一个32位的整数（考虑到符号位），它将填充符号位。对于正数（或0），结果是0；对于负数，结果是-1。 - 例如，对于
x = -5：- 二进制表示：
11111111 11111111 11111111 11111011 - 右移31位：
11111111 11111111 11111111 11111111（即-1） - 对于
x = 5： - 二进制表示：
00000000 00000000 00000000 00000101 - 右移31位：
00000000 00000000 00000000 00000000（即0）
- 二进制表示：
- 这一步将
-
x ^ (x >> 31)：- 这一步利用异或运算（XOR）将
x进行条件取反。如果x是负数，它将x的每个位进行翻转。如果x是正数，这一步不会改变x。 - 例如，对于
x = -5：-5右移31位结果是-1（即所有位都是1）x ^ -1等于~x（即对x取反）：00000000 00000000 00000000 00000100（即4）- 对于
x = 5： 5右移31位结果是0x ^ 0结果仍然是5
- 这一步利用异或运算（XOR）将
-
(x ^ (x >> 31)) - (x >> 31)：- 如果
x是负数，x取反之后再减去-1，相当于加1，这样就得到了x的绝对值。 - 例如，对于
x = -5：(x ^ -1)结果是4- 再减去-1，结果是5
- 对于
x = 5：(x ^ 0)结果是5- 再减去0，结果仍然是5
- 如果
代码实现如下：
public int absolute_value(x) {return (x ^ (x >> 31)) - (x >> 31);
}
3.判断两个数符号是否相同
使用位运算判断两个数的符号是否相同可以通过 (a ^ b) >= 0 来实现。以下是原理解释：
-
a ^ b：- 异或运算
a ^ b会比较a和b的每一个对应的二进制位，如果相同则结果为0，不同则结果为1。 - 对于符号位（最高位），如果
a和b的符号相同（即符号位相同），则a ^ b的符号位将是0；如果符号不同，符号位将是1。 - 因此，如果
a和b符号相同，结果是非负数（符号位为0）；如果符号不同，结果是负数（符号位为1）。
- 异或运算
-
(a ^ b) >= 0：- 通过检查
a ^ b是否为非负数，可以判断a和b的符号是否相同。如果a ^ b的结果大于等于0，说明符号相同；否则符号不同。
- 通过检查
代码实现如下：
public boolean have_same_sign(a, b){return (a ^ b) >= 0;
}
总结:
- 对于位运算这个算法,预期叫做一种思想,不如当做一种
技巧,是一个加快运算速度的技巧 - 记住常见的集中位运算的性质和经典题目就可(求二进制中1的个数.利用
^操作更改奇偶性,利用&1操作判断元素的奇偶性…)
