常见位运算技巧与实战总结
在算法竞赛和底层开发中,位运算往往能带来意想不到的性能提升。它直接操作内存中的比特位,常用于状态压缩、奇偶判断等场景。下面梳理一下核心用法及组合技巧。
基础运算符
左移运算符 <<
用来将一个数的各二进制位全部左移若干位,移动的位数由右操作数指定。右边空出的位用 0 填补,高位溢出则舍弃。
示例:5 << 2 就是将 5 的二进制 101 左移两位变成 10100,也就是 20。相当于乘以 4。
右移运算符 >>
将一个二进制位的操作数按指定移动的位数向右移动,移出位被丢弃。左边移出的空位根据符号位补 0 或补符号位(算术右移)。
示例:5 >> 2 就是将 5 的二进制 101 右移两位变成 001,也就是 1。相当于除以 4 取整。
取反运算符 ~
将一个数的二进制表达的每一位取反,即 0 变为 1,1 变为 0。注意在补码表示下,~x 等于 -x - 1。
按位与运算符 &
参与运算的两数各对应的二进位相与。只有对应的两个二进位都为 1 时,结果位才为 1。
示例:1 & 2,即 001 & 010,最后结果为 000。常用于清零或保留特定位。
按位或运算符 |
参与运算的两数各对应的二进位相或。只要对应的二个二进位有一个为 1 时,结果位就为 1。
示例:1 | 2,即 001 | 010,最后结果为 011。常用于置位。
按位异或运算符 ^
用于对两个二进制数的每一位进行异或运算。如果参与运算的两个位中只有一个为 1,则结果位为 1;如果两个位都为 0 或都为 1,则结果位为 0。
示例:1 ^ 2,即 001 ^ 010,最后结果为 011。
注意:按位异或的运算结果与无进位相加后的结果相同,且具有交换律和结合律。
常用组合技巧
掌握了基础运算符后,我们可以通过组合来实现一些非常实用的功能。
1. 获取第 x 位
给定一个数 n,确定它的二进制表示中的第 x 位是 0 还是 1。
int bit = (n >> x) & 1;
将 n 右移 x 位,使目标位落到低位,再与 1 做与运算即可提取。
2. 设置第 x 位为 1
将一个数 n 的二进制表示的第 x 位修改成 1。
n |= (1 << x);
构造一个只有第 x 位为 1 的掩码,然后与原数做或运算。
3. 清除第 x 位为 0
将一个数 n 的二进制表示的第 x 位修改成 0。
n &= ~(1 << x);


