位操作的一些常识和技巧
1. 在明确知道补码整数类型对应位数为
时，可以通过右移
位再与常数1做与操作来得到符号位数值
假设int类型以4字节(32位bit)表示，则对应的为32，符号位计算方法如下：
int sign = (x >> 31) & 1;
2. 几乎所有现代机器对右移操作都遵循以下原则：有符号数(补码)使用算术右移(左边填充符号位数值), 无符号数使用逻辑右移(左边填充0)
假设int类型以8位bit表示，右移结果如下：
int x = 0x80; // 1000 0000
unsigned int y = 0x80; // 1000 0000
x = x >> 2; // x = 0xE0 (1110 0000)
y = y >> 2; // y = 0x20 (0010 0000)
3. 二进制补码转换为十进制时，最直观的方法是对各数位取对应2的幂级数后相加，其中符号位幂级数取负值，其余位幂级数取正值
对于位补码二进制串:
，转换为十进制操作定义为
，其中
表示第
位的数值，
为最低位，
为最高位（符号位），则有：
4. 全0码 与 全1码 的应用
假设x和y是8位整型数值，8位全0码为0x00，8位全1码为0xFF，则有如下公式成立：
- x & 0x00 = 0
- x & 0xFF = x
- x | 0x00 = x
- x | 0xFF = 0xFF
- x ^ 0x00 = x
- x ^ 0xFF = ~x
5. 位操作补码整数取负
Trick ：“取反加1”
/*
* negate - return -x
* Example: negate(1) = -1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
int negate(int x) {
return ~x + 1;
}
6. 位操作判断某些二进制位是否为1
Trick ：与掩码做"与"操作后的值如果与掩码相同则可以确定相应位置全为1
/*
* allOddBits - return 1 if all odd-numbered bits in word set to 1
* where bits are numbered from 0 (least significant) to 31 (most significant)
* Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 12
* Rating: 2
*/
int allOddBits(int x) {
int mask = 0xAA;
mask += (mask << 8);
mask += (mask << 16);
return !((mask & x) ^ mask);
}
7. 位操作判断一个数是否在取值范围内
Trick ：要判断 a <= x <= b 是否成立, 可以转换为判断 x-a >= 0 && x-(b+1) < 0 是否成立，进而转换为判断 x-a 和 x-(b+1) 的符号
/*
* isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' to '9')
* Example: isAsciiDigit(0x35) = 1.
* isAsciiDigit(0x3a) = 0.
* isAsciiDigit(0x05) = 0.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 15
* Rating: 3
*/
int isAsciiDigit(int x) {
int lower = x + (~0x30 + 1);
int upper = x + (~0x3a + 1);
// return 1 if lower >= 0 and upper < 0
return !((lower >> 31) | ~(upper >> 31));
}
8. 位操作实现三目运算
Trick ：bool型数值（0或1）取负正好可以得到全0码或全1码（0x00或0xFF）
/*
* conditional - same as x ? y : z
* Example: conditional(2,4,5) = 4
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 16
* Rating: 3
*/
int conditional(int x, int y, int z) {
x = !!x; // 0x01 or 0x00
x = ~x + 1; // 0xff or 0x00
return (x & y) | (~x & z);
}
9. 位操作判断两数大小
Trick ：判断符号相同或不同可以使用异或操作，符号不同时正数大，符号相同时判断差值
/*
* isLessOrEqual - if x <= y then return 1, else return 0
* Example: isLessOrEqual(4,5) = 1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 24
* Rating: 3
*/
int isLessOrEqual(int x, int y) {
int is_x_neg = (x >> 31);
int is_y_neg = (y >> 31);
int is_y_sub_x_neg = ((y + ~x + 1) >> 31);
int is_diff_sign = is_x_neg ^ is_y_neg;
return (!is_diff_sign & !is_y_sub_x_neg) | (is_diff_sign & !is_y_neg);
}
10. 位操作实现“否”运算
/*
* logicalNeg - implement the ! operator, using all of
* the legal operators except !
* Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
* Legal ops: ~ & ^ | + << >>
* Max ops: 12
* Rating: 4
*/
int logicalNeg(int x) {
return ((x | (~x + 1)) >> 31) + 1;
}
11. 位操作判断一个数最少需要多少bit表示
Trick1：
若为正数，找到最高一位1，再加上一个符号位
若为负数，找到最高一位0，再加上一个符号位示例：
-3可以表示为101、1101、11101等，但最高以为0都是出现在第2位，当使用3位以上bit表示的时候高位均为1，所以最少需要2+1=3位bit来表示，也就是101
Trick2：
为了统一操作可以把负数转换为正数，则只要找最高位1即可
Trick3：
可以使用二分思想移位，来排除或确定某一半的高位是否存在1大致思想如下（x为n位二进制正数）：
（1）令 b = x >> (n/2)，若 b = 0 表示高 n/2 位中不包含1，只需在低 n/2 位中寻找1即可，反之若 b != 0 则表示高 n/2 位中包含1。
（2）当 b != 0 时可以很容易想到令 x = x >> (n/2) 来移除低 n/2 位，再令 n = n/2 并重复步骤（1）来判断剩余一半的情况；而当 b = 0 时，需要考虑的是低 n/2 ，此时可以先令 n = n/2，再令 x = x >> (n/2) ，由于已经可以确定高 n/2 位全为0，此时只需要右移余下的一半（即 n/4）即可继续二分判断。
/* howManyBits - return the minimum number of bits required to represent x in
* two's complement
* Examples: howManyBits(12) = 5
* howManyBits(298) = 10
* howManyBits(-5) = 4
* howManyBits(0) = 1
* howManyBits(-1) = 1
* howManyBits(0x80000000) = 32
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 90
* Rating: 4
*/
int howManyBits(int x) {
// 如果是负数取反, 统一转换为找最高位1
// is_neg = 0 --> 0xff & x --> x
// is_neg = 1 --> (0xfe & x) | (0x01 & ~x) --> ~x
int is_neg = (x >> 31);
x = (~is_neg & x) | (is_neg & ~x);
// 二分法找最高位1
// 每次右移n/2或0位,来判断高位是否包含1并缩小搜索范围
int b16, b8, b4, b2, b1, b0;
b16 = (!!(x >> 16)) << 4; // if high 16 bits has 1 b16 = 16 else b16 = 0
x = x >> b16;
b8 = (!!(x >> 8)) << 3;
x = x >> b8;
b4 = (!!(x >> 4)) << 2;
x = x >> b4;
b2 = (!!(x >> 2)) << 1;
x = x >> b2;
b1 = !!(x >> 1);
x = x >> b1;
b0 = x;
return b16 + b8 + b4 + b2 + b1 + b0 + 1;
}
11. 快速找到补码二进制最低位的1的位置
Trick: 二进制取负变换可以快速写成除最低位1之后的所有位都取反
例：假设x为8位bit表示的int，x = 12，则x和~x+1的二进制表示分别为：
0 0 0 0 1 1 0 0
1 1 1 1 0 1 0 0
x & (~x + 1) 即可以得到只剩最低位1的二进制表示 0 0 0 0 0 1 0 0
int x = 12;
unsigned int y = x & (~x + 1);
int pos = 0;
while (y > 0) {
y >>= 1;
++pos;
}
// finally pos = 3
