比特（bit），字节及整数

使用bit表示信息

所有的bit都是0或1的
使用bit的原因：电路易于存储双稳态的元素——低压表示0，高压表示1

二进制表示法

格式：数字+下标2，例如： 1110110110110 1 2 11101101101101_2 111011011011012​

字节（byte）

1字节=8 bits
在二进制上，从00000000 2 _2 2​到11111111 2 _2 2​
在十进制上，从0 10 _{10} 10​到255 10 _{10} 10​
在十六进制上，从00 16 _{16} 16​到FF 16 _{16} 16​

bit层级的运算

按位逻辑操作

真值为1，假值为0

与：A&B

&	0	1
0	0	0
1	0	1

或：A|B

|	0	1
0	0	1
1	1	1

非：~A

~
0	1
1	0

异或：A^B

^	0	1
0	0	1
1	1	0

上述运算均为按位运算，按位运算中，它们被视作bit向量进行运算
上述四种运算适用于一切整型（integral）数值类型，例如：long, int, short, char, unsigned…

与普通逻辑操作（例如&&, ||, !）不同。普通逻辑操作对整体进行运算，然后返回值为0或1

使用集合表示

长度为w的bit向量是{0, …, w-1}集合的子集，例如：01101001可以用集合表示为{0, 3, 5, 6}，表示第0/3/5/6位（从右往左）上值为1

使用集合表示时，&相当于交集，|相当于并集，^相当于并集减去交集，~相当于全集减去原有集合

移位操作

左移位：x<<y表示对bit向量x，向左移位y个位置，将左边的多余的字节省去，右边留下的空位补零。
例如：01100010<<3=00010000

右移位：x>>y表示对bit向量x，向右移位y个位置，将右边的多余的字节省去，左边留下的空位补零。
例如：10100010>>2=00101000

移位数不能超过此变量的bit总数

整数

整数的编码

无符号型： B 2 U ( X ) = ∑ i = 0 w − 1 x i ⋅ 2 i B2U(X)=\sum\limits_{i=0}^{w-1}x_i\cdot 2^i B2U(X)=i=0∑w−1​xi​⋅2i

二补数（Two’s Complement）： B 2 T ( X ) = − x w − 1 ⋅ 2 w − 1 + ∑ i = 0 w − 2 x i ⋅ 2 i B2T(X)=-x_{w-1}\cdot 2^{w-1}+\sum\limits_{i=0}^{w-2}x_i\cdot 2^i B2T(X)=−xw−1​⋅2w−1+i=0∑w−2​xi​⋅2i
其中， x w − 1 x_{w-1} xw−1​为符号位
对于二补数而言，许多符号位都以0表示非负，1表示负。例如：00111011 01101101表示十进制的15213，11000100 10010011表示十进制的-15213。

数值范围

无符号型： U M i n = 0 ,   U M a x = 2 w − 1 UMin=0,\ UMax=2^w-1 UMin=0, UMax=2w−1

二补数： T M i n = − 2 w − 1 ,   T M a x = 2 w − 1 − 1 TMin=-2^{w-1},\ TMax=2^{w-1}-1 TMin=−2w−1, TMax=2w−1−1

关系： ∣ T M i n ∣ = T M a x + 1 ,   U M a x = 2 ∗ T M a x + 1 |TMin|=TMax+1,\ UMax=2*TMax+1 ∣TMin∣=TMax+1, UMax=2∗TMax+1

符号与无符号之间的转换

T2B，B2U可以逆向变换为U2B，B2T（此映射是可逆的）

符号型与无符号型之间的转换，满足非负部分相等，负数部分（符号型）相差16的情况，如图1所示：

图1

从权重的角度来看，有符号型的最高位的权重是负值，而无符号位的最高位的权重是正值，如图2所示：

图2

在C语言中，有符号型和无符号型可以互相转换，无符号型在数字的最后加上U，例如：0U。
在两种类型同时出现时，会强制转换，有符号型会被强制转换为无符号型，例如：比较-1和0U的大小时，会将有符号型-1转换为无符号型，再与0U进行比较，结果是-1>0U

延伸与截断

符号延伸：将w-bit的有符号整数x转换为w+k-bit的相同值整数
规则：对符号位复制k次，得到 X ′ = x w − 1 , … , x w − 1 , x w − 2 , … , x 0 X'=x_{w-1},\dots,x_{w-1},x_{w-2},\dots ,x_0 X′=xw−1​,…,xw−1​,xw−2​,…,x0​
复制后保证只有最高位的权重为负，如图3所示：复制后，最高位的权重为-32，而原来的最高位的-16更新为正数16

图3

例如：短整型-15213的十六进制表示为C4 93，转换为整型后，字节数由2变至4，由于最高位的符号位1被复制，因此相应的十六进制表示变为FF FF C4 93

截断：将k+w-bit的有符号或无符号型整数X转换为w-bit的整数X’时，丢去最高的k位
如图4所示，截断有符号型的最高位时，如果最高位与第二高位相同，则截断后没有变化，反之则会发生变化

图4

加法运算

无符号型：计算结果超出最高位后会被截断，从而溢出： s = U A d d w ( u , v ) = ( u + v )   m o d   2 w s=UAdd_w(u,v)=(u+v)\ mod\ 2^w s=UAddw​(u,v)=(u+v) mod 2w
4-bit无符号型整数u,v的相加结果如图5所示：

图5

有符号型：分为负溢出和正溢出，如图6所示：

图6

正溢出： s u m ≥ 2 w − 1 sum\ge 2^{w-1} sum≥2w−1
负溢出： s u m < − 2 w − 1 sum<-2^{w-1} sum<−2w−1

T A d d w ( u , v ) = { u + v + 2 w ,   u + v < T M i n w u + v ,   T M i n w ≤ u + v ≤ T M a x w u + v − 2 w ,   T M a x w < u + v TAdd_w(u,v)=\left\{\begin{aligned} &u+v+2^w,\ u+v<TMin_w\\ &u+v,\ TMin_w\le u+v\le TMax_w\\ &u+v-2^w,\ TMax_w<u+v \end{aligned}\right. TAddw​(u,v)=⎩⎪⎨⎪⎧​​u+v+2w, u+v<TMinw​u+v, TMinw​≤u+v≤TMaxw​u+v−2w, TMaxw​<u+v​