位运算

左移: 在二进制表示下把数字同时向左移动，高位越界舍弃，低位补 0
算术右移: 在二进制补码表示下把数字同时向右移动，高位以符号补充，低位越界舍弃
逻辑右移: 在二进制补码表示下把数字同时向右移动，高位以 0 补充，低位越界舍弃
与: 二进制表示下两位同时为 1 则为 1，否则为 0
或: 二进制表示下只要有一位为 1 则为 1，否则为 0
异或: 二进制表示下相应位不同则为 1，否则为 0

常用操作：

(1)  求$x$的第$k$位数字 x>>k&1

(2)  lowbit(x) = x & -x，返回$x$的最后一位1

1. 判断一个整数是否为偶数

bool isEven (int n) {
    return (n & 1) == 0;
}

// 下面的代码用来判断一个整数是否为奇数
bool isOdd (int n) {
    return (n & 1) == 1;
}

应用：统计一个int型数组中偶数的和：

int sumOfEven(int[] array) {
    int sum = 0;
    for (int num : array)
        sum += num * (num & 1 ^ 1);
    return sum;
}

2. 交换两个整数：

int a = 6;
int b = 1;
a ^= b;
b ^= a;
a ^= b;

3. 求一个整数的绝对值：

int i = a >> 31;
int abs = i == 0 ? a : (~a + 1));

4. 变换符号：

int a = 45;
int b = -9;
std::cout(~a + 1);
std::cout(~b + 1);

5. 求两数平均值：

(x & y) + ((x ^ y) >> 1);

6. 取余运算：

对于 a % b，当b为2的n次方的时候，a % b 等价于 a & (b - 1)。

7. 取int型变量的第k位：

a >> (k - 1) & 1;

运算顺序为先右移 k - 1位，再与1。

8：取末k位：

a & ((1 << k) - 1);

总结

    功能                    示例                    位运算
去掉最后一位          (101101 -> 10110)             x >> 1
在最后加一个0         (101101 -> 1011010)           x << 1
在最后加一个1         (101101 -> 1011011)           x << 1 + 1
把最后一位变成1       (101100 -> 101101)            x | 1
把最后一位变成0       (101101 -> 101100)            x | 1 - 1
最后一位取反          (101101 -> 101100)            x ^ 1
把右数第k位变成1      (101001 -> 101101,k=3)        x | (1 << (k - 1))
把右数第k位变成0      (101101 -> 101001,k=3)        x & ~ (1 << (k - 1))
右数第k位取反         (101001 -> 101101,k=3)        x ^ (1 << (k - 1))
取末三位              (1101101 -> 101)              x & 7
取末k位               (1101101 -> 1101,k = 5)       x & ((1 << k)-1)
取右数第k位           (1101101 -> 1,k = 4)          x >> (k-1) & 1
把末k位变成1          (101001 -> 101111,k = 4)      x | (1 << k-1)
末k位取反             (101001 -> 100110,k = 4)      x ^ (1 << k-1)
把右边连续的1变成0    (100101111 -> 100100000)      x & (x + 1)
把右起第一个0变成1    (100101111 -> 100111111)      x | (x + 1)
把右边连续的0变成1    (11011000 -> 11011111)        x | (x - 1)
取右边连续的1         (100101111 -> 1111)           (x ^ (x + 1)) >> 1
去掉右起第一个1的左边 (100101000 -> 1000)           x & (x ^ (x - 1))
判断奇数              (x & 1) == 1
判断偶数              (x & 1) == 0

状态压缩

取出整数n在二进制表示下的第k位: (n >> k) & 1
取出整数n在二进制表示下的第0 ~ k-1位(后k位): n & ((1 << k) - 1)
把整数n在二进制表示下的第k位取反: n ^ (1 << k)
对整数n在二进制表示下的第k位赋值为1: n | (1 << k)
对整数n在二进制表示下的第k位复制为0: n & (~(1 << k))