整数的机器表示
# 整数的机器表示
# 预备知识
# 字,字节,比特
转换关系
- 1 word(字) = 2 byte(字节) = 16 bit(比特)
- 1 个比特 = 1 个二进制位
# 常用的储存容量与比特之间的换算
换算关系
比特(bit) | |||||
---|---|---|---|---|---|
储存容量 | 1 KB | 1 MB | 1 GB | 1 TB | 1 PB |
# 数制
常用数制
数制 | 基数 | 数码 |
---|---|---|
二进制 Binary | 2 | 0, 1 |
八进制 Octal | 8 | 0, 1, 2, 3, 4, 5, 6, 7 |
十进制 Decimal | 10 | 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 |
十六进制 Hexadecimal | 16 | 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F |
# 数制之间的转换
常用的数制转换
数字末尾的 H 表示十六进制, O 表示八进制, B 表示二进制
# 十六进制数的加减法
基本规则:逢十六进一,借一当十六
# 逻辑运算(二制数按位操作)
"与"运算(AND)
"或"运算(OR)
"非"运算(NOT)
"异或"运算(XOR)
计算示例
# 数的机器表示
# 机器字长(Machine word)
定义
- 一般指计算机进行一次整数运算所能处理的二进制数据的位数
- 通常也包括数据地址长度
常用的机器字长
- 32 位字长
- 地址的表示空间, 4 GB
- 64 位字长
- 地址的表示空间约是
bytes - 目前 x86-64 支持 48 位宽的地址: 256 TB
- 地址的表示空间约是
# 机器字在内存中的组织
地址按照字节 (byte) 来定位
- 机器字中第一个字节的地址
- 相邻机器字的地址相差4(32-bit)或者8(64-bit)
示意图
# 大端字节序与小端字节序
描述一个机器字内各个字节的排列方法
- Big Endian, 大端字节序,
- 低位字节占据高位地址,与人类阅读顺序相同
- 应用:Sun, PowerPC, Internet
- Little Endian, 小端字节序
- 低对低,高对高
- 常用的字节序,与人类阅读顺序相反
示意图
两种字节序对性能基本没有影响
示例
# 整数表示
C 语言中基本数据类型的大小(Bytes)
# 无符号数
二进制数到无符号数的转换
- 其中
为字长 - 表示范围:
- 对于 32 位字长,
- 对于 32 位字长,
# 有符号数(补码)
二进制数到有符号数的转换
- MSB(Most Significant Bit) 表示整数的符号位(sign bit)
- 0 为正
- 1 为负
- 取值范围
- 对于 32 位机器,其范围为
- 全 1 表示 -1
示例
short int x = 15213;
short int y = -15213;
1
2
2
Decimal | Hex | Binary | |
---|---|---|---|
x | 15213 | 3B 6D | 00111011 01101101 |
y | -15213 | C4 93 | 11000100 10010011 |
在有符号数不溢出的情况下,负数的补码等于正数的补码取反后加 1; 正数的补码为其本身
- 具体可由上述定义的
和 推出
# 无符号数和有符号数之间的转换
是十进制表示的转换,其二进制串的表示是不变,相当于是编译器对同一内存块的不同解释
- 相当于把符号数的负数等距的偏移为无符号数
示意图
# C 语言中的无符号数与有符号数
常数(constant)默认是有符号数,如果有 U 作为后缀,则是无符号数
如果无符号数与有符号数混合使用,则有符号数默认转换为无符号数
# 何时采用无符号数
不能仅因取值范围非负而使用,能用有符号数,就用有符号数
错误示例1:
unsigned i
for (i = cnt-2; i >= 0; i--)
a[i] += a[i+1];
1
2
3
2
3
错误示例2:
#define DELTA sizeof(int)
int i;
for (i=CNT; i - DELTA >=0; i -= DELTA)
...
1
2
3
4
2
3
4
sizeof
的返回值为无符号数
# 无符号数加法
计算公式
均为 位的无符号数 - 溢出后直接舍弃进位
# 补码加法
# 补码加法的溢出
溢出后正得负,负得正,相当于等距平移
- 要从二进制加法的角度用时借助
的计算公式去理解- 要注意
都是 位的数
- 要注意
- 只有正正相加才会正溢出
- 正溢出后使得符号位由零变 1 ,整体会变为负数,十进值上值减小
- 正溢出后使得符号位由零变 1 ,整体会变为负数,十进值上值减小
- 只有负负相加才会负溢出
- 负溢出后,符号位溢出,导致原本符号位变为0,整体会变为正数,十进制上值增加了
- 负溢出后,符号位溢出,导致原本符号位变为0,整体会变为正数,十进制上值增加了
示意图
# 无符号整数除以 2 的 k 次幂
实现方法
- 逻辑右移可理解为将
乘以 ,然后舍掉最后的 位,相当于整数变小,即为向下取整
图示
- 逻辑右移可理解为将
# 有符号除以 2 的 k 次幂
直接采用算术右移存在的问题
- 采用算术右移
时,会出现舍入错误- 即结果为负数时,向下取整,而不是向
取整 - 理解基本与无符号数一致,从
公式的定义入手- 算术右移在首位补上的 k 个 1, 可以将
变为 ,达到了除以 的效果 - 其余各正数项都是相当于乘了
后,再舍掉最后 位的一部分小数,由于舍掉的可能存在正数,会导致整体变小,相当于向下取整
- 算术右移在首位补上的 k 个 1, 可以将
图示
- 即结果为负数时,向下取整,而不是向
实现向零取整
- 为了修正负数时除法不向0取整的问题,当
时,按照下式计算- 在 C 中可表示为
(x + (1<<k) - 1) >> k
- 相当于加上一个二进制最后
位全为 1 的数
具体分析时,可分为原本没有舍入,和原本有舍入两种情况
- 完全没有舍入时,加入的项完全被移出,不影响结果
- 原本有舍入时,加入的项会导致在第
位产生进位操作,相当于将最后的结果加 1,将负数的向下取整变为了向零取整
- 在 C 中可表示为
编辑 (opens new window)