7.1 Bit Manipulation
优质
小牛编辑
130浏览
2023-12-01
位操作有按位与、或、非、左移n位和右移n位等操作。
XOR - 异或
异或：相同为0，不同为1。也可用「不进位加法」来理解。
异或操作的一些特点：
x ^ 0 = x
x ^ 1s = ~x // 1s = ~0
x ^ (~x) = 1s
x ^ x = 0 // interesting and important!
a ^ b = c => a ^ c = b, b ^ c = a // swap
a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c // associative
移位操作
移位操作可近似为乘以/除以2的幂。0b0010 * 0b0110等价于0b0110 << 2. 下面是一些常见的移位组合操作。从低位向高位看过去，个位为1，那么有：
- 将
x最右边的n位清零 -x & (~0 << n) - 获取
x的第n位值(0或者1) -(x >> n) & 1 - 获取
x的第n位的幂值 -x & (1 << (n - 1)) - 仅将第
n位置为1-x | (1 << n) - 仅将第
n位置为0-x & (~(1 << n)) - 将
x最高位至第n位(含)清零 -x & ((1 << n) - 1) - 将第
n位至第0位(含)清零 -x & (~((1 << (n + 1)) - 1)) - 仅更新第
n位，写入值为v;v为1则更新为1，否则为0 -mask = ~(1 << n); x = (x & mask) | (v << i)
Reference
- 位运算应用技巧（1） » NoAlGo博客
- 位运算应用技巧（2） » NoAlGo博客
- 位运算简介及实用技巧（一）：基础篇 | Matrix67: The Aha Moments
- cc150 chapter 8.5 and chapter 9.5
- 《编程珠玑2》
- 《Elementary Algorithms》 Larry LIU Xinyu