Bit Manipulation
常用位运算
| 功能 | 示例 | 位运算 |
|---|---|---|
| 去掉最后一位 | (101101->10110) | x >> 1 |
| 在最后加一个0 | (101101->1011010) | x << 1 |
| 在最后加一个1 | (101101->1011011) | (x << 1) + 1 |
| 把最后一位变成1 | (101100->101101) | x or 1 |
| 把最后一位变成0 | (101101->101100) | x or 1 - 1 |
| 最后一位取反 | (101101->101100) | x ^ 1 |
| 把右数第k位变成1 | (101001->101101,k=3) | x or (1 << (k-1)) |
| 把右数第k位变成0 | (101101->101001,k=3) | x and not (1 << (k-1)) |
| 右数第k位取反 | (101001->101101,k=3) | x ^ (1 << (k-1)) |
| 取末三位 | (1101101->101) | x and 7 |
| 取末k位 | (1101101->1101,k=5） | x and( (1 << k) -1)即 x and 2k−1)2k−1) |
| 取右数第k位 | (1101101->1,k=4) | x >> (k-1) and 1 |
| 把末k位变成1 | (101001->101111,k=4) | x or ((1<< k)-1) 即 x or 2k−12k−1 |
| 末k位取反 | (101001->100110,k=4) | x xor ( (1 << k) -1)即 x ^ 2k−12k−1 |
| 把右边连续的1变成0 | (100101111->100100000) | x and (x+1) |
| 把右起第一个0变成1 | (100101111->100111111) | x or (x+1) |
| 把右起第一个1变成0 | 11011000->11010000 | x and (x-1) |
| 把右边连续的0变成1 | (11011000->11011111) | x or (x-1) |
| 取右边连续的1 | (100101111->1111) | (x ^ (x+1)) << 1 |
| 去掉右起第一个1的左边 | (11010 1000->1000) | x and (x xor (x-1))或者 x & (-x) |
交换两个整数a,b `` a = a^b; b = a^b; a = a^b;
# 不同任何比较判断找出两个数中较大的数
```c++
/*
*得到a-b的值得符号
*/
/n只取值0或1，为0时返回1，为1时返回0
int b_xor(int n){
return n^1;
}
//当一个数字高位为0时，表示为整数，返回1，
int isPositive(int c){
return b_xor((c>>31) & 1);
}
int getMax(int a, int b){
//c可能溢出
int c = a - b;
int signOfC = isPositive(c);
int signOfB = b_xor(signOfc);
return a*signOfC + b*signOfB;
}
int getMax(int a, int b){
int c = a-b;
int sa = isPositive(a);
int sb = isPositive(b);
int sc = isPositive(c);
int difSab = sa ^ sb;
int sameSab = b_xor(difSab);
return a*(difSab*sa + sameSab*sc) + b*b_xor(difSab*sa + sameSab*sc)
}
用位运算实现整数的加减乘除运算
加法
int add(int a, int b){
int sum = 0;
while(b != 0){
sum = a^b;
b = (a&b) << 1;
a = sum;
}
return sum;
}
减法
//取反
int neg(int n){
return add(~n,1);
}
int minus(int a, int b){
return add(a, neg(b));
}
乘法
用位运算实现乘法。a*b的结果可以写成
$$a2^0b0 + a 2^1 b_1 + a2^ib_i + ...a2^{31}b{31}$$,
其中bi为0或1代表整数b的二进制表达式中第i位的值。
int mul(int a, int b){
int res = 0;
while(b != 0){
if(b&1){
res = add(res, a);
}
a <<= 1;
b >>= 1;
}
return res;
}