位运算技巧可以巧妙有效的操作整数,有许多非常有用的应用,同时因为程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算直接对整数在内存中的二进制位进行操作。因此处理速度非常快。

例如,在计算一个整数中包含多少个1之类的操作时,可以只用几个位操作符来搞定。

假设我们已经知道一个整数的原码、补码、反码表示,以及位运算的相关知识。

在本文中,将使用以下符号表示位操作:

1
2
3
4
5
6
&   -  bitwise and
| - bitwise or
^ - bitwise xor
~ - bitwise not
<< - bitwise shift left
>> - bitwise shift right

判断整数的奇偶

1
2
3
bool isOddNumber(int n){
return (n & 1) == 0;
}

判断两个数符号是否相同

1
2
3
bool isSameSign(int x, int y){ //有0的情况例外
return (x ^ y) >= 0; // true 表示 x和y有相同的符号, false表示x,y有相反的符号。
}

判断一个数是不是2的幂

1
2
3
4
5
6
bool isPowerOfTwo(int x){

//如果一个数是2的次幂,那么除首位,其余为肯定都为0,减一后其余为为1

return x && !(x & (x - 1)) == 1;
}

交换两个数(不用临时变量)

1
2
3
void swap(int *a, int*b){
(*a) ^= (*b) ^= (*a) ^= (*b);
}
1
2
3
4
def swap(a, b):
a ^= b
b ^= a
a ^= b

当然也可以这样写:

1
2
3
4
5
void swap(int *a, int *b){
a = a + b;
b = a - b;
a = a - b;
}

加法和减法互为逆运算,并且加法满足交换律,所以不需要临时变量即可交换。

而xor的逆运算即为本身,所以我们就看到了用三次xor运算交换两个数的方法。

同样因为xor的逆运算即为本身,两次xor同一个数最后结果不变,即(a xor b) xor b = a,我们可以实现简单的加密,选择一个数为密钥作为b。

获得整型最大值

intlong, … 都可以用这种方法 获得最大值和最小值

1
2
3
int getMaxInt(){
return ((unsigned int) - 1) >> 1; //2147483647
}
1
2
3
int getMaxInt(){
return (1 << 31) - 1;//2147483647
}
1
2
3
int getMaxInt(){
return ~(1 << 31);//2147483647
}
1
2
3
int getMaxInt(){//有些编译器不适用
return (1 << -1) - 1;//2147483647
}

获得整型最小值

1
2
3
int getMinInt(){
return 1 << 31;//-2147483648
}
1
2
3
int getMinInt(){//有些编译器不适用
return 1 << -1;//-2147483648
}

乘以2的m次方

1
2
3
int mulTwo(int n){
return n << m;
}

这样当m=1时,即为乘以2.

除以2的m次方

1
2
3
int divTwo(int n){
return n >> m;
}

同理,m=1时,即为除以2.

一些变换操作

功能 示例 位运算
去掉最后一位 (101101->10110) x >> 1
在最后加一个0 (101101->1011010) x << 1
在最后加一个1 (101101->1011011) (x << 1) + 1
把最后一位变成1 (101100->101101) x | 1
把最后一位变成0 (101101->101100) (x | 1) - 1
最后一位取反 (101101->101100) x ^ 1
把右数第k位变成1 (101001->101101,k=3) x | (1 << (k-1))
把右数第k位变成0 (101101->101001,k=3) x & ~ (1 << (k-1))
右数第k位取反 (101001->101101,k=3) x ^ (1 << (k-1))
取末三位 (1101101->101) x & 7
取末k位 (1101101->1101,k=5) x & (1 << k-1)
取右数第k位 (1101101->1,k=4) x >> (k-1) & 1
把末k位变成1 (101001->101111,k=4) x | (1 << k-1)
末k位取反 (101001->100110,k=4) x ^ (1 << k-1)
把右边连续的1变成0 (100101111->100100000) x & (x+1)
把右起第一个0变成1 (100101111->100111111) x | (x+1)
把右边连续的0变成1 (11011000->11011111) x | (x-1)
取右边连续的1 (100101111->1111) (x ^ (x+1)) >> 1
去掉右起第一个1的左边 (100101000->1000) x & (x ^ (x-1))