Bit Twiddling Hacks

位运算就是基于整数的二进制表示进行的运算。由于计算机内部就是以二进制来存储数据，位运算是相当快的。

运算符

基本的位运算共 6 种，分别为按位与、按位或、按位异或、按位取反、左移和右移。

运算 运算符 解释
与 & 只有两个对应位都为 1 时才为 1
或 | 只要两个对应位中有一个 1 时就为 1
异或 ^ 只有两个对应位不同时才为
取反 ~ 0变1, 1变0
左移 << 各二进位全部左移若干位，高位丢弃，低位补0
右移 >> 各二进位全部右移若干位，对于无符号数，高位补0; 有符号数，有的补符号位

按位与 &

相同位的两个数字都为1，则为1；若有一个不为1，则为0。

示例：6&11

1
2
3
4
 6    0 1 1 0
 11   1 0 1 1
&-----------
      0 0 1 0 = 2

and运算通常用于二进制的取位操作。

小技巧：一个数 & 1的结果就是取二进制的最末位。这可以用来判断一个整数的奇偶，二进制的最末位为0表示该数为偶数，最末位为1表示该数为奇数。

按位或 |

相同位只要一个为1即为1

示例：6 | 11

1
2
3
4
    0 1 1 0
    1 0 1 1
| ----------- 
    1 1 1 1 = 15

or运算通常用于二进制特定位上的无条件赋值。
小技巧：一个数or 1的结果就是把二进制最末位强行变成1。如果需要把二进制最末位变成0，对这个数or 1之后再减一就可以了，其实际意义就是把这个数强行变成最接近的偶数。

按位异或 ^

两个位相同为0，相异为1

示例：6 ^ 11

1
2
3
4
    0 1 1 0
    1 0 1 1
^ -----------
    1 1 0 1 = 13

^运算通常用于翻转指定位。
小技巧：将数 X=1010 1110 的低4位进行翻转，只需要另找一个数Y，令Y的低4位为1，其余位为0，即Y=0000 1111，然后将X与Y进行异或运算（X^Y=1010 0001）即可得到。

按位取反

not运算的定义是把内存中的0和1全部取反。

示例：~ 6

使用按位取反运算符，要知道几点：
1、内存中，一个int，4个字节，1字节8位。
2、有符号整数的按位取反情况略有偏差。

1
2
3
    00000000 00000000 00000000 00000110
~ --------------------------
    11111111 11111111 11111111 11111001

小技巧：可以用~使每个数的最低位为0，方法：a & ~1

左移位运算符 <<

将一个运算对象的各二进制位全部左移若干位（左边的二进制位丢弃，右边补0）。

示例：6 << 2

1
2
3
        0 1 1 0
<<2 ------------
    0 1 1 0 0 0 = 24

小技巧：若左移时舍弃的高位不包含1，则每左移一位，相当于该数乘以2。

右移位运算符 >>

将一个数的各二进制位全部右移若干位，正数左补0，负数左补1，右边丢弃。

示例： 6 >> 2

1
2
3
        0 1 1 0
>>2 -------------
        0 0 0 1 = 1

小技巧：操作数每右移一位，相当于该数除以2。

负数的二进制表示

用字节的最高位表示:”1”表示”正”,”0”表示”负”

1、把补码“取反”（把二进制数的各位“1”换“0”，“0”换“1”。比如“101010”取反后为“010101”）
2、把取反后的二进制数“+1”

示例：-17 转码

1
2
3
17:     00000000 00000000 00000000 00010001
反码:    11111111 11111111 11111111 11101110
转码:    11111111 11111111 11111111 11101111

优先级

Go语言运算符优先级和结合性一览表

优先级 分类 运算符 结合性
1 逗号运算符 , 从左到右
2 赋值运算符 =、+=、-=、*=、/=、 %=、 >=、 <<=、&=、^=、|= 从右到左
3 逻辑或 | 从左到右
4 逻辑与 && 从左到右
5 按位或 | 从左到右
6 按位异或 ^ 从左到右
7 按位与 & 从左到右
8 相等/不等 ==、!= 从左到右
9 关系运算符 <、<=、>、>= 从左到右
10 位移运算符 <<、>> 从左到右
11 加法/减法 +、- 从左到右
12 乘法/除法/取余 *（乘号）、/、% 从左到右
13 单目运算符 !、*（指针）、& 、++、–、+（正号）、-（负号） 从右到左
14 后缀运算符 ( )、[ ]、-> 从左到右

注意：优先级值越大，表示优先级越高。

基本操作

  • x & (- x)：保留二进制下最后出现的1的位置，其余位置置0（即一个数中最大的2的n次幂的因数
  • x & (x - 1)：消除二进制下最后出现1的位置，其余保持不变
  • x & 0 = 0
  • (a ^ b) ^ c == a ^ (b ^ c)
  • a = 0 ^ a = a ^ 0
  • 对于任何数x，都有x ^ x=0，x ^ 0=x
  • 自反性: a ^ b ^ b=a ^ 0=a
  • 移除最后一个 1 ： a = n & (n - 1)
  • 获取最后一个 1： diff = (n & (n - 1)) ^ n， 跟x & (- x) 一样，都是保留二进制下最后出现的1的位置

高端操作

实现swap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//普通操作
void swap(int &a, int &b) {
  a = a + b;
  b = a - b;
  a = a - b;
}

//位与操作
void swap(int &a, int &b) {
  a ^= b;
  b ^= a;
  a ^= b;
}

// a ^= b  -->  a = a^b
// b ^= a  -->  b = b^a^b = a
// a ^= b  -->  a = a^b^a = b

 a = b的时候会出问题

1
2
3
a ^= b  -->  a = a^b = 0
b ^= a  -->  b = b^a^b = a = 0
a ^= b  -->  a = a^b^a = b = 0

快速求数字二进制表示中 1 的个数

1
2
3
4
5
6
// n & (n - 1)：消除最低位的 1 
// Time：O(k) 1的个数，Space:O(1) 
while (n != 0) {  
    count++;
    n &= (n - 1);
}

判断奇偶数

只要根据数的最后一位是 0 还是 1 来决定即可，为 0 就是偶数，为 1 就是奇数。

1
2
3
if(0 == (a & 1)) {
 //偶数
}

判断符号是否相同

1
2
3
bool isSameSign(int x, int y) {  // 有 0 的情况例外
    return (x ^ y) >= 0;
}

一个正数补码的符号位和一个负数补码的符号位肯定相反，经过异或运算后，最后符号位结果肯定是 1(代表负数)。

移除最后一位 1

1
2
3
4
5
6
byte n = 10;
// n的二进制表示为: 0 0 0 0 1 0 1 0
//       异或运算  ^
//n-1的二进制表示为:0 0 0 0 1 0 0 1
n & (n-1);  
// 结果为:         0 0 0 0 1 0 0 0

 n & (n -1 ) 主要作用：消除数字 n 的二进制表示中的最后一个 1

获取最后一个 1

两种方法

1
2
3
4
5
6
(n & (n-1)) ^ n; 
// n & (n-1) 消除二进制下最后出现1的位置，再与n异或，获取最后一个1


n & (-n);
// -n 按位取反+1 再与n按位与，获取最后一个1

Herbert : x & (x- 1) ^x == x & (-x) 这个等式是正确的吗？

ChatGpt:

我们可以分别证明等式的两边，最终证明它们相等。

左边：x & (x-1) ^ x

因为按位异或运算 ^ 的规则是：相同位上的数字不同则为 1，否则为 0，所以 (x-1) ^ x 的结果是把 x 的最低位上的 1 变成 0。因此 x & (x-1) 会把 x 的最低位上的 1 变成 0，其它位不变。也就是说，它把 x 中最低位上的 1 和它右边所有的 0 都清除掉了。这个操作等价于将 x 取整个数的二进制表示中，最低的一位 1 之后的所有位都清零。所以，左边的等式可以看成是：x 取整个数的二进制表示中，最低的一位 1 之后的所有位都清零。

右边：x & (-x)

-x 表示的是 x 的补码的相反数。在计算机中，一个数 x 的补码等于它的反码加 1。反码的规则是，正数的反码就是其原码，负数的反码就是其原码除符号位以外取反。因此-x 的补码就是（x 的原码除符号位以外取反加 1）。因此，-x 和 & 运算的结果是将 x 的值除最低位以外的所有位取反并加 1，最低位不变。也就是说，它把 x 中最低位上的 1 和它右边所有的 0 都清除掉了，其它位不变。这个操作等价于将 x 取整个数的二进制表示中，最低的一位 1 之后的所有位都清零。

因此，左边和右边的值是相等的，等式成立。

交换符号

将正数变成负数，负数变成正数 

1
2
3
int reversal(int a) {
    return ~a + 1;
}

整数取反加1，正好变成其对应的负数(补码表示)；负数取反加一，则变为其原码，即正数5.

求绝对值

整数的绝对值是其本身，负数的绝对值正好可以对其进行取反加一求得，即我们首先判断其符号位（整数右移 31 位得到 0，负数右移 31 位得到 -1,即 0xffffffff），然后根据符号进行相应的操作

1
2
3
4
int abs(int a) {
    int i = a >> 31;
    return i == 0 ? a : (~a + 1);
}

上面的操作可以进行优化，可以将 i == 0 的条件判断语句去掉。我们都知道符号位 i 只有两种情况，即 i = 0 为正，i = -1 为负。对于任何数与 0 异或都会保持不变，与 -1 即 0xffffffff 进行异或就相当于对此数进行取反,因此可以将上面三目元算符转换为((a^i)-i)，即整数时 a 与 0 异或得到本身，再减去 0，负数时与 0xffffffff 异或将 a 进行取反，然后在加上 1，即减去 i(i =-1)

1
2
3
4
int abs2(int a) {
    int i = a >> 31;
    return ((a^i) - i);
}

大小写字母转换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 利用 或操作 和空格将英文字母转成小写

('a' | ' ') = 'a';
('A' | ' ') = 'a'; 

# 利用与运算 & 和下划线将英文字符转换成大写

('b' & '_') = 'B';
('B' & '_') = 'B';

# 利用异或运算 ^ 和空格进行英文字符大小写互换

('d' ^ ' ') = 'D';
('D' ^ ' ') = 'd';

上述技巧能够产生奇特效果的原因在于字符类型的数据都是通过 ASCII 进行编码的，字符本身其实就是数字，而刚好这些字符对应的数字通过位运算符就可以得到正确结果。

用 O(1) 时间检测整数 n 是否是 2 的幂次

N如果是2的幂次，则N满足两个条件。

  1. N >0

  2. N的二进制表示中只有一个1

因为N的二进制表示中只有一个1,所以使用N & (N - 1)将N唯一的一个1消去，应该返回0。

1
2
3
bool isPowerOfTwo(int n) { 
    return n > 0 && (n & (n - 1)) == 0; 
}

对 2 的非负整数次幂取模

1
2
3
int modPowerOfTwo(int x, int mod) { 
    return x & (mod - 1); 
}

表示集合

一个数的二进制表示可以看作是一个集合（0 表示不在集合中，1 表示在集合中）。比如集合 {1, 3, 4, 8} ，可以表示成 ((100011010)_2) 。而对应的位运算也就可以看作是对集合进行的操作。

操作 集合表示 位运算语句
交集 (a \cap b) a & b
并集 (a \cup b) a | b
补集 (\bar{a}) ~a （全集为二进制都是 1）
差集 (a \setminus b) a & (~b)
对称差 (a\triangle b) a ^ b

数组中，只有一个数出现一次，剩下都出现两次，找出出现一次的数

因为只有一个数恰好出现一个，剩下的都出现过两次，所以只要将所有的数异或起来，就可以得到唯一的那个数。（异或自反性）

乘/除 2 的非负整数次幂

1
2
3
4
5
6
7
int mulPowerOfTwo(int n, int m) {  // 计算 n*(2^m)
  return n << m;
} 

int divPowerOfTwo(int n, int m) {  // 计算 n/(2^m)
  return n >> m;
}

warning : 我们平常写的除法是向 0 取整，而这里的右移是向下取整（注意这里的区别），即当数大于等于 0 时两种方法等价，当数小于 0 时会有区别，如： -1 / 2 的值为 0，而 -1 >> 1 的值为 -1 。

总结

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
1
a & a = a
a ^ a = 0

2
a & 0 = 0
a | 0 = a
a ^ 0 = a

3
a | (a & b) = a
a & (a | b) = a

4、交换值
a ^= b;
b ^= a;
a ^= b;

5、判断奇偶(取出最后一位)
a & 1
等价于 a % 2(结果等于,位运算效率高)

6、比较两值是否相等
a ^ b == 0

7、i+1位置1
a |= 1 << i

8、i+1位置0
a &=~(1 << i)

9、取出i+1
位(联系第5点)
a & (1 << i)

10、在对应i+1位，插入b的对应位;
a |= 1 << i; (a的bit位置1)
a & (b & 1 << i) (与b的bit位相与)

11、删除最后的1;
a & (a-1)

12、负数
a = ~a+1

13、仅保留最后一个1
a & (-a)
a & (a - 1)) ^ a

14、得到全1
~0

15、保留最后i-1位
a & ((1 << i) - 1)

16、清零最后i-1位
a & ~((1 << i) - 1)

以上，为最常见的用法，不带循环，全部O(1)。

leetcode example

Leetcode-260-single-number-iii

Leetcode-461-hamming-distance

reference

https://graphics.stanford.edu/~seander/bithacks.html