用bits表示信息 Link to 用bits表示信息

在计算机中,一切都是bits 每个bit是0或1

• 为什么采用bit?
  • 易于存储
  • 在噪声和电线中传输可靠.例如,可以预设高电压表示1,低电压表示0,相比于十进制分成10份,这样的抗干扰能力肯定更强

数的二进制表示: 整数和浮点数的小数点左边是$2^0,2^1,2^2,...$
浮点数的小数点右边是$2^{-1},2^{-2},2^{-3},...$ 这样依次展开.

字节 Link to 字节

1byte = 8 bits 采用十六进制,一个字符相当于4 bits,所以一字节相当于2位十六进制数,从00到ff

c语言中的数据表示 Link to c语言中的数据表示


位运算 Link to 位运算

布尔代数 Link to 布尔代数

1. 与 and

2. 或 or

3. 非 not

~| —|— 0|1 1|0

4. 异或 Xor

位移运算 Link to 位移运算

1. 左移 << 去掉左边多余的位，右边低位填0
2. 右移 >> 去掉右边多余的位，

• 对于逻辑位移: 左边填0
• 对于算术位移: 填左边的标志位,即 正数:都是填0 负数的补码:高位填1

4. 未定义的行为 移动的位数小于0或者大于字长(可能是移动取模后的位数)

整数的表示 Link to 整数的表示

编码整数 Link to 编码整数

• 对于unsigned类型 $Bit2Unsigned(X) = \sum_{i=0}^{w-1} x_i \cdot 2^{i}$ 比如说,对于 $(1101)_2 = 2^0+2^2+2^3 = 1+4+8=13$
• 对于二进制补码 (Two’s Complement) $Bit2T(X) = -x_{w-1}\cdot 2^{w-1} + \sum_{i=0}^{w-2} x_i \cdot 2^{i}$ 比如说,对于 $(1101)_2 = 2^0+2^2-2^3 = 1+4-8=-3$ 最高位是符号位,0表示非负数,1表示负数

数值范围 Link to 数值范围

• 对于unsigned类型 $UMin = 0$ $000...0$ $UMax = 2^{w}-1$ $111...1$
• 对于二进制补码 $TMin = -2^{w-1}$ $100\dots 0$ $TMax = 2^{w-1}-1$ $011\dots 1$ 特别地,$111...1_{2}= -1$

相互转换 Link to 相互转换

我们可以发现他们之间存在一一对应的函数关系 首先是反函数的关系: $U2B(X) = B2U^{-1}(X)$ $T2B(X) = B2T^{-1}(X)$ 其次是Signed和Unsigned之间的关系 

• 总结:在C语言中,signed和unsigned相互转换的规则
  • 位保持不变
  • 数值被重新阐述
  • 可能有意想不到的效果:加上或减去$2^w$
  • 当表达式含有signed和unsigned类型的时候,signed会发生强制转换成unsigned

字长拓展 Link to 字长拓展

 比如说,对于一个signed类型4比特整数,拓展成8比特长 $(-6)_{10}=(1010)_{2}=(11111010)_{2}$ $(4)_{10}=(0100)_{2}=(00000100)_{2}$

字长截断 Link to 字长截断

对unsigned类型截短即取模运算 $(11010)_{2} \ \ mod \ \ 2^4 = (1010)_{2}$ 对signed类型截短也类似于取模运算,有时会把正数变成负数,有时会把负数变成正数

总结: Link to 总结:

• 拓展
  • unsigned类型:填0
  • signed类型:填符号位
• 截断
  • unsigned类型:取模
  • signed类型:类似于取模

四则运算 Link to 四则运算

加法 Link to 加法

1. unsigned类型加法需要w+1位来完整存储,但这会造成溢出,所以舍去溢出位,即取模 $UAdd_{w}(u,v) = (u+v) \ \ mod \ \ 2^{w}$

   很喜欢的可视化: 

2. 补码的加减法 同样舍去溢出位,会导致负溢出和正溢出(下溢和上溢)

   • 负溢出 两个负数的和小于TMin,会变成正数
   • 正溢出 两个正数的和大于TMax,会变成负数 所以,对于以下这两段代码:

   C

   Copy to clipboard

   1
   2
   3

   unsigned i;
   for (i = cnt-2; i >= 0; i--) 
   	a[i] += a[i+1];
   

   及

   C

   Copy to clipboard

   1
   2
   3
   4
   5

   #define DELTA sizeof(int) 
   int i; 
   for (i = CNT; i-DELTA >= 0; i-= DELTA) 
   	. . .
   
   

   都会发生异常! 正确的做法是

   C

   Copy to clipboard

   1
   2
   3

   unsigned i; 
   for (i = cnt-2; i < cnt; i--) 
   	a[i] += a[i+1];
   

   精益求精的是

   C

   Copy to clipboard

   1
   2
   3

   size_t i; 
   for (i = cnt-2; i < cnt; i--) 
   	a[i] += a[i+1];
   

   如果cnt是signed类型并且小于0会怎样?

   很喜欢的可视化: 加上负数,就是减法 计算相反数:先取反,再加1 $-x=\ \sim x + 1$

乘法 Link to 乘法

1. unsigned类型的乘法需要2w位来完整存储,但这会造成溢出,所以舍去溢出位,即取模 $UMult_{w}(u,v) = (u \cdot v) \ \ mod \ \ 2^{w}$

2. signed类型的乘法同样,直接舍去溢出位,有时这会导致正数相乘变负数

举一个有趣的例子: $(1101)_{2} \ \ \ \ \ \ (signed \ \ -3/unsigned \ \ 13)$ $(1110)_{2} \ \ \ \ \ \ (signed \ \ -2/unsigned \ \ 14)$ $(1101)_{2} \cdot (1110)_{2}= (1011 \ \ \ 0110)_{2}$ 低4位是 0110,在unsigned中为 6. 所以,在计算13*14的低4位时,可以作unsigned算

特别地, $u\ll k == u \cdot 2^k$ 通常,计算机移位比乘法快得多,编译器会自动比较选择最快的方式: $u\ll 5 - u \ll 3 == u * 24$ 相似地, 对于unsigned类型: $u\gg k == \left\lfloor \frac{u}{2^k} \right\rfloor$ 对于signed类型使用算术移位

在内存,指针,字符串中的表示 Link to 在内存,指针,字符串中的表示

面向字节的内存组织 Link to 面向字节的内存组织

程序通过地址访问数据,地址就像数组的索引 系统给每个程序提供私有地址空间

字长 Link to 字长

字长是计算机惯常处理的数值大小以及地址的大小 所以,32位计算机的地址局限是4GB(2^ 32 bytes) 64位计算机可以有18EB的地址内存 硬件和编译器共同决定在某个程序中使用多大的字长,这提供了一些兼容性

大端序和小端序 Link to 大端序和小端序

按照多字节数据在存储器中的存储顺序分为大端序和小端序 大端序设备:某些互联网设施 小端序设备:x86,ARM处理器 大端序:低位存储在高地址 小端序:低位存储在低地址  检查数据在内存中的存储顺序:

1
2
3
4
5
6
7
8
9
10
11
12

typedef unsigned char *pointer; 
void show_bytes(pointer start, size_t len){ 
	size_t i; 
	for (i = 0; i < len; i++) 
		printf(”%p\t0x%.2x\n",start+i, start[i]);  // %p:打印指针,%x:打印十六进制数
	printf("\n"); 
}

			   
int a = 15213; 
printf("int a = 15213;\n"); 
show_bytes((pointer) &a, sizeof(int));

结果(Linux x86-64):

1
2
3
4
5
6

int a = 15213; 
0x7fffb7f71dbc 6d 
0x7fffb7f71dbd 3b 
0x7fffb7f71dbe 00 
0x7fffb7f71dbf 00