C++ 位运算高级技巧
位运算基础回顾
在深入探讨C++ 位运算高级技巧之前，我们先来简单回顾一下基础的位运算操作。
按位与（&）
按位与操作符&对两个整数的每一位进行逻辑与操作。只有当两个对应的二进制位都为1时，结果位才为1，否则为0。例如：
#include <iostream>
int main() {
int a = 5; // 二进制: 00000101
int b = 3; // 二进制: 00000011
int result = a & b;
std::cout << "按位与结果: " << result << std::endl;
return 0;
}
在上述代码中，5的二进制是00000101，3的二进制是00000011。按位与操作后，结果为00000001，即十进制的1。
按位或（|）
按位或操作符|对两个整数的每一位进行逻辑或操作。只要两个对应的二进制位中有一个为1，结果位就为1，只有当两个位都为0时，结果位才为0。例如：
#include <iostream>
int main() {
int a = 5; // 二进制: 00000101
int b = 3; // 二进制: 00000011
int result = a | b;
std::cout << "按位或结果: " << result << std::endl;
return 0;
}
这里，5和3按位或操作后，结果为00000111，即十进制的7。
按位异或（^）
按位异或操作符^对两个整数的每一位进行异或操作。当两个对应的二进制位不同时，结果位为1，相同时结果位为0。例如：
#include <iostream>
int main() {
int a = 5; // 二进制: 00000101
int b = 3; // 二进制: 00000011
int result = a ^ b;
std::cout << "按位异或结果: " << result << std::endl;
return 0;
}
5和3按位异或的结果为00000110，即十进制的6。
按位取反（~）
按位取反操作符~对一个整数的每一位进行取反操作，将0变为1，1变为0。例如：
#include <iostream>
int main() {
int a = 5; // 二进制: 00000101
int result = ~a;
std::cout << "按位取反结果: " << result << std::endl;
return 0;
}
由于计算机中整数通常以补码形式存储，5的按位取反结果在32位系统中为11111111111111111111111111111010，以补码形式表示的有符号整数为 -6。
左移（<<）
左移操作符<<将一个整数的二进制位向左移动指定的位数。右边空出的位用0填充。例如：
#include <iostream>
int main() {
int a = 5; // 二进制: 00000101
int result = a << 2;
std::cout << "左移2位结果: " << result << std::endl;
return 0;
}
5左移2位后，二进制变为00010100，即十进制的20。
右移（>>）
右移操作符>>将一个整数的二进制位向右移动指定的位数。对于无符号整数，左边空出的位用0填充；对于有符号整数，若为正数左边空出的位用0填充，若为负数左边空出的位用1填充（算术右移）。例如：
#include <iostream>
int main() {
int a = 5; // 二进制: 00000101
int result = a >> 2;
std::cout << "右移2位结果: " << result << std::endl;
return 0;
}
5右移2位后，二进制变为00000001，即十进制的1。
利用位运算实现高效数据存储与操作
位掩码（Bitmask）
位掩码是一种利用位运算来表示一组标志或选项的技术。通过使用位掩码，可以在一个整数中存储多个布尔值，从而节省内存空间。
假设我们有一个表示文件权限的场景，文件可以有读（read）、写（write）和执行（execute）权限。我们可以用一个整数的不同位来表示这些权限：
// 定义权限掩码
const int READ = 1 << 0; // 00000001
const int WRITE = 1 << 1; // 00000010
const int EXECUTE = 1 << 2; // 00000100
// 设置文件权限
int filePermissions = READ | WRITE;
// 检查文件是否有读权限
bool hasReadPermission = (filePermissions & READ) != 0;
// 增加执行权限
filePermissions |= EXECUTE;
// 移除写权限
filePermissions &= ~WRITE;
在上述代码中，我们通过左移操作创建了不同的权限掩码，然后利用按位或|来设置权限，按位与&来检查权限，按位取反~和按位与&来移除权限。
状态压缩
在一些算法问题中，我们需要记录多个对象的状态。如果每个对象的状态只有两种（例如开/关、存在/不存在等），可以使用位运算进行状态压缩，将多个对象的状态存储在一个整数中。
例如，假设有5个灯泡，每个灯泡可以是亮或灭。我们可以用一个5位的整数来表示这5个灯泡的状态：
#include <iostream>
// 打开第n个灯泡
void turnOn(int& state, int n) {
state |= (1 << n);
}
// 关闭第n个灯泡
void turnOff(int& state, int n) {
state &= ~(1 << n);
}
// 检查第n个灯泡是否打开
bool isOn(int state, int n) {
return (state & (1 << n)) != 0;
}
int main() {
int bulbState = 0; // 初始状态，所有灯泡关闭
turnOn(bulbState, 2); // 打开第3个灯泡
std::cout << "第3个灯泡是否打开: " << (isOn(bulbState, 2) ? "是" : "否") << std::endl;
turnOff(bulbState, 2); // 关闭第3个灯泡
std::cout << "第3个灯泡是否打开: " << (isOn(bulbState, 2) ? "是" : "否") << std::endl;
return 0;
}
这里，我们通过位运算实现了对多个灯泡状态的高效存储和操作。
位运算在算法优化中的应用
快速乘除法
利用位运算可以实现快速的乘法和除法操作。对于乘以2的幂次方，可以使用左移操作；对于除以2的幂次方，可以使用右移操作。
// 快速乘法
int fastMultiply(int a, int b) {
int result = 0;
while (b > 0) {
if (b & 1) {
result += a;
}
a <<= 1;
b >>= 1;
}
return result;
}
// 快速除法
int fastDivide(int a, int b) {
int result = 0;
while (a >= b) {
int temp = b;
int multiple = 1;
while ((temp << 1) <= a) {
temp <<= 1;
multiple <<= 1;
}
a -= temp;
result += multiple;
}
return result;
}
在fastMultiply函数中，我们通过检查b的二进制位是否为1来决定是否将a的相应倍数加到结果中。在fastDivide函数中，我们通过不断左移b找到小于等于a的最大b的倍数，然后从a中减去该倍数并累加倍数到结果中。
奇偶判断
判断一个整数是奇数还是偶数可以通过检查其最低位（LSB）来实现。如果最低位为1，则该数为奇数；如果为0，则为偶数。
bool isOdd(int num) {
return (num & 1) != 0;
}
这种方法比使用num % 2的取模操作更高效，因为取模操作在一些处理器上相对较慢。
找出数组中唯一出现一次的数
在一个数组中，除了一个数只出现一次外，其他数都出现两次。我们可以利用按位异或的性质来找出这个唯一的数。因为任何数与自身按位异或结果为0，而0与任何数按位异或结果为该数本身。
int findSingle(int arr[], int n) {
int result = arr[0];
for (int i = 1; i < n; i++) {
result ^= arr[i];
}
return result;
}
假设数组为{2, 3, 2, 4, 4}，通过对数组元素依次进行按位异或操作，最终得到的结果就是唯一出现一次的数3。
位运算与内存管理
内存对齐
在C++ 中，内存对齐对于提高程序性能非常重要。通过位运算可以实现内存对齐。例如，假设我们有一个结构体，需要按特定字节数对齐：
struct MyStruct {
char a;
int b;
};
// 计算结构体对齐后的大小
size_t alignSize(size_t size, size_t alignment) {
return (size + alignment - 1) & ~(alignment - 1);
}
int main() {
size_t structSize = sizeof(MyStruct);
size_t alignedSize = alignSize(structSize, 4);
std::cout << "结构体大小: " << structSize << std::endl;
std::cout << "对齐后大小: " << alignedSize << std::endl;
return 0;
}
在上述代码中，alignSize函数通过位运算实现了对大小的对齐。(size + alignment - 1)确保即使当前大小已经对齐，也能得到正确的结果。~(alignment - 1)创建了一个掩码，用于清除低alignment - 1位，从而实现对齐。
指针运算
在一些底层编程场景中，可能需要对指针进行按位操作。例如，在嵌入式系统中，可能需要根据内存地址偏移来访问特定的寄存器。
#include <iostream>
int main() {
int data[5] = {1, 2, 3, 4, 5};
int* ptr = data;
// 指针偏移
ptr = reinterpret_cast<int*>(reinterpret_cast<size_t>(ptr) + sizeof(int) * 2);
std::cout << "偏移后的值: " << *ptr << std::endl;
return 0;
}
这里，我们先将指针转换为size_t类型进行按位加法操作，然后再转换回指针类型，实现了指针的偏移。但需要注意的是，这种操作需要谨慎使用，因为不当的指针操作可能导致未定义行为。
位运算的高级技巧与优化
位运算与缓存优化
现代计算机系统中，缓存对于程序性能有着重要影响。通过合理使用位运算，可以减少缓存冲突，提高缓存命中率。
例如，在处理大型数组时，我们可以通过位运算来优化数组访问模式，使数据访问更具局部性。假设我们有一个二维数组，传统的按行访问方式可能导致缓存冲突：
int matrix[100][100];
// 传统按行访问
for (int i = 0; i < 100; i++) {
for (int j = 0; j < 100; j++) {
matrix[i][j] = i + j;
}
}
我们可以通过位运算来重新排列访问顺序，提高缓存命中率：
int matrix[100][100];
// 优化后的访问
for (int i = 0; i < 100; i++) {
for (int j = 0; j < 100; j++) {
int index = (i << 7) | j;
int row = index >> 7;
int col = index & ((1 << 7) - 1);
matrix[row][col] = row + col;
}
}
这里，我们通过将行和列索引进行位运算组合，然后再分解，改变了访问顺序，可能提高缓存利用率。
位运算与多线程编程
在多线程编程中，位运算也可以发挥作用。例如，在使用标志位来同步线程时，位运算可以提供高效的操作方式。
假设我们有多个线程，需要通过一个共享的标志位来通知某些事件。我们可以使用原子变量结合位运算来实现：
#include <iostream>
#include <atomic>
#include <thread>
std::atomic<int> flag(0);
const int FLAG1 = 1 << 0;
const int FLAG2 = 1 << 1;
void threadFunction1() {
// 设置标志1
flag |= FLAG1;
}
void threadFunction2() {
// 等待标志1
while (!(flag & FLAG1));
// 设置标志2
flag |= FLAG2;
}
int main() {
std::thread t1(threadFunction1);
std::thread t2(threadFunction2);
t1.join();
t2.join();
std::cout << "标志2是否设置: " << (flag & FLAG2 ? "是" : "否") << std::endl;
return 0;
}
在这个例子中，通过原子变量的位运算实现了线程间的简单同步。
位运算与代码混淆
在一些需要保护代码知识产权的场景中，位运算可以用于代码混淆。通过对代码中的关键逻辑使用位运算进行改写，可以增加代码的阅读难度。
例如，将简单的条件判断语句改写成位运算形式：
// 原始条件判断
int a = 5;
int b = 3;
if (a > b) {
std::cout << "a 大于 b" << std::endl;
}
// 位运算改写
int result = (a - b) >> 31;
if ((result & 1) == 0) {
std::cout << "a 大于 b" << std::endl;
}
这里，通过将减法结果的最高位右移并检查其值，实现了与a > b类似的判断逻辑，但代码变得更难理解。不过需要注意的是，代码混淆不应过度使用，以免影响代码的可维护性。
避免位运算中的常见错误
符号扩展问题
在进行右移操作时，对于有符号整数，要注意符号扩展问题。例如：
#include <iostream>
int main() {
signed char a = -1; // 二进制: 11111111
int result1 = a >> 1; // 有符号右移，结果为 -1，二进制: 11111111
unsigned char b = 255; // 二进制: 11111111
int result2 = b >> 1; // 无符号右移，结果为 127，二进制: 01111111
std::cout << "有符号右移结果: " << result1 << std::endl;
std::cout << "无符号右移结果: " << result2 << std::endl;
return 0;
}
如果在需要无符号右移的场景中使用了有符号右移，可能会得到意外的结果。
溢出问题
在进行左移操作时，要注意溢出问题。当左移的位数过多时，可能会导致数据溢出。例如：
#include <iostream>
int main() {
int a = 1;
int result = a << 31; // 在32位系统中，这会导致溢出
std::cout << "左移结果: " << result << std::endl;
return 0;
}
在进行左移操作前，应该确保左移的位数不会导致数据溢出，特别是在处理较大的数值时。
优先级问题
位运算符的优先级相对较低，在复杂表达式中，要注意优先级问题。例如：
#include <iostream>
int main() {
int a = 2;
int b = 3;
int result = a & b + 1; // 先计算 b + 1，再进行按位与操作
std::cout << "结果: " << result << std::endl;
return 0;
}
如果不确定优先级，可以使用括号来明确运算顺序，以避免错误。
通过深入理解和正确使用C++ 位运算的高级技巧，可以在程序性能优化、数据存储和算法设计等方面取得显著的效果。同时，要注意避免常见错误，确保代码的正确性和稳定性。