位运算作为计算机最底层的操作之一，其高效性源于直接对整数的二进制表示进行操作。在C++编程中，巧妙运用位运算往往能显著提升算法性能、简化代码逻辑，特别是在处理集合操作、状态压缩和性能敏感场景时表现突出。

我一直觉得位运算是个很有意思的话题。它连接了高级算法思维与计算机底层实现，掌握这些技巧不仅能够编写出更高效的代码，更能深化对计算机系统工作原理的理解。今天就来聊聊位运算的一些实用技巧。

位运算的基础原理与核心操作

位运算直接操作整数的二进制位，每个操作都有其特定的数学含义。这些操作之所以高效，是因为它们通常被编译为单条机器指令，直接在CPU的寄存器级别完成运算。

先来看看几个基础操作：

**按位与(&)**：两个位都为1时结果才为1，常用于掩码操作。比如判断一个数的奇偶性，用n & 1就能直接获取最低位。

**按位或(|)**：两个位中有一个为1时结果就为1，常用于设置特定位。在状态压缩中，我们可以用set |= (1 << i)来添加元素。

**按位异或(^)**：两个位不同时结果为1，相同则为0，具有”开关切换”特性。这个特性很有意思，后面会看到它的妙用。

**按位取反(~)**：将所有位取反，0变1，1变0。配合其他操作使用，比如删除集合中的元素可以用set &= ~(1 << i)。

**左移(<<)**：将所有位向左移动，右侧补0，相当于乘以2的幂。n << k就是n * 2^k，但效率更高。

**右移(>>)**：将所有位向右移动，左侧补符号位（算术右移）或0（逻辑右移），相当于除以2的幂。n >> k就是n / 2^k。

数值属性的快速判断技巧

利用位运算可以在常数时间内完成某些数学属性的判断，这比传统的数学运算要快得多。

奇偶性检测

判断一个数是奇数还是偶数，最直接的方法是n % 2 == 0。但用位运算会更高效：

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

这个方法的原理很简单：任何整数的二进制表示中，最低位决定了它的奇偶性。通过与操作n & 1，我们能够直接访问最低位，无需进行耗时的模运算。这种方法的效率优势在循环遍历或频繁判断的场景中尤为明显。

2的幂次方判断

判断一个数是否是2的幂次方，有个很巧妙的技巧：

1
2
3
bool isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

这个表达式利用了2的幂次方的数学性质：对于2的幂，其二进制表示有且仅有一个1。当n为2的幂时，n-1会将那个唯一的1及其后的所有位翻转，使得按位与的结果为0。

举个例子，8的二进制是1000，7的二进制是0111，两者相与结果为0000。而6的二进制是0110，5的二进制是0101，相与结果为0100，不为0。

高效位操作技巧集锦

最低位1的提取（lowbit操作）

这是许多高级算法的基础，比如树状数组（Fenwick Tree）：

1
2
3
int lowbit(int n) {
    return n & (-n);
}

这个操作利用了补码表示中负数的特性：负数是原数按位取反再加1。表达式n & (-n)能够快速分离出最低位的1及其后面的0。

比如12的二进制是1100，-12的二进制是0100（在补码表示中），两者相与得到0100，正好是最低位的1。

1的个数统计

统计一个数二进制表示中1的个数，有个很经典的算法叫Brian Kernighan算法：

1
2
3
4
5
6
7
8
int countOnes(int n) {
    int count = 0;
    while (n) {
        n &= (n - 1);  // 移除最低位的1
        count++;
    }
    return count;
}

n &= (n - 1)操作能够巧妙地移除最低位的1。重复此操作直到n变为0，操作次数即为原数中1的个数。这种方法的时间复杂度与1的个数成正比，在稀疏二进制数中特别高效。

无临时变量的交换

这个技巧体现了异或运算的自反性质：

1
2
3
4
5
void swap(int& a, int& b) {
    a ^= b;
    b ^= a;
    a ^= b;
}

通过三次异或操作，可以在不使用额外内存的情况下交换两个变量。虽然现代编译器的优化可能减少了这种技巧的实际必要性，但它仍然是理解位运算特性的绝佳示例。

原理很简单：a ^ b的结果包含了a和b的所有差异信息。第一次异或后，a变成了a ^ b；第二次异或后，b变成了b ^ (a ^ b) = a；第三次异或后，a变成了(a ^ b) ^ a = b。

状态压缩与集合操作

位运算在状态压缩领域展现出巨大威力。使用整数作为位掩码，可以将一个大小为n的布尔数组压缩到n个比特中，不仅节省空间，而且集合操作可以直接转换为位运算，效率极高。

集合的位表示法

我们可以用一个整数来表示一个集合，每一位代表一个元素是否存在：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int set = 0;  // 空集合

// 添加元素i
set |= (1 << i);

// 删除元素i
set &= ~(1 << i);

// 判断元素i是否在集合中
bool contains = (set >> i) & 1;

// 集合的交、并、差运算
int intersection = set1 & set2;
int union_set = set1 | set2;
int difference = set1 & ~set2;

这种表示法不仅节省空间，而且集合的交、并、差运算可以直接转换为&、|、& ~操作，效率极高。

子集遍历技巧

枚举一个集合的所有子集，有个很高效的技巧：

1
2
3
4
5
6
7
int set = 0b1011;  // 假设有4个元素，当前集合是{0, 1, 3}
int subset = set;
do {
    // 处理当前子集subset
    // ...
    subset = (subset - 1) & set;
} while (subset != set);

通过subset = (subset - 1) & set循环，可以无重复地遍历集合的所有子集。这个技巧在状态空间搜索、动态规划等算法中应用广泛，将指数级问题的实现变得简洁高效。

算术运算的位级优化

位运算可以实现某些算术运算的替代方案，有时能获得更好的性能。

2的幂次乘除

这是位运算最常见的优化场景：

1
2
3
4
5
6
7
int multiplyByPowerOfTwo(int n, int k) {
    return n << k;  // n * 2^k
}

int divideByPowerOfTwo(int n, int k) {
    return n >> k;  // n / 2^k
}

这些操作不仅避免了乘除法指令的开销，而且意图更明确，代码更简洁。不过需要注意的是，右移对于负数来说是算术右移，结果可能和预期不同。

平均值计算的位运算方法

计算两个数的平均值，有个巧妙的位运算方法可以避免整数溢出：

1
2
3
int average(int a, int b) {
    return (a & b) + ((a ^ b) >> 1);
}

这个方法巧妙地避免了整数溢出的风险。前半部分a & b提取了需要进位的位置，后半部分(a ^ b) >> 1计算了不需要进位的部分除以2。这种方法的正确性基于二进制加法的进位原理。

异或运算的巧妙应用

异或运算有几个很有意思的性质，在LeetCode中经常用到。

找唯一数字

当数组中只有一个数字出现一次，其他数字都出现两次时，可以用异或快速找出这个唯一数字：

1
2
3
4
5
6
7
int findSingle(vector<int>& nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;
    }
    return result;
}

原理很简单：异或满足交换律和结合律，而且a ^ a = 0，a ^ 0 = a。所以所有出现两次的数字异或后都变成0，最后剩下的就是那个唯一出现一次的数字。

这个技巧在LeetCode中非常经典，是很多位运算题目的基础。

条件交换

有时候我们需要根据条件交换两个变量的值，用异或可以写得很简洁：

1
2
3
4
// 如果x等于a，则x变为b；如果x等于b，则x变为a
void conditionalSwap(int& x, int a, int b) {
    x = a ^ b ^ x;
}

这个技巧利用了异或的自反性质。当x == a时，a ^ b ^ a = b；当x == b时，a ^ b ^ b = a。在某些特定场景下，这种写法比if-else更简洁。

更多实用的位操作技巧

提取最高位的1

有时候我们需要找到最高位的1，这在某些算法中很有用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int highestBit(int n) {
    // 方法1：不断右移直到为0
    int pos = 0;
    while (n) {
        n >>= 1;
        pos++;
    }
    return pos - 1;
    
    // 方法2：使用位运算技巧（需要知道位数）
    // 假设是32位整数
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return (n + 1) >> 1;
}

第二种方法通过不断将最高位的1向右”扩散”，最终得到一个只有最高位为1的数，然后再右移一位加1，就能得到最高位的值。这个方法在常数时间内完成，但需要知道整数的位数。

位掩码的翻转操作

除了设置和清除，翻转操作也很有用：

1
2
3
4
5
6
7
8
9
10
11
12
13
int mask = 1 << i;  // 第i位的掩码

// 翻转第i位：原来是0变成1，原来是1变成0
n ^= mask;

// 判断第i位是否为1
bool isSet = (n & mask) != 0;

// 将第i位设置为1
n |= mask;

// 将第i位清除为0
n &= ~mask;

翻转操作在状态切换、权限管理、游戏状态等场景中经常用到。比如一个开关，每次操作都要翻转状态，用异或就非常方便。

n倍数补全（向上取整到2的幂）

有时候我们需要将一个数向上取整到最近的2的幂次方：

1
2
3
4
5
6
7
8
9
10
int roundUpToPowerOfTwo(int n) {
    if (n <= 0) return 1;
    n--;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return n + 1;
}

这个技巧和提取最高位的方法类似，通过”扩散”操作将所有低位都设置为1，然后加1就能得到大于等于原数的最小2的幂。这在内存对齐、哈希表大小设置等场景中很有用。

反转二进制位

有时候我们需要反转一个整数的所有二进制位：

1
2
3
4
5
6
7
8
uint32_t reverseBits(uint32_t n) {
    n = ((n & 0x55555555) << 1) | ((n & 0xAAAAAAAA) >> 1);  // 交换相邻的1位
    n = ((n & 0x33333333) << 2) | ((n & 0xCCCCCCCC) >> 2);  // 交换相邻的2位
    n = ((n & 0x0F0F0F0F) << 4) | ((n & 0xF0F0F0F0) >> 4);  // 交换相邻的4位
    n = ((n & 0x00FF00FF) << 8) | ((n & 0xFF00FF00) >> 8);  // 交换相邻的8位
    n = ((n & 0x0000FFFF) << 16) | ((n & 0xFFFF0000) >> 16); // 交换相邻的16位
    return n;
}

这个方法采用了分治的思想，从交换相邻的1位开始，逐步扩大交换范围，最终完成整个32位的反转。虽然看起来复杂，但每一步都是简单的位操作，效率很高。

分治法统计1的个数

除了Brian Kernighan算法，还有一种分治的方法在某些场景下更高效：

1
2
3
4
5
6
7
8
int countOnes(uint32_t n) {
    n = (n & 0x55555555) + ((n >> 1) & 0x55555555);  // 每2位统计1的个数
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333);  // 每4位统计1的个数
    n = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F);  // 每8位统计1的个数
    n = (n & 0x00FF00FF) + ((n >> 8) & 0x00FF00FF);  // 每16位统计1的个数
    n = (n & 0x0000FFFF) + ((n >> 16) & 0x0000FFFF); // 每32位统计1的个数
    return n;
}

这个方法通过分治的思想，将统计1的个数的问题逐步分解。每一步都将相邻的位组合起来，统计它们的1的个数之和。最终得到整个32位数中1的总数。这种方法虽然代码看起来复杂，但在某些CPU架构上可能比循环方法更快。

总结

位运算的这些技巧就像小甜品，这些技巧在位运算题目中经常出现，不过也要注意，虽然位运算很高效，但在普通业务逻辑中过度使用可能会损害代码的可读性。毕竟，代码是写给人看的，偶尔才是给机器执行的。这些”小甜品”虽然不能当主食，但偶尔尝一尝，还是挺有意思。

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

快来参与讨论吧~