位运算技巧和实例

概述

• 在计算机中所有数据都是以二进制的形式储存的。位运算其实就是直接对在内存中的二进制数据进行操作，因此处理数据的速度非常快。
• 位操作只能用于整形数据，对float和double类型进行位操作会被编译器报错。

符号	作用
&	与
|	或
~	非
^	异或
<<	左移：高位丢弃，低位补0
>>	右移：对无符号数，高位补0

入门技巧

1. 判断奇偶 i & 1
   若i为奇，则为1；10101 & 00001 = 00001
   若i为偶，则为0；10110 & 00001 = 00000

2. 交换变量 a ^= b；b ^= a；a ^= b；

3. 变号 ~a + 1

4. 绝对值

a = 10 或者 -50
i = a >> 31
a = (a ^ i) - i

5. 设置第n位
   设为1：y = x | (1<<n)
   设为0：y = x & ~(1<<n)
   取反：y = x ^ (1<<n)

简单技巧

1. 高低位互换：a = (a >> 8) | (a << 8)
2. 二进制逆序：使用归并排序 和 1中的技巧
3. 将最右边的1的设为0：y = x & (x-1)
4. 统计二进制中1的个数，利用3的技巧：

count = 0
while n:
    count += 1
    n = n & (n - 1)

系列问题：在数组里面找只出现一次的数字

1. 在其他数字都出现2次的数组里面找到唯一只出现1次的数
   思路：全部异或一次，相同的会抵消，最后剩下的就是ans

a = [1,2,2,1,3,5,5]
ans = 0
for i in a:
    ans ^= i

2. 在其他数字都出现2次的数组里面找到唯二只出现1次的数
   思路：全部异或，最后剩下的是ans = ans1 ^ ans2，找到ans第一个1，即代表ans1和ans2在该位肯定不同，一个取0，一个取1。把数组依据这一位是0还是1分为两个数组就能将ans1和ans2分开，再对两个数组分别进行异或即可得到ans1和ans2。

array = [1, 1, 2, 2, 5, 3]
ans = 0
for i in array:
    ans ^= i
position = 0
while ans:
    if (ans >> position)&1:
        break
    position+=1
ans1,ans2 = 0,0
for i in array:
    if (i >> position)&1:
        ans1 ^= i
    else:
        ans2 ^= i
print(ans1,ans2)

3. 在其他数字都出现次的数组里面找到唯一只出现1次的数

# 法1：对正数有效
array = [2,2,2,5,5,5,4,4,4,10]
counts = [0]*32
for num in array:
    i = 0
    while num>>i:
        counts[i]+=(num>>i)&1
        i+=1
ans = 0
for i,count in enumerate(counts):
    if count % 3 != 0 :
        ans += (1 << i)
print(ans)

# 法2：皆有效
ones , twos = 0 , 0
for i in array:
    ones = ones ^ i & ~twos
    twos = twos ^ i & ~ones
print(ones)

不使用加减乘除运算符计算

1. 加法

def add_bit(a,b):
    x,y = a^b,(a & b) << 1
    while y:
        x,y = x^y,(x & y) << 1
    return x

2. 乘法

def mul_bit(a,b):
    ans = 0
    while b:
        if b & 1:
            ans = add_bit(ans,a)
        a<<=1
        b>>=1
    return ans

参考

• 位操作基础篇之位操作全面总结
• 我是楼下的翻译和提取
• bit twiddling hacks 英语原文