东莞网站建设怎么样靠谱的免费建站
位运算的进阶操作,适合做题的时候用,共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;
}