位运算的骚操作
题目1 判断一个整数是不是2的幂
1
2
3
4
bool isPowerOfTwo(int n){
return n > 0 && n == (n & -n);
// 或者return n > 0 && n & (n-1) == 0;
}
题目2 判断一个整数是不是3的幂
1
2
3
bool isPowerOfThree(int n){
return n > 0 && 1162261467 % n == 0;
}
题目3 >= n 的最小的2的幂
1
2
3
4
5
6
7
8
9
10
11
12
13
int near2power(int n){
if(n <= 0){
return 1;
}
n--; // 减1是为了防止n本身就是2的幂
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
n++;
return n;
}
题目4 范围内所有数字&的结果
1
2
3
4
5
6
int rangeBitwiseAnd(int left, int right) {
while(left < right){
right &= right - 1;
}
return right;
}
题目5 逆序二进制的状态
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int reverseBits(unsigned int n){
// 32位整数的位数
// 1:0001 2:0010 3:0011 4:0100 5:0101 6:0110 7:0111 8:1000 9:1001
// a:1010 b:1011 c:1100 d:1101 e:1110 f:1111
// n = abcdefgh 以8位为例
n = (n & 0xaaaaaaaa) >> 1 | (n & 0x55555555) << 1;
// 步骤1:a0c0e0g0 和 0b0d0f0h
// 步骤2:得到 0a0c0e0g 和 b0d0f0h0
// 步骤3:得到 badcfehg
// 此时交换相邻1位完毕 -> n = (ba)(dc)(fe)(hg)
n = (n & 0xcccccccc) >> 2 | (n & 0x33333333) << 2;
// 此时交换相邻2位完毕 -> n = (dcba)(hgfe)
n = (n & 0xf0f0f0f0) >> 4 | (n & 0x0f0f0f0f) << 4;
// 此时交换相邻4位完毕 -> n = (hgfedcba)
n = (n & 0xff00ff00) >> 8 | (n & 0x00ff00ff) << 8;
// 此时交换相邻8位完毕
n = (n & 0xffff0000) >> 16 | (n & 0x0000ffff) << 16;
// 此时交换相邻16位完毕，即为正确答案
return n;
}
题目6 二进制中有几个1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int cntOne(unsigned int n){
// 32位整数的位数
// 1:0001 2:0010 3:0011 4:0100 5:0101 6:0110 7:0111 8:1000 9:1001
// a:1010 b:1011 c:1100 d:1101 e:1110 f:1111
// n = 11111001 以8位为例
n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
// 步骤1:相与得到 01010001 和 01010100
// 步骤2:相加得到 11011000
n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f);
n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff);
n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff);
return n;
}
为简便操作，可使用以下函数：
1
2
3
4
5
6
7
8
9
10
11
__builtin_popcount(n); // 直接返回n的二进制1的个数
// __builtin_popcountl(n); // 32位整数的位数
// __builtin_popcountll(n); // 64位整数的位数
// Count Leading Zeros (CLZ) and Count Trailing Zeros (CTZ)
// 分别指 前导0的个数 和 末尾0的个数
__builtin_clz(n); // 计算前导0的个数(返回n的二进制最高位的1的位置)
// __builtin_clzll(n); // 64位整数的位数
__builtin_ctz(n); // 计算末尾0的个数(返回n的二进制最低位的0的位置)
// __builtin_ctzll(n); // 64位
__builtin_parity(n); // 计算n的奇偶性(返回n的二进制中1的个数的奇偶性)
// __builtin_parityll(n); // 64位
