本次笔记内容：
03.整数的计算机表示与运算

文章目录

• • • 预备知识
    • 数制
    • • 数的机器表示
      • 机器字在内存中的组织
      • 字节序（Byte Ordering）
    • 整数表示
    • • 计算机中整数的二进制编码方式
      • 无符号数与带符号数
      • • 范围
        • 转换
        • C语言中的无符号数和带符号数
        • 何时采用无符号数
        • 加法
        • 无符号整数除以2的k次幂
        • 带符号整数除以2的k次幂
    • Integer C Puzzles
    • • x<0 infer ((x*2)<0)
      • ux>=0
      • x & 7 == 7 infer (x<<30)<0
      • ux > -1
      • x > y infer -x < -y
      • x * x >= 0
      • x > 0 && y > 0 infer x + y > 0
      • x >= 0 infer -x <= 0
      • x <= 0 infer -x >= 0
      • (x|-x)>>31 == -1
      • ux>>3 == ux/8
      • x >> 3 == x/8
      • x & (x-1) != 0
    • 另一道练习题

预备知识

• 1K = 2^10 = 1024 (Kilo)
• 1M = 1024K =2^20 (Mega)
• 1G = 1024M = 2^30 (Giga)
• 1T = 1024G = 2^40 (Tera)
• 1P = 1024T = 2^50 (Peta)
• 1个二进制位：bit (比特)
• 8个二进制位：Byte (字节) 1 Byte = 8 bit

注意在存储领域，不是以1024进位的，是以1000进位的。

在x86中，默认一个Word为16个比特：

• 2个字节：Word (字)
• 1 Word = 2 Byte = 16 bit

数制

数的机器表示

机器字（machine word）长：

• 一般指计算机进行一次整数运算所能处理的二进制数据的位数；
• 通常也包括数据地址长度。
• 32位长：
• • 地址的表示空间是4GB；
• • 对很多内存需求量大的应用而言，非常有限。
• 64位字长：
• • 地址的表示空间的是1.8 × 10^19 bytes；
• • 目前的x86-64机型实际支持48位宽的地址：256 TB。

机器字在内存中的组织

地址按照字节（byte）来定位：

• 机器字中第一个字节的地址；
• 相邻机器字的地址相差4（32-bit）或者8（64-bit）。

字节序（Byte Ordering）

一个机器字内的各个字节如何排序？

• 很不幸，历史上没有过强制一统的标准，有从高位开始的，也有从地位开始的。

Big Endian：Sun，PowerPC，Internet

• 低位字节（Least significant byte, LSB）占据高地址；

Little Endian：x86

• 与LSB相反

例子如下。

0x100	0x101	0x102	0x103
01	23	45	67
67	45	23	01

如上，要存储数值为0x01234567的数，上面是LSB，下面是x86的存储方式。

socket就有将本地字节序与网络字节序的功能。

再举一个例子：

Decimal: 15213
Binary: 0011 1011 0110 1101
Hex: 3 B 6 D

对于以下三种实现：

int A = 15321;
int B = -15213;
long int C = 15213;

在IA32, x86-64, Sun设备上的存储分别为：

整数表示

C语言中基本数据类型的大小（in Bytes）：

C Data Type	Typical 32-bit	x86-32	x86-64
char	1	1	1
short	2	2	2
int	4	4	4
long	4	4	8
long long	8	8	8
float	4	4	4
double	8	8	8
long double	8	10/12	10/16
char * or any other pointer	4	4	8

计算机中整数的二进制编码方式

w表示字长，对于无符号数： B 2 U ( X ) = ∑ i = 0 w − 1 x i ⋅ 2 i B2U(X) = \sum^{w-1}_{i=0} x_i \cdot 2^i B2U(X)=i=0∑w−1​xi​⋅2i

对于带符号数（补码，Two’s Complement）： B 2 T = − x w − 1 ⋅ 2 w − 1 + ∑ i = 0 w − 2 x i ⋅ 2 i B2T = -x_{w-1} \cdot 2^{w-1} + \sum^{w-2}_{i=0} x_i \cdot 2^i B2T=−xw−1​⋅2w−1+i=0∑w−2​xi​⋅2i

对于下列实现：

short int x = 15213;
short int y = -15213;

其存储为：

	Decimal	Hex	Binary
x	15213	3B 6D	00111011 01101101
y	-15213	C4 93	11000100 10010011

对于负数（补码），即取反再加一。

符号位（sign bit）：

• 对于补码表示，MSB（Most Significant Bit）表示整数的符号；
• 0 for nonnegative；
• 1 for negative。

无符号数与带符号数

范围

在带符号数中，负数范围个数总比整数范围个数多1，举例：

• 00000000表示0；
• 00000001表示1；
• 01111111表示127；
• 10000001表示-127（按位取反再加1）。
• 10000000表示-128（不能用按位取反表示，因为不存在正128，可以理解为-127-1）

转换

无符号数与带符号数之间的转换：

• 二进制串的表示是不变的。

上图为无符号数和带符号数的关系。

C语言中的无符号数和带符号数

常数（Constants）：

• 默认是带符号数，如果有U作为后缀则是无符号数，如0U，4294967259U；

如果无符号数与带符号数混合使用，则带符号数默认转换为无符号数，包括比操作符。

下面是例题，比较常数1和常数2的关系：

Constant_1	Constant_2	Relation	Evaluation
0	0U	==	unsigned
-1	0	<	signed
-1	0U	>	unsigned
2147483647	-2147483647-1	>	signed
2147483647U	-2147483647-1	<	unsigned
-1	-2	>	signed
(unsigned) -1	-2	>	unsigned
2147483647	2147483648U	<	unsigned
2147483647	(int) 2147483648	>	signed

将负的带符号数转换为无符号数时，总比正的带符号数大，可以参考上面的映射示意图。

何时采用无符号数

建议：不能仅仅因为取值范围是非负而使用。只在两种情况使用：

• 模运算
• 按位运算

不能乱用unsigned的例子：

// example I
unsigned i;
for (i = cnt - 2; i >= 0; i--)
	a[i] += a[i+1];
// 永远无法结束，i恒大于等于0
// example II
#define DELTA sizeof(int)
int i;
for (i = CNT; i-DELTA >= 0; i-= DELTA)
	...
// sizeof()返回unsigned，而i-=DELTA运算后，i被转换为unsigned，导致for无法退出

加法

无符号数和带符号数（补码）加法所用的x86机器指令都是同一条类型。加法就是两个位串加起来。

无符号整数除以2的k次幂

在编译时，如果遇到无符号整数除以2的k次幂，不调用除法指令（硬件的除法非常慢），而调用逻辑右移。

u >> k gives ⌊ u / 2 k ⌋ \lfloor u / 2^k \rfloor ⌊u/2k⌋

// C Function
unsigned udiv8(unsigned x)
{
	return x / 8;
}
// Compiled Arithmetic Operations
shrl	$3, %eax
// Explanation
# Logical shift
return x >> 3;

带符号整数除以2的k次幂

u >> k gives ⌊ u / 2 k ⌋ \lfloor u / 2^k \rfloor ⌊u/2k⌋

但是如果 x < 0 x < 0 x<0，出现舍入错误。

解决方案：

• Want ⌈ x / 2 k ⌉ \lceil x / 2^k \rceil ⌈x/2k⌉（需要向0舍入，而不是向下舍入）
• （对于负数而言）Compute as ⌊ ( x + 2 k − 1 ) / 2 k \lfloor (x + 2^k -1) / 2^k ⌊(x+2k−1)/2k
• In C: (x + (1<<k) - 1) >> k （即做一个偏移处理）
• Biases dividend toward 0

// C Function
int idiv8(int x)
{
	return x / 8;
}
// Compiled Arithmetic Operations
	testl	%eax, %eax
	js		L4
L3:
	sarl	$3, %eax
	ret
L4:
	addl	$7, %eax
	jmp		L3
// Explanation
# Logical shift
if x < 0
	x += 7;
# Arithmetic shift
return x>>3;

Integer C Puzzles

int x = foo();
int y = bar();
unsigned ux = x;
unsigned uy = y;

x<0 infer ((x*2)<0)

不对，可能溢出。

ux>=0

对。

x & 7 == 7 infer (x<<30)<0

对。

7即111，x & 7 == 111，即x低位的3位为111。

x是int类型（32位），111向左移30位，则符号位为1，是负数。

ux > -1

不对，ux一定是小于等于-1的（-1转换为unsigned后，大）。

x > y infer -x < -y

不对，因为不一定。负数的表示范围比正数大1，若y为-128，推论将不成立。

x * x >= 0

不对，可能溢出，高位被截断。

x > 0 && y > 0 infer x + y > 0

不对，可能溢出。

x >= 0 infer -x <= 0

对。

x <= 0 infer -x >= 0

不对，-128为反例。

(x|-x)>>31 == -1

不对，0位反例。

ux>>3 == ux/8

对。

x >> 3 == x/8

不对，负数为反例。

x & (x-1) != 0

不对，x取0为反例。

另一道练习题

已知某32位整数X，其值为-101，则其16进制补码为（0xFFFFFF9B），另一32位整数Y的补码为0xFFFFFF6A，则X+Y的16进制补码（32位）为（0xFFFFFF05），X-Y的16进制补码为（0x31）。

解：

• -101，写出其绝对值（101）2进制串，按位取反，加1；
• 对于第二、三个空，转为10进制运算，按位取反加一即可。