整数的表示与处理

录制文件: record/talk-2.mp4

这一节简单地讨论整数的表示与处理. Programmers 64-bit Calc 是一个很好的在线工具, 可以用来查看有符号整数与无符号整数的二进制表示, 以及它们的位运算.

无符号整数

无符号整数只能表示非负整数. 计算机中无符号整数的表示方法建立了二进制数据与非负整数的双射关系.

我们记一个 $w$ 位的二进制数为一个长度为 $w$ 的向量, 最高位在前:

$$\vec{x}=(x_{w-1},x_{w-2},\ldots,x_0), x_i=0,1$$

记函数 $B2U_w$ 将一个二进制数解读为无符号整数:

$$B2U_w (\vec{x})\coloneqq \sum_{i=0}^{w-1}x_i 2^i$$

例如, $B2U_4(1101)=8+4+0+1=13$.

有符号整数

有符号整数可以表示正整数, 负整数和零. 计算机中有符号整数的表示方法建立了二进制数据与整数的双射关系.

最通用的有符号整数表示方法是补码. 一个 $w$ 位的补码数的最高位是符号位, 0 表示正数, 1 表示负数. 负数的补码是对应正数的补码取反加一.

记函数 $B2T_w$ 将一个二进制数解读为有符号整数:

$$B2T_w (\vec{x})\coloneqq -x_{w-1}2^{w-1}+\sum_{i=0}^{w-2}x_i 2^i$$

例如, $B2T_4(1101)=-8+4+1=-3$.

大小端

在计算机中, 一个多字节的对象在内存中的存储顺序有两种: 大端序 (big-endian, 也称网络序) 和小端序 (little-endian).

例如, 一个 4 字节的整数 0x01234567 在内存中的存储顺序如下:

• 大端序: 01 23 45 67
• 小端序: 67 45 23 01

上面用到了 16 进制表示法, 用 0-9 和 A-F 表示 0-15.

正常情况下, 不用关心大小端序, 例如对于整数的位移, 位运算等操作, 编译器会自动处理大小端序的问题.

如果手动查看内存中的数据, 需要注意大小端序的问题. 例如:

#include <stdio.h>
int main() {
    int x = 0x01234567;
    char *p = (char *)&x;
    for (int i = 0; i < sizeof(x); i++) {
        printf("%02x ", p[i]);
    }
    return 0;
}

关于 printf 函数的格式化控制符 %02x, %x 表示输出 16 进制数, %02x 限定不足两位用 0 补齐.

可以参考 Format Specification Syntax | Microsoft Learn 来查看更多的格式化控制符.

逻辑运算

在 C 中, 任何非零的整数都被视为 true, 零被视为 false.

产生 true 或 false 的运算符有 == (等于), != (不等于), > (大于), < (小于), >= (大于等于), <= (小于等于).

逻辑运算常用于条件判断, 对 true 或 falase 进行逻辑运算符的运算符有 ! (非), && (与), || (或).

下面用真值表表示逻辑运算符的运算规则:

例子

三目运算符 ?: 可以用来简化条件判断. 例如, 下面的代码用来计算两个数的最小值, 并在最小值为负数时返回 0.

int non_negative_min(int x, int y) {
    int is_negative = x < 0 || y < 0;
    return is_negative ? 0 : x < y ? x : y;
}

位运算

位运算符有 & (与), | (或), ^ (异或), ~ (取反), << (左移), >> (右移).

下面用真值表表示位运算符的运算规则:

左移和右移是移位运算符, 用来将一个数的二进制表示向左或向右移动若干位.

• 左移始终将空出的位补 0.
• 右移有两种方式: 逻辑右移和算术右移.
  • 逻辑右移将空出的位补 0.
  • 算术右移将空出的位填充为原先的最高位.

无符号数的右移必须被实现为逻辑右移, 有符号数的右移在绝大多数平台上被实现为算术右移.

思考题

下面这个 C 函数的功能是什么?

 int f(int x) {
     int a = x | (~x + 1);
     return (a >> 31) + 1;
 }