位运算进阶操作

位运算的进阶操作，适合做题的时候用，共10点

1.通过位运算与特定的位模式进行掩码操作，可以提取、设置或清除特定的位信息。例如，我们可以使用位掩码来检查一个数的二进制表示中特定位置是否为1。

bool checkBit(int num, int position) {int mask = 1 << position;return ((num & mask) != 0);
}

2.位运算交换值,无需使用额外的变量

void bitwiseSwap(int& a, int& b) {a = a ^ b;b = a ^ b;a = a ^ b;
}

3.位运算计数，可以快速计算整数的二进制表示中有多少个位为1。

int countBits(int num) {int count = 0;while (num != 0) {count += num & 1;num >>= 1;}return count;
}

4.位运算生成全排列

void generatePermutations(int n) {// 生成0到2^n-1的所有整数for (int i = 0; i < (1 << n); ++i) {// 对每个整数，输出选择的位for (int j = 0; j < n; ++j) {if (i & (1 << j)) {cout << j << " ";}}cout << endl;}
}

5.位运算快速幂运算，时间复杂度为O(logn) n为指数

int fastPower(int base, int exponent) {int result = 1;while (exponent > 0) {if (exponent & 1) {result *= base;}base *= base;exponent >>= 1;}return result;
}

6.位运算判断是否为2的幂

bool isPowerOfTwo(int num) {return (num != 0) && ((num & (num - 1)) == 0);
}

7.位运算求补集

int bitwiseComplement(int num) {unsigned int mask = 1;while (mask < num) {mask = (mask << 1) + 1;}return num ^ mask;
}

8.位运算统计不同位数,以快速统计两个整数的二进制表示中不同的位数

int countDifferentBits(int num1, int num2) {int count = 0;int diff = num1 ^ num2;while (diff != 0) {count += diff & 1;diff >>= 1;}return count;
}

9.位运算获取最右边的1

int getRightmostOne(int num) {return num & -num;
}

10.位运算交换二进制奇偶位

int swapOddEvenBits(int num) {unsigned int evenBits = num & 0xaaaaaaaa;  // 1010...unsigned int oddBits = num & 0x55555555;   // 0101...evenBits >>= 1;oddBits <<= 1;return evenBits | oddBits;
}