神奇的位运算

In editing…

必备知识

首先要对原码、反码、补码有一定理解，推荐阅读此文：https://www.cnblogs.com/zhangziqiu/archive/2011/03/30/computercode.html

摘要：按1 byte来算，1的机器数为0000 0001，原码、反码、补码均为 0000 0001. -1的机器数为1000 0001，原码为机器数、反码为1111 1110，补码为1111 1111. 总结来说：最高位用作符号位，0表示正数，1表示负数。正数的原、反、补码一样。负数的反码为除符号位外按位取反，补码为反码加1.

为什么C系语言中，int的范围为 $- 2^{n - 1} \sim 2^{n - 1} - 1$ ，其中n为bit数。同样以1 byte来算，8bit能够表达的有符号范围如下：

1111 1111   # -(2^7 - 1) = -127
0111 1111   #  (2^7 - 1) =  127

但从排列组合来看，8位能够表达的数字共有 $2^{8} = 256$ 个，而 $- 127 \sim 127$ 只有255个数。还有一个数跑哪去了呢。答案是0，0有两种表示方法：

1000 0000   # -0
0000 0000   # +0

这无疑是一种浪费，我们选择下面那个数表示0。而将上面的1000 0000（首先它表示一个负数，负数用补码表示，因此它应该是代表-128的补码）用于表示-128，如此一来，8bit的表达范围扩展到 $- 128 \sim 127$ ，正好 $256 = 2^{8}$ 个数。

至于为什么用1000 0000来表示-128，此中还是有些门道，来看-127的三码：

1111 1111   # -127原码
1000 0000   # -127反码
1000 0001   # -127补码

如此一来-128的补码就等于-127的补码减一得：1000 0000. 关于负数为什么用补码表示，其实是为了做加法，计算机内没有减法器，只有加法器，具体参见上文。以上我只是用8bit数举例，实际计算机中int可能有32bit，以此类推。

以下部分转载自：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++位运算符

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

Summary from learncpp.com

Cf. https://www.learncpp.com/cpp-tutorial/bit-manipulation-with-bitwise-operators-and-bit-masks/

Summarizing how to set, clear, toggle, and query bit flags:

To query bit states, we use bitwise AND:

if (flags & option4) ... // if option4 is set, do something

To set bits (turn on), we use bitwise OR:

flags |= option4; // turn option 4 on.
flags |= (option4 | option5); // turn options 4 and 5 on.

To clear bits (turn off), we use bitwise AND with bitwise NOT:

flags &= ~option4; // turn option 4 off
flags &= ~(option4 | option5); // turn options 4 and 5 off

To flip bit states, we use bitwise XOR:

flags ^= option4; // flip option4 from on to off, or vice versa
flags ^= (option4 | option5); // flip options 4 and 5

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:

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<<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低位，按位取反相与

Learn2Live

探索