Leetcode复盘8——位运算
导读
基本原理
0s 表示一串 0，1s 表示一串 1。
x ^ 0s = x x & 0s = 0 x | 0s = x
x ^ 1s = ~x x & 1s = x x | 1s = 1s
x ^ x = 0 x & x = x x | x = x
利用x ^ 1s = ~x的特点，可以将一个数的位级表示翻转；
利用x ^ x = 0的特点，可以将三个数中重复的两个数去除，只留下另一个数。
例如：
1^1^2 = 2
位与运算技巧
n & (n - 1)去除 n 的位级表示中最低的那一位 1。例如对于二进制表示 01011011，减去 1 得到 01011010，这两个数相与得到 01011010。
01011011 &
01011010
--------
01011010
n & (-n)得到 n 的位级表示中最低的那一位 1。-n 得到 n 的反码加 1，也就是 -n=~n+1。例如对于二进制表示 10110100，-n 得到 01001100，相与得到 00000100。
10110100 &
01001100
--------
00000100
移位运算
>> n为算术右移，相当于除以 2n，例如 -7 >> 2 = -2。
11111111111111111111111111111001 >> 2
--------
11111111111111111111111111111110
>>> n 为无符号右移，左边会补上 0。例如 -7 >>> 2 = 1073741822。
11111111111111111111111111111001 >>> 2
--------
00111111111111111111111111111111
<< n 为算术左移，相当于乘以 2n。-7 << 2 = -28。
11111111111111111111111111111001 << 2
--------
11111111111111111111111111100100
1.汉明距离 / 统计两个数的二进制表示有多少位不同（Leetcode461）
idea: 异或(xor)
将两个数字进行异或(即相同的位为0,不同的位为1),然后统计有多少位为1,即用异或结果与1进行"与"运算,即用末位与1进行与运算,为1的话count+1
e.g 1(0001)和4(0100)
res = 1 & 4 = (0101), 用res & 1,然后>>1进行右移,
第一轮: 0101 & 1 = 1(0001), count = 1, 右移: 0010
第二轮: 0010 & 1 = 0, count = 1, 右移: 0001
第三轮: 0001 & 1 = 0001, count = 2
代码：
Java版
class Solution {
public int hammingDistance(int x, int y) {
int z = x ^ y;
int count = 0;
while(z != 0) {
if ((z & 1) == 1) count++; // z & 1(二进制:0001),即看末位是否为1
z = z >> 1; // 右移一位
}
return count;
}
}
idea: 位运算
- n & (n - 1)可以去除n中的最低一位的1
- n & (-n)可以得到n的位级中表示最低的那一位1
方法跟之前的一样,先异或,然后用n&(n-1)的方法不停的去除最低一位的1,同时判断是否等于0了
Java版
class Solution {
public int hammingDistance(int x, int y) {
int z = x ^ y;
int count = 0;
while (z != 0) {
z &= (z - 1); // z = z & (z - 1)
count++; // 每去除一次最低一位的1(即1和4不同的位),count就加1
}
return count;
}
}
2.只出现一次的数字 / 数组中唯一一个不重复的元素（Leetcode136）
idea: 位运算(异或xor)
利用两个相同的数异或为0的特性,即x^x=0,将该数组中所有的元素进行异或,相同的同归于尽了,只剩下出现1次的
e.g nums = [4,1,2,1,2]
4: 0100, 1: 0001, 2: 0010
ret = 4 ^ 1 = 0101;
ret = ret ^ 2 = 0111;
ret = ret ^ 1 = 0110;
ret = ret ^ 2 = 0100 = 4;
代码：
Java版
class Solution {
public int singleNumber(int[] nums) {
int ret = 0;
for (int n : nums) ret = ret ^ n;
return ret;
}
}
3.丢失的数字 / 找出数组中缺失的那个数（Leetcode268）
idea: 位运算(异或xor)
利用自己和自己异或得0的特点,一共有n个数,大小为从0到n,故我们可以用下标异或数字本身来找到缺失的数,下标从[0]到[n],数字从[0]到[n]但中间缺了个数
e.g: nums = [3,0,1], 下标i从[0]到[3]: 3 -> [0], 0 -> [1], 1 -> [2]
对比正常的情况: nums = [3,0,1,2],下标i从[0]到[3]: 3 -> [0], 0 -> [1], 1 -> [2], 2 -> [3]
故用下标0,1,2,3异或数字3,0,1就能找到缺失的数字2
代码：
Java版
class Solution {
public int missingNumber(int[] nums) {
int ret = 0;
for (int i = 0; i < nums.length; i++) {
ret ^= i ^ nums[i];
}
return ret ^ nums.length; // 最后异或下标[n]
}
}
4.只出现一次的数字 III / 数组中不重复的两个元素（Leetcode260）
idea: 位运算(异或xor)
本题分为以下几部:
- 先让所有的数进行异或,相同的互相抵消,得到两个不同的数的异或结果,下一步是想办法把它俩区分开;
- 利用n & (-n)得到最后一位不为0的数的特点,提取最后一位的1,此即那两个不相同的数最右边的不同的位diff;
- 再次异或,这次分开异或,把跟最后一位不同的位diff进行"与运算"得到0的放一边,得到1的放另外一边.重复的数字都互相抵消了,不用考虑
e.g nums = [1,2,1,3,2,5]
代码：
Java版
class Solution {
public int[] singleNumber(int[] nums) {
int diff = 0;
for (int num : nums) diff ^= num; // 只剩3(0011)和5(0101)的异或结果0110
diff &= -diff; // 得到最右边不同的位: diff = 0010
int[] ret = new int[2]; // 最后返回两个数
for (int num : nums) {
if ((num & diff) == 0) ret[0] ^= num; // 数字5(0101)与0010与运算后得0(其他数字抵消了)
else ret[1] ^= num; // 数字3(0011)与0010与运算后的1(其他数字抵消了)
}
return ret;
}
}
11.两整数之和 / 实现整数的加法（Leetcode371）
idea: 位运算(异或xor)
a + b的问题拆分为(a和b的无进位结果)+(a和b的进位结果)
1.无进位加法使用异或运算计算得出(a^b)
2.进位结果使用与运算和移位运算计算得出(carry = (a & b) << 1)
循环此过程,直到进位carry为0
代码：
Java版
class Solution {
public int getSum(int a, int b) {
return b == 0 ? a : getSum((a ^ b), (a & b) << 1);
}
}
idea: 位运算(异或xor)
a + b的问题拆分为(a和b的无进位结果)+(a和b的进位结果)
1.无进位加法使用异或运算计算得出(a^b)
2.进位结果使用与运算和移位运算计算得出(carry = (a & b) << 1)
循环此过程,直到进位carry为0
e.g: a + b = 5(0101) + 4(0100)
第一轮: carry = (a & b) << 1 = (0101 & 0100) << 1 = 1000(进位), a = a ^ b = 0101 ^ 0100 = 0001, b = 1000
第二轮: carry = (a & b) << 1 = (0001 & 1000) << 1 = 0000(进位), a = a ^ b = 0001 ^ 1000 = 1001, b = 0000
Python版
class Solution:
def getSum(self, a: int, b: int) -> int:
MASK = 0x100000000
# 整型最大值
MAX_INT = 0x7FFFFFFF
MIN_INT = MAX_INT + 1
while b != 0:
# 计算进位
carry = (a & b) << 1
# 取余范围限制在[0,2^32-1]范围内
a = (a ^ b) % MASK
b = carry % MASK
return a if a <= MAX_INT else ~((a % MIN_INT) ^ MAX_INT)
13.比特位计数 / 统计从 0 ~ n 每个数的二进制表示中 1 的个数（Leetcode338）
idea: 位运算(与and)
要求某一个数的二进制1的个数,从1开始求,已知0的二进制中1的个数是0个
利用n & (n - 1)即n的二进制中去除最低一位的1,故可以+1再补回来.
e.g: 求0到5的二进制中1的个数
求ret[1]:ret[1&0]=ret[0]即数字1被数字0干掉了最低一位的1,变成了数字0,在这基础上再加回来;
求ret[2]:ret[2&1]=ret[0]即数字2被数字1干掉了最低一位的1,变成了数字0,在这基础上再加回来;
求ret[3]:ret[3&2]=ret[2]即数字3被数字2干掉了最低一位的1,变成了数字2,在这基础上再加回来;
求ret[4]:ret[4&3]=ret[0]即数字4被数字3干掉了最低一位的1,变成了数字0,在这基础上再加回来;
求ret[5]:ret[5&4]=ret[4]即数字5被数字4干掉了最低一位的1,变成了数字4,在这基础上再加回来;
代码：
Java版
class Solution {
public int[] countBits(int num) {
int[] ret = new int[num + 1];
for(int i = 1; i <= num; i++) {
ret[i] = ret[i & (i - 1)] + 1; // 数字i被数字(i-1)干掉了最低一位的1,变成了"i&(i-1)",再在它的基础上再加回来
}
return ret;
}
}