欢迎访问我的博客:blog.chungzh.cn

基本概念

比特(bit,亦称二进制位)是指 1 位二进制的数码(0 或 1),是计算机中信息的最小单位。

字节(byte):一个字节由 8 位组成。

熟练地运用位运算,可以提高我们程序的时空效率。

计算机中的整数存储与运算

下面以 32 位二进制数,即 C++ 中的 intunsigned int 类型为例。

原码、反码

简单介绍一下:

  1. 原码:最高位为符号位,正数为 00,负数为 11,其余所有位为十进制数的绝对值。

    • 优点:对人类而言最直观。
    • 缺点:无法将减法转换成加法运算。如:11=1+(1)=0001+1001=1010=21-1=1+(-1)=0001+1001=1010=-200 有两种表示方法 0000000010001000
  2. 反码:最高位为符号位,正数为 00,负数为 11。正数的反码等于本身,负数的反码除符号位外,各位取反。

    • 优点:解决了减法运算的问题。11=1+(1)=0001+1110=1111=01-1=1+(-1)=0001+1110=1111=0
    • 缺点:00 有两种表示方法 0000000011111111;减法算法规则较复杂,需要额外判断溢出。

补码

  • 32 位无符号整数 unsigned int: 直接把这 32 位编码 CC 看作 32 位二进制数 NN

  • 32 位有符号整数 int: 以最高位作为符号位00 表示非负数,11 表示负数。

    对于最高位为 00 的每种编码 CC,直接看做 32 位二进制数 SS

    同时,定义该编码按位取反后得到的编码 ~C 表示的数值为 1S-1-S

    32 位补码表示 unsigned int int
    000000000000000000\cdots 000000 00
    011111111111011111\cdots 111111 21474836472147483647
    100000000000100000\cdots 000000 21474836482147483648 2147483648-2147483648
    111111111111111111\cdots 111111 42949672954294967295 1-1

可以发现,在补码下,每个数值都有唯一的表示方式,并且任意两个数值做加减法运算,都等价于在 32 位补码下做最高位不进位的二进制加减法运算。发生上/下溢出时,32 位无符号整数和有符号整数都相当于自动对 2322^{32} 取模(回绕)。

这也解释了有符号整数算术上溢时会出现负数的现象。我们来对 int 的溢出做一个实验:

void print(int t) { cout << bitset<32>(t) << " " << t << endl; }
int main() {
  int t = 2147483647;
  print(t);
  print(t + 1);
  print((t + 1) * 2);
  return 0;
}

输出:

01111111111111111111111111111111 2147483647
10000000000000000000000000000000 -2147483648
00000000000000000000000000000000 0

(t+1)*2 的结果本应是 1000000000003201\underbrace{00000\cdots 000000}_{32 个 0},依据最高位不进位原则,结果变成了 00000000000320=0\underbrace{00000\cdots 000000}_{32 个 0} = 0

补码也被称为“二补数”(Two's complement)。反码也叫“一补数”(Ones' complement),直接把 CC(正数)的每一位取反表示负 CC。补码与反码在负数表示中,绝对值相差 11。例如在上面的表格中,第一、四行是一对反码,第二、三行是一对反码。作为整数编码,补码比反码有很多优势。除了上面提到的“自然溢出取模”之外,补码重点解决了 00 的编码唯一性问题,能比反码多表示一个数。同时减少特殊判断,在电路设计中简单高效。

形式 加数
32 位补码 111111111\cdots 111 000001000\cdots 001 (1)溢出000000(1)_{溢出}000\cdots 000
int 1-1 11 00
unsigned int 42949672954294967295 0(mod232)0(\mod 2^{32})

“反码加一”只是补码所具有的一个性质,不能被定义成补码。负数的补码,是能够和其相反数相加通过溢出从而使计算机内计算结果变为 00 的二进制码。这是补码设计的初衷,具体目标就是让 1+(1)=01+(-1)= 0,这利用原码是无法得到的。

所以对于一个 nn 位的负数 X-X,有如下关系:

X+(X)=1000n=2nX_补 + (-X)_补 = 1\underbrace{00\cdots 0}_n = 2^n

所以 X-X 的补码应该是 2nX2^n-X 的二进制编码。

形式 加数
32 位补码 011111011\cdots 111 000001000\cdots 001 100000100\cdots 000
int 21474836472147483647 11 2147483648-2147483648
unsigned int 21474836482147483648

因为用二进制表示一个 int 需要写出 32 位,比较繁琐。而用十进制表示,又不容易明显地体现出补码的每一位,所以在程序设计中,常用十六进制来表示一个常数,这样只需要书写 8 个字符,每个字符(09,AF0\sim 9, A\sim F)代表补码下的 4 个二进制位。C++ 的十六进制常数以 0x 开头,0x 本身只是声明了进制,0x 后面的部分对应具体的十六进制数值。例如:

32 位补码 int(十进制) int(十六进制)
000000000000000000\cdots 000000 00 0x00x0
011111111111011111\cdots 111111 21474836472147483647 0x7FFFFFFF0x7F\thinspace FF\thinspace FF\thinspace FF
00111111重复400111111 重复4次 10611095671061109567 0x3F3F3F3F0x3F\thinspace 3F\thinspace 3F\thinspace 3F
111111111111111111\cdots 111111 1-1 0xFFFFFFFF0xFF\thinspace FF\thinspace FF\thinspace FF

上表中的 0x3F3F3F3F0x3F\thinspace 3F\thinspace 3F\thinspace 3F 是一个很有用的数值,它有两个特性:

  1. 它的两倍不超过 0x7FFFFFFF0x7F\thinspace FF\thinspace FF\thinspace FF,即 int 能表示的最大正整数。
  2. 整数的每 8 位(每个字节)都是相同的。

我们常用的 memset(a, val, sizeof(a)) 初始化一个 int 数组 aa 时,把 val(0x000xFF)val(0x00\sim 0xFF) 填充到数组 aa每个字节上,而一个 int 占用 4 个字节,所以用 memset 只能赋值出每 8 位都相同的 int。

所以,当我们想把一个数组中的数值初始化为正无穷时,为了避免加法上溢或者繁琐的判断,可以用 memset(a, 0x3f, sizeof(a)) 给数组赋 0x3F3F3F3F0x3F\thinspace 3F\thinspace 3F\thinspace 3F 的值。

移位运算

左移

在二进制表示下把数字同时向左移动,低位以 00 填充,高位越界后舍弃。

算术右移

在二进制补码表示下把数字同时向右移动,高位以符号位填充,低位越界后舍弃。

n>>1=n2.0n>>1 = \lfloor \frac{n}{2.0} \rfloor

注意,整数除法在 C++ 中的实现是向零取整(舍弃小数部分),例如 (3)/2=1(-3)/2=-13/2=13/2=1

逻辑右移

在二进制补码表示下把数字同时向右移动,高位以 00 填充,低位越界后舍弃。

无符号整数右移使用的是逻辑右移。对于有符号整数,在 C++ 20 前并没有规定使用算术右移还是逻辑右移(大多数平台上进行算术右移)。C++ 20 开始才规定使用算术右移。

参考资料