神奇的位运算

In editing…

必备知识

以下部分转载自：http://www.cnblogs.com/junsky/archive/2009/08/06/1540727.html

假设有一个 int 类型的数，值为5，那么，我们知道它在计算机中表示为：

00000000 00000000 00000000 00000101

5转换成二制是101，不过int类型的数占用4字节（32位），所以前面填了一堆0。

1 byte = 8 bits

现在想知道，-5在计算机中如何表示？在计算机中，负数以其正值的补码形式表达。什么叫补码呢？这得从原码，反码说起。

原码：一个整数，按照绝对值大小转换成的二进制数，称为原码。
比如
00000000 00000000 00000000 00000101 是 5 的原码。
反码：将二进制数按位取反，所得的新二进制数称为原二进制数的反码。
取反操作指：原为1，得0；原为0，得1。（1变0; 0变1）
比如：将
00000000 00000000 00000000 00000101每一位取反，得
11111111 11111111 11111111 11111010。
称：
11111111 11111111 11111111 11111010 是
00000000 00000000 00000000 00000101 的反码。
反码是相互的，所以也可称：
11111111 11111111 11111111 11111010 和
00000000 00000000 00000000 00000101 互为反码。
补码：反码加1称为补码。
也就是说，要得到一个数的补码，先得到反码，然后将反码加上1，所得数称为补码。
比如：
00000000 00000000 00000000 00000101 的反码是：
11111111 11111111 11111111 11111010。
那么，补码为：
11111111 11111111 11111111 11111010 + 1 =
11111111 11111111 11111111 11111011

所以，-5 在计算机中表达为：
11111111 11111111 11111111 11111011。转换为十六进制：0xFFFFFFFB。

再举一例，我们来看整数-1在计算机中如何表示。假设这也是一个int类型，那么：

先取1的原码：
00000000 00000000 00000000 00000001
得反码：
11111111 11111111 11111111 11111110
得补码：
11111111 11111111 11111111 11111111

可见，－1在计算机里用二进制表达就是全1。16进制为：0xFFFFFF.

转载部分结束，感谢原作者。为了便于阅读，我对排版稍作了改动。

常见的位运算

C/C++位运算符

~：按位取反
<<：左移位
>>：右移位
&：按位与
|：按位或
^：按位异或

Applications

除以/乘以2

n >> 1: 右移一位，低位的1被忽略，floor(n/2).
n << 1: 左移一位，低位补0，n * 2.

取相反数

~n + 1：对n取反得到反码，加1得到补码，即对应的负数。
(n ^ -1) + 1：-1的二进制全是1，按位异或之后得到的等价与按位取反。

计算 n+1

-(~n)：

~n + 1 = -n
-(~n + 1) = n
-~n - 1 = n
-~n = n+1

计算 n-1

~-n:

1
2
3

n-1 = -(-n+1)
-n+1 = -(~-n) <--- n+1 = -~n
n-1 = ~-n

if(x==a) x=b; if(x==b) x=a;

x = a ^ b ^ x：如果x=a，则相当于对b翻转两次，结果自然是b；如果x=b，那么b^b=0，0异或任何数都没有效果，故结果是a.

判断奇偶

n & 1: 如果结果为1，则表明n的最低位为1，n为奇数；反之为偶数。

变量互换（无需临时变量）

a ^= b ^= a ^= b:

// the expression expands two:
1). b ^= a ^= b; // now final_b = b ^ (a^b) = a, temp_a = (a^b)
2). a ^= b; // now final_a = temp_a ^ final_b = (a^b) ^ a = b

// as you know, xor twice does nothing!

// ---------------------------------------------//
// if you doesn't understand, read the following:
// read from right to left
// now we are reading `a ^= b`
a ^= b --> = a ^ b // tag this tmp_a = a ^ b

// we are reading `b ^= a ^= b`
b ^= a --> = b ^ (a ^ b) = a

// we are reading `a ^= b ^= a ^= b`
a ^= b --> = tmp_a ^ b = (a ^ b) ^ a = b

// at last
b = a
a = b

判断是否为2的幂

n & (n-1)：如果n是2的幂，则

n   = 0b100000...
n-1 = 0b011111...
// now n & (n-1) = 0, we can judge if it is 0
// to determine wether n is a power of 2.

对2的n次方取余

m & ((1<<n) - 1):

1
2
3

(1<<n)      = 0b10000... // is the nth power of 2
(1<<n) - 1  = 0b01111...
m & ((1<<n) - 1) // keep the bits lower than n

取n的第m低位

(n >> (m-1)) & 1: 右移m-1位，最低位即为原从低到高第m位

将n的第m低位置1

n | (1 << (m-1)): 将1左移m-1位于n的第m低位对应，相或置1

将n的第m低位置0

n & ~(1 << (m-1)): 将1左移m-1位对上n的第m低位，按位取反相与