前置内容
运算符优先级
在实现位运算时，需要注意位运算的运算优先级，对于不确定的优先级，建议加括号保证运算顺序的正确性，运算符的优先级从高到低顺序如下表所示：
| 加减 | 移位 | 比较 | 位与 | 异或 | 位或 |
|---|---|---|---|---|---|
| + - | << >> | > < == != | & | ^ | | |
位运算
概念
位运算是直接对整数在二进制形式下进行的逐位运算。
运算符号
| 运算符 | 名称 | 规则 |
|---|---|---|
& | 与（AND） | 两位均为 1 时结果为 1，否则为 0 |
| ` | ` | |
^ | 异或（XOR） | 两位不同为 1，相同为 0 |
~ | 取反（NOT） | 0 变 1，1 变 0 |
<< | 左移（Shift Left） | 二进制数整体左移，低位补 0 |
>> | 右移（Shift Right） | 二进制数整体右移，高位补符号位（算术右移）或 0（逻辑右移） |
前面四个运算符号的规则较为简单，我们着重讲左移和右移。
性质
左移（<<）
规则：所有位向左移动，低位补 0 数学意义：x << n 等价于 x * 2ⁿ
右移（>>）
规则：所有位向右移动，高位补符号位（正数补 0，负数补 1）
数学意义：x >> n 等价于 x / 2ⁿ（向下取整）
常用技巧
| 取出整数n在二进制表示下的第k位 | (n >> k) & 1 |
|---|---|
| 取出整数n在二进制表示下的第0~ k -1位 | n & ((1 << k)-1) |
| 把整数n在二进制表示下的第k位取反 | n xor (1 << k) |
| 对整数n在二进制表示下的第k位赋值1 | n｜(1 << k) |
| 对整数n在二进制表示下的第k位赋值0 | n &( ~ (1 << k ) ) |