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. 先取 1 的原码： 00000000 00000000 00000000 00000001
  2. 得反码： 11111111 11111111 11111111 11111110
  3. 得补码： 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:

1

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

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

1
2

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:

1
2

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

To flip bit states, we use bitwise XOR:

1
2

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

// 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 的幂，则

1
2
3
4

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

References

  1. 负数的二进制表示方法
  2. 优秀程序员不得不知道的 20 个位运算技巧