Bits
Date: . Last updated: .
位操作
x & (x – 1) // 最右边1清0
x = A 1 0 0 0 ... 0
x - 1 = A 0 1 1 1 ... 1
--------------------------------
结果 = A 0 0 0 0 ... 0
常见用途：
- 判断一个数是不是 2 的幂：x > 0 && (x & (x-1)) == 0
- 统计一个数二进制中有几个 1（Brian Kernighan 算法）：while(x){ count++; x &= (x-1); }
- 枚举子集时去掉一个元素（lowbit 相关技巧）
- 字符串查找 / KMP / BM 算法优化中也有类似思想（快速跳过某些状态）
if (x > 0 && (x & (x-1)) == 0) {
// x是2的幂（如1,2,4,8,16...）
}
处理“最低位 1”的一组
| 表达式 | 作用 | 本质 |
| ------------------| -----------------| ------------|
| x & (x - 1) | 最低位1置0 | 借位消除 |
| x & (x + 1) | 低位连续1清0 | |
| x & -x | 提取最低位 1 | 补码定位 |
处理“最低位 0”的一组
| 表达式 | 作用 | 本质 | |
| -------------------- | -------------- | ---------- | ---- |
| x | (x + 1) | 最低位0置1 | | |
| x | (x – 1) | 低位连续0置1 | | |
| 操作 | 写法 | 含义 | |
| --- | ---------------- | ----------- | --------- |
| 置 1 | n |= (1 << x)| 把第 x 位置 1 ||
| 置 0 | n &= ~(1 << x) | 把第 x 位清 0 | |
| 翻转 | n ^= (1 << x) | 把第 x 位取反 | |
一个数是2n的倍数 ⇨ 二进制最低 n 位必须全为 0
x & 1 == 0 2的倍数？(判断奇偶)
x & 3 == 0 4的倍数？
x & 7 == 0 8的倍数？
x & 15 == 0 16的倍数？
x & 31 == 0 32的倍数？
x & 63 == 0 64的倍数？
x & (2^n - 1) == 0 2^n的倍数？
1010 10 1101 13
& 0001 & 0001
-------- -----------
0 偶 1 奇
16 = 2⁴ 最后 4 位是 0 → 十六进制最后一位是 0
0x10 0x20
32 = 2⁵ 最后 5 位是 0 → 十六进制最后一位必须0,倒数第二位必须是 偶数(0,2,4,6,8,A,C,E)
0x00 = 0000 0000
0x20 = 0010 0000
0x40 = 0100 0000
0x80 = 1000 0000
0xA0 = 1010 0000
0xC0 = 1100 0000
0xE0 = 1110 0000
64 = 2⁶ 最后 6 位是 0 → 十六进制最后一位必须0,倒数第二位必须是4的倍数(0,4,8,C)
0x00 = 0000 0000
0x40 = 0100 0000
0x80 = 1000 0000
0xC0 = 1100 0000
一个数是2n 快速转换为十六进制 ==> 把 n 写成：n = 4×k + r （k 是商，r 是余数 0~3） $$2^{n} = 1\underbrace{ 0000'0000\cdots0000'0000}_{n\text{ 位} (n = 4×k + r )} = 0x2^{r}\underbrace{ 0\cdots0}_{k\text{位}}$$
24 = 24x1 + 0 = 0x200 = 0x10
210 = 24x2 + 2 = 0x2200 = 0x400