下面的第k位是从0开始计数的。
| 位运算 | 解释 |
|---|---|
lowbit(i) 即i & -i |
返回i的最后一位1以及后面的0 |
(n >> k) & 1 |
求n的第k位数字 |
x | (1 << k) |
将x第k位置为1 |
x & ~(1 << k) |
将x第k位置为0 |
x ^ (1 << k) |
将x第k位取反 |
x & (x - 1) |
将x最右边的1置为0 (去掉最右边的1) |
x | (x + 1) |
将x最右边的0置为1 |
x & 1 |
取x的最后一位。用于判断x的奇偶性：1为奇，0为偶 |
(n > 0) && ((n & (n - 1)) == 0) |
判断n是否为2的幂。因为2的幂的二进制只有一个1，用n & (n-1)可以直接把它唯一的1去掉变成0。 |
n & ((1 << k) - 1) |
等价于 n % (1 << k)，即n对$2^k$取模 |
a ^= b; b ^= a; a ^= b; |
交换a和b的值 |
~n |
对n按位取反，结果为-n-1 |
统计二进制数中1的个数：
1int countOnes(int n) {
2 int count = 0;
3 while (n) {
4 n &= (n - 1); // 即 n = n & (n - 1)
5 count++;
6 }
7 return count;
8}