算法总结-位操作
位操作是计算机底层使用二进制运算时实际使用的操作，主要包括以下几种
|按位或&按位与^异或~取反>>右移<<左移- 有些语言还有
>>>逻辑右移
位运算的一些“骚”操作
位操作与数值在计算机中的表示方式息息相关，整数使用补码表示，正整数补码与原码相同，负数等于绝对值的原码取反+1，上面数位操作是计算机中底层使用的操作，如加法，使用循环计数加法器，对应LeetCode 371.不使用加减运算符实现两个数相加。
class Solution_371:
def getSum(self, a, b):
# Bit manipulation
# 使用二进制循环进位加法器的原理
mask = 0xffffffff
res = 0
c = 0
for i in range(32):
ai = ((a & mask) >> i) & 1
bi = ((b & mask) >> i) & 1
s = (ai ^ bi ^ c)
c = (ai & bi) | (ai & c) | (bi & c)
res |= (s << i)
# 为了处理python不会溢出的问题
bins = bin(res & mask)[2:].zfill(32)
return int(bins[1:], 2) - int(bins[0]) * (1 << 31)
算法中使用位操作可以有更快的运算速度，合理运用位操作还能获得神奇的解法。下面来看一看位运算中有那些”骚操作”。
1.x & 1 取最低有效位的值，可以通过是否为1来判断x的奇偶性,例如快速幂：
def big_pow(a, b):
# 快速求a的b次幂
r = big_pow(a, b//2)
if b & 1: # b为奇数
return r*r*a
else: #b为偶数
return r*r
2.x & (x-1) 将x最低的一位1置零，例如
x = 0b1100
x-1 = 0b1011
x & (x - 1) = 0b1000
这个在实际中可以用来判断x是否是2的幂，也可用来数x的二进制表表示中1的个数。
def is_pow_of_2(x):
cnt = 0
while x:
x &= (x-1)
cnt += 1 # cnt是x的二进制表表示中1的个数
return cnt == 1 # 二进制表示中只有一位1就是2的幂了（正整数）
3.对x&(x-1)结合异或操作的话，就可以得到x ^ (x & (x-1))，返回x最右边一位1对应位为1其余位为0的数。同样也可以使用x & (-x)或者是x&(~(x-1))来实现这个。
x = 0b00001000
x-1 = 0b00000111
~(x-1) = 0b11111000 # ~(x-1)再加一的话表示 -(x-1), 因此~(x-1) = -x
x & (x-1) = 0b00000000
-x = 0b11111000 # 负数的补码表示 x取反加一
x & (-x) = 0b00001000
x & (~(x-1)) = 0b00001000
x ^(x & (x-1)) = 0b00001000
# 上述语句实现这样的功能
# mask = 1
# for i in range(32):
# if r & mask == mask:
# break
# mask<<=1
# 获得mask
4.x ^ x = 0 这是一个特别有用的性质，比如可以用来实现swap。
void swap(int &a, int &b){
a ^= b;
b ^= a;
a ^= b;
}
再比如LeetCode 136.找一个数组中唯一一个出现一次的数，其余数出现两次。
class Solution_136:
def singleNumber(self, nums: List[int]) -> int:
r = 0
for x in nums:
r ^= x
return r
5.C++之类的语言中，可以使用(x ^ (x»31)) - (x»31) 来对32位int值x取绝对值（python整数不会溢出，所以不能这么干）。
int abs(int a){
(x ^ (x>>31)) - (x>>31);
}
6.因为python整数不会溢出，所以处理负数位操作会有点麻烦，可以这样转换。
def to_int32(x):
mask = 0xffffffff
bins = bin(x & mask)[2:].zfill(32)
return int(bins[1:], 2) - int(bins[0]) * (1 << 31)
一些题目实例
接下来记一些在实际题目中灵活应用的操作。 前面LeetCode 371.的例子还有一种不太直观的解法，分两种情况来处理
- a,b对应位都是
1，则该位上会产生一个进位，使用a & b产生进位，并左移一位（向做进位）。 - a,b对应位不都为
1，该位上不产生进位，使用a ^ b获取这一部分的结果。class Solution_371: def iterative_getSum(self, a: int, b: int) -> int: # 迭代形式 if a == 0 or b == 0: return a | b mask = 0xffffffff while b & mask: c = (a & b) << 1 # 进位 a = a ^ b # 把部分"加"的结果存进a b = c # 把进位赋值给b 进入下一轮迭代 return a & mask if b > mask else a def recursive_getSum(self, a: int, b: int) -> int: # 递归形式 return a if b==0 else recursive_get_sum(a^b, (a&b)<<1)LeetCode 137. 一个数组中，只有一个数出现一次，其余数出现三次，找出这个数。最简单的办法是用额外的空间存一下都有那些数，对其求和，和的三倍减去数组元素和除以2就是要找的数字，这样时间复杂度和空间复杂度都是
O(n)，代码如下解法1。
更好的解法是统计32位数上每一位上1出现的次数，如果是3的倍数，则结果的该位为0，否则为1，代码如解法2。
一个更好的思路是沿续解法2的思路，模3的值只有0b00,0b01,0b10三种，因此可以使用两个状态来表示当前位1的总数%3，对应表示某个数x是第一出现还是第二次出现，没出现是状态位为(0, 0), 第一次出现状态为更新为(0, 1)，第二次出现状态为更新为(1, 0),再次出现则重置为(0, 0)，这样对于任何一个出现三次的数，两个状态量都必定为0，最终只出现一次的状态量中保存的就是结果值。
class Solution_137:
def singleNumber(self, nums: List[int]) -> int:
# 解法1
# using extra space for set
return (3 * (sum(set(nums))) - sum(nums)) // 2
def singleNumber(self, nums: List[int]) -> int:
# 解法2
# 对于每一位如果 1 出现的总次数是3的倍数，则该位为0，否则该位为1
res = 0
for i in range(32):
v = 1 << i
s = sum([x & v != 0 for x in nums])
if s % 3 != 0:
res |= v
if res > (1 << 31) - 1:
return (res & 0x7fffffff) - (1 << 31) # python负数
return res
def singleNumber(self, nums):
# 解法3
# 状态记作(b, a)，这样对每一位有 真值表如下：
# b a x | b' a'
# 0 0 0 | 0 0
# 0 0 1 | 0 1
# 0 1 0 | 0 1
# 0 1 1 | 1 0
# 1 0 0 | 1 0
# 1 0 1 | 0 0
# 状态转移为(0, 0) -> (0, 1) -> (1, 0) -> (0, 0)的循环
# 使用卡诺图化简上述真值表，得到表达式为：
# a' <-- (~b) & (a ^ x) (1)
# b <-- (~b)ac | b(~a)(~c) (2)
# 如果将第一步a已经赋值考虑进去，第二步可以改写为
# b <-- (~a') & (b ^ x)
# 代码如下
sone = stwo = 0
for x in nums:
sone = (sone ^ x) & ~stwo
stwo = (stwo ^ x) & ~sone
return sone
对于题目LeetCode 260.一个数组中有两个数只出现出现一次，其余数出现两次，找出那两个只出现一次的数。这题与LeetCode 136.的区别是只出现一次的数多了一个，假设只出现一次的数为a和b，直接对数组元素进行异或操作只能得到a^b的值，需要一些额外的操作将a和b区分开，注意到a^b为1的位一定是a和b对应位不同才得到的，因此我们可以使用这一不同将a和b区分开。
class Solution_260:
def singleNumber(self, nums: List[int]) -> List[int]:
r = 0
for n in nums:
r ^= n
# 上述循环结束后 r = a^b (a, b是要找的两个只出现一次的数)，
# 其最低位的1一定是由于a,b对应位置不同才出现的 0^1 = 1^0 = 1,
# 于是通过判断nums中数的这一位为0还是为1可以将nums分为两组，
# 一组是包含a,和其他出现两次的数；另一组是包含b和剩下出现两次的数。
# 这样分别对两组数异或，就可以求出a, b了
mask = r & (-r) # 或 mask = r & ~(r-1) 或 mask = r ^ (r & (r -1))
res = [0, 0]
for n in nums:
if n & mask:
res[0] ^= n
else:
res[1] ^= n
return res
可以用位来表示集合，1表示对应元素存在集合中，0表示不存在。对LeetCode 78. 生成所有子集问题，可以通过回溯的方法生成，也可直接枚举，注意子集的数目是$2^n$, n是集合元素数目，可以通过n位的数字，对应位是否为1表示对应元素是否在子集中。
class Solution_78:
def subsets(self, nums):
# 使用位操作来生成所有子集（注意溢出问题）
# 对应位i为 1 表示取nums[i]这个元素，否则不取
t = 1 << len(nums)
res = []
for i in range(t):
tmp = []
for j in range(len(nums)):
if i & (1 << j):
tmp.append(nums[j])
res.append(tmp)
return res
同样的经典的8皇后问题也是一个使用回溯可以解的问题，使用位操作可以更优雅的解决这个问题。8皇后问题中，我们一行一行地放置皇后，对于一行中的每个位置，可能遇到3种冲突而不能放置。
- 列冲突， 这一列已经放置过皇后
- 右上对角线冲突，当前位置向右上的对角线位置上已经放过皇后
- 左上对角线冲突，当前位置向左上的对角线位置上已经放过皇后
我们可以用三个八位二进制数来表示三种冲突，分别记为A，B，C。有了一行的状态量之后我们可以很容易地通过D=~(A|B|C)来判断出那些位置是可行的，而状态的更新则分别对应置位和左右移位。
class Solution_EightQueens{
int cnt;
int helper(unsigned char A, unsigned char B, unsigned char C){
if (A ^ 0xff == 0){ //A全为1，放完了所有皇后
cnt += 1;
return;
}
unsigned char D = ~(A|B|C); //可行位置
while (D){
unsigned char mask = D & (-D);
D ^= mask;
helper(A|mask, (B|mask)>>1, (C|mask)<<1);
}
}
public:
int EightQueens(){
cnt = 0;
helper(0, 0, 0);
return cnt;
}
};
另外位操作还有很多应用，比如加解密，错误检测和恢复，数据压缩等，之前看到的一道Google的面试题：十个人排成一列，每人头上有一定帽子，帽子颜色位红色或者黑色。后面的人能看到前面所有人帽子的颜色，但看不到后面的和自己的。要他们每个人都开口报一个颜色，问用什么策略可以保证说出的颜色恰好是自己头上帽子的颜色的人数最多。比如一个简单策略，10号报9号帽子的颜色，9跟着10号报，8号报7号帽子的颜色，7号跟着8号报，依次类推，这样可以保证至少有5个人说对。
对于帽子的颜色只有两种，显然是用二进制表示，0表示黑色，1表示红色。然后使用策略就是奇偶校验，最后一个人当作校验位，假设使用奇校验。例子：假设第十位看到从第一位到第9位的帽子颜色为：101001110。则根据奇校验规则，第十位报的颜色为：
1^0^1^0^0^1^1^1^0^[1] = 0 # [1]是奇校验规则，保证1个数位奇数个
第9个人根据自己看到的前8个人和校验位报的颜色，可以准确算出自己的颜色。前面1个数为奇数个，校验位报的为0,因此自己这一位为0。然后8号根据校验位和九号位报的算出自己的颜色，依次类推。
使用这样的策略最终能够保证至少报对9个，校验位帽子的颜色和校验数值一致的话可以报对十个。
另外之前在Google kick start Round G中也遇到了的一道位操作的题目，题目大意是：
一个数组A中有N个非负整数，给定一个值M,求找出满足下式 $(A_1 xor k) + (A_2 xor k) + … + (A_N xor k) \le M$ (1) 的k的最大值，不存在这样的k的话返回-1。 其中:$1 \le N \le 1000$ 小测试集合$0 \le M<=100$， $0 \le A_i \le 100$ 大测试集合$0\le M \le 10^{15}$，$0\le A_i \le 10^{15}$
刚看到这题的想法是枚举，对于小数据集，k的最大值是127，因为Ai和M的最大值为100，如果k>=128,则Ai xor k >= 128 > M，因此k的最大值是127，所以可以枚举，但是对于大数据集。因为k<2**50，不可能在有限时间内枚举，时间复杂度太高了，需要优化。
注意到，k的每一位影响A中每个元素的对应位（回忆xor的作用），可以利用这一性质分别计算k的每一位。使用数组ones[i]表示数组A中第i位取值为1的元素个数，。对应的zeros[i]表示数组中第i位值为0的元素个数，i的取值范围[0, 50)。这样前面不等式(1)的左半部分可以变成：
\(\sum_{j=1}^{N}(A_j xor k) = \sum_{i:k的第i为1} 2^i * zeros[i] + \sum_{i:k的第i位为0} 2^i * ones[i]\)
有了上面的表示，我们可以通过如下设置来使上述总和变小。
if ones[i] >= zeros[i]:
k的第i位 := 1
else:
k的第i位 := 0
定义f[j] 表示对所有i属于[0,j]内上述和的最小值（即上述和只算到第j位），那么如果有 f[50] > M 的话，显然k不存在，返回-1。
接下来可以从高位到第位开始，分别考察每一位，如果把这一位设为1的话，是否满足(1),如果满足则可以设为1，否则置0。最后得到的就是结果。这里总和的计算可以用截止到当前位的部分和sums和当前为置1的和zeros[i](* (1<<i))已经右边部分最小值f[i-1]。
class Solution:
@staticmethod
def solve(N, M, A):
ones = [0] * BITS
zeros = [0] * BITS
for x in A:
for shift in range(BITS):
# 这里为了方便直接乘上了 2 ** shift。
ones[shift] += ((x >> shift) & 1) * (1 << shift)
zeros[shift] += (1 - (x >> shift) & 1) * (1 << shift)
f = [0] * (BITS + 1)
# 先算出集合f
for i in range(BITS):
f[i] = min(ones[i], zeros[i])
for i in range(BITS):
f[i + 1] += f[i]
# 最小情况下也超过了M, 显然没有解。
if f[50] > M:
return -1
k = sums = 0
for i in range(BITS - 1, -1, -1):
front = f[i - 1] if i > 0 else 0
# 如果把这一位置1，加上右边的最小值小于等于M, 满足
if sums + zeros[i] + front <= M:
k |= (1 << i)
sums += zeros[i]
else: # 大于M的话，这一位不能置一
sums += ones[i]
return k
位操作非常灵活，比如上面同一个效果有不同的实现方法，复杂的位操作算法题思路非常的难想，必须对数据的二进制表示以及位操作（尤其是xor，这个考的特别多)有足够的理解和灵活的运用能力，多做题，多总结~