062. 使用位运算优化算法
位运算是C语言中一种高效的操作方式，通过对整数的二进制表示进行操作，可以实现快速的数学运算和逻辑操作。位运算通常比传统的算术运算更快，因为它直接操作CPU寄存器中的数据。以下是一些常见的位运算技巧及其在优化算法中的应用。
常见的位运算符
-
&：按位与（AND） -
|：按位或（OR） -
^：按位异或（XOR） -
~：按位取反（NOT） -
<<：左移 -
>>：右移
1. 判断奇偶性
传统方法：
int isEven(int n) {
return n % 2 == 0;
}
位运算优化：
int isEven(int n) {
return (n & 1) == 0;
}
解释：一个数的二进制表示中，最低位为0表示偶数，为1表示奇数。
2. 交换两个变量的值
传统方法：
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
位运算优化：
void swap(int* a, int* b) {
*a ^= *b;
*b ^= *a;
*a ^= *b;
}
解释：利用异或运算的性质，a ^= b; b ^= a; a ^= b; 可以实现两个变量的值交换。
3. 获取两个数的最大值和最小值
传统方法：
int max(int a, int b) {
return (a > b) ? a : b;
}
int min(int a, int b) {
return (a < b) ? a : b;
}
位运算优化：
int max(int a, int b) {
return b & ((a - b) >> 31) | a & (~(a - b) >> 31);
}
int min(int a, int b) {
return a & ((a - b) >> 31) | b & (~(a - b) >> 31);
}
解释：a - b 的符号位（最高位）可以用来判断 a 和 b 的大小。右移31位可以将符号位扩展到整个32位整数。
4. 检查一个数是否是2的幂
传统方法：
int isPowerOfTwo(int n) {
if (n <= 0) return 0;
while (n > 1) {
if (n % 2 != 0) return 0;
n /= 2;
}
return 1;
}
位运算优化：
int isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
解释：一个数如果是2的幂，其二进制表示中只有一个1，其余位都是0。n & (n - 1) 会将最低位的1清零，如果结果为0，则说明 n 是2的幂。
5. 计算一个数的二进制表示中有多少个1
传统方法：
int countBits(int n) {
int count = 0;
while (n) {
if (n & 1) count++;
n >>= 1;
}
return count;
}
位运算优化（Brian Kernighan算法）：
int countBits(int n) {
int count = 0;
while (n) {
n &= (n - 1); // 清除最低位的1
count++;
}
return count;
}
解释：n & (n - 1) 会将最低位的1清零，每次循环清除一个1，直到 n 为0。
6. 交换两个变量的值而不使用临时变量
传统方法：
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
位运算优化：
void swap(int* a, int* b) {
*a ^= *b;
*b ^= *a;
*a ^= *b;
}
解释：利用异或运算的性质，a ^= b; b ^= a; a ^= b; 可以实现两个变量的值交换。
7. 检查两个整数的符号是否相同
传统方法：
int sameSign(int a, int b) {
return (a > 0 && b > 0) || (a < 0 && b < 0);
}
位运算优化：
int sameSign(int a, int b) {
return (a ^ b) >= 0;
}
解释：两个数的符号位相同，它们的异或结果的符号位为0；符号位不同，异或结果的符号位为1。
8. 清除一个数的最低位的1
传统方法：
int clearLowestBit(int n) {
int pos = 0;
while ((n & (1 << pos)) == 0) {
pos++;
}
return n & ~(1 << pos);
}
位运算优化：
int clearLowestBit(int n) {
return n & (n - 1);
}
解释：n & (n - 1) 会将最低位的1清零。
9. 设置一个数的第k位为1
传统方法：
int setBit(int n, int k) {
return n | (1 << k);
}
解释：使用按位或运算将第k位设置为1。
10. 清除一个数的第k位
传统方法：
int clearBit(int n, int k) {
return n & ~(1 << k);
}
解释：使用按位与运算将第k位清零。
11. 翻转一个数的第k位
传统方法：
int flipBit(int n, int k) {
return n ^ (1 << k);
}
解释：使用按位异或运算翻转第k位。
总结
位运算是一种强大的工具，可以显著提高程序的效率。通过使用位运算，可以避免复杂的算术运算和条件判断，直接操作数据的二进制表示。在实际开发中，合理使用位运算可以优化算法的性能，特别是在处理低级系统编程和嵌入式系统时。
视频讲解
BiliBili： 视睿网络-哔哩哔哩视频 (bilibili.com)