位计算技巧(一)

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

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

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

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

&   -  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有相反的符号。
}

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);
}

def swap(a, b):
    a ^= b
    b ^= a
    a ^= b

当然也可以这样写：

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。

int， long， … 都可以用这种方法获得最大值和最小值

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
}

1
2
3

int mulTwo(int n){
	return n << m;
}

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

1
2
3

int divTwo(int n){
    return n >> m;
}

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