文章目录
- 计算机系统漫游
- 信息的表示和处理
-
- 信息存储
-
- 数字革命的基础——二值信号
- 信息存储
- 十六进制表示法的妙用
- 字数据大小
- 寻址和字节顺序
- 表示字符串
- 布尔代数简介
- C语言逻辑运算和移位运算
- 整数表示
-
- 无符号编码的定义
- **深度为k的满二叉树的结点数计算，可以理解为k位且数位都是1的无符号数，计算它表示的大小**
-
- 补码编码的定义
- 补码转成无符号数
- 无符号数转换成补码
- 无符号数加法
- 无符号数取反[加法逆元(`$-^u_w $`)]
- 补码加法
- 补码加法溢出函数
- 补码的非[加法逆元(`$-^t_w$`)]
- 无符号乘法
- 补码乘法
- 乘以常数
- 除以2的幂的无符号除法
- 除以2的幂的补码除法
- 浮点数
计算机系统漫游
bss段(bss segment)——静态内存分配
Block started by Symbol
通常是指用来存未初始化的全局变量的内存区域。
data段——动态内存分配(data segment)
通常是指用来存放程序中已被初始化的全局变量的内存区域。
text段(code segmet/text segment)
通常是指用来存放程序执行代码的内存。
堆（heap）
进程运行中被动态分配的内存段，malloc等函数分配内存（扩张堆）。
free函数释放内存（堆缩减）
栈（stack)
用户创建的局部变量，函数体中定义的变量（但不包括static声明的变量=>data segment）
信息的表示和处理
信息存储
数字革命的基础——二值信号
在构造存储和处理信息的机器时，二值信号能够很容易地被表示、存储和传输，例如，可以表示为穿孔卡片上的有洞或无洞、导线上的高电压和低电压，或者顺时针和逆时针的磁场。
二值信号的电子电路简单和可靠，制造商能够在一个单独的硅片上集成数百万甚至数十亿个这样的电路。
孤立的讲，单个的位(二进制数字)意义不大。然而，当把位组合在一起，再加上某种解释(interpretation)，即赋予不同的可能位模式以含意，我们就能够表示任何有限集合的元素。
信息存储
C语言中一个指针的值都是某个存储块的第一个字节的虚拟地址(c编译器会将类型信息与之联 系起来)。
- 大多数计算机使用8位的块，或者字节(byte)，作为最小的可寻址的内存单位，而不是访问内存中单独的位。
- 内存的每个字节都由一个唯一的数字来表示，称为它的地址(adress)，地址们在虚拟地址空间里。
十六进制表示法的妙用
二进制表示法太冗长，而十进制表示法与位模式互相转化太麻烦。16进制数以16做基数，以0X或0x开头。
| 基数 | 含义 | |||||
|---|---|---|---|---|---|---|
| 十六进制 | $2^4$ |
1 | 7 | A | F | 4位二进制数字做一位数 |
| 二进制 | $2^1$ |
0001 | 0111 | 1010 | 1111 | 1位二进制数字做一位数 |
将一个2的非负整数n次幂进行十六进制转换：
当x=2^n,可将n表示为i+4j的形式，\\例如x=2047=2^{11}=2^{8+3}=2^{3+4*2}，\\得到十六进制数\\0x800
字数据大小
每台计算机都有一个字长(word size)，字长决定的最重要的系统参数就是虚拟地址空间的最大大小。
因为虚拟地址是以这样的一个字来编码，对一个字长为w位的机器而言，虚拟地址的范围就是0~$2^w-1$,程序最多访问$2^w$个字节。
寻址和字节顺序
对于跨越多字节的程序对象，需要了解这个对象的地址是什么，以及在内存中如何排列这些字节。
在几乎所有的机器中，多字节对象都被存储为连续的字节序列，对象的地址为++所使用字节中最小的地址++。
- 如何排列这些字节？
- [
$x_{w-1}$,$x_{w-2}$，…，$x_1$,$x_0$],$x_{w-1}$是最高有效位，$x_0$是最低有效位。- 小端法——最低有效字节在最前面
- 大端法——最高有效字节在最前面
- 字符串是个例外。。。
| x=0x01234567 | … | 0x100 | 0x101 | 0x102 | 0x103 | … |
|---|---|---|---|---|---|---|
| 大端法 | 高有效位 | |||||
| … | 01 | 23 | 45 | 67 | … | |
| 小端法 | 低有效位 | |||||
| … | 67 | 45 | 23 | 01 | … | |
| char*p=(char*)&p; | p[0] | p | p[1] | *(p+2) | %.2x |
//打印程序对象的字节表示，使用强制转换。
#include<stdio.h>
typedef unsigned char* byte_pointer;//show_bytes打印出每个以十六进制表示的字节。
void show_bytes(byte_pointer start,size_t len){//size_t就是unsigned intsize_t i;for(i=0;i<len;i++){printf("%.2x",start[i]);//至少两个数字的十六进制格式输出}printf("\n");
}void show_int(int x){//测试一个int的数据，逐个字节访问，得出字节排列的顺序show_bytes((byte_pointer)&x,sizeof(int));
}void show_pointer(void *x){//任意类型、无类型指针xshow_bytes((byte_pointer)&x,sizeof(void*));
}
表示字符串
字符串是以’\0’结尾的字符数组。
int main(){show_bytes("12345",6);//包括结束符'\0',输出 31 32 33 34 35 00//十进制数字的十六进制表示是0x3x。const char* s="abcdef";show_bytes((bytes_pointer)s,stelen(s));//不包括'\0'，输出 61 62 63 64 65 66//const类型强转为普通类型，strlen(s)是有效字符的长度。
}
在使用ASCII码作为字符码的任何系统上都将得到相同的结果，与字节顺序和字大小规则无关。
因而，文本数据比二进制数据具有更强的平台独立性。
ASCII字符集适合于编码英文文档，
Unicode——“统一字符集”，使用32位来表示字符，但可以利用某些编码规则灵活使用存储空间，例如UTF-8编码会用一个字符保存ASCII字符，多字节存储汉字。
编码那点事,带你了解什么是GB2312、GBK、GB18030。
二进制代码很少能在不同机器和操作系统组合之间移植。
布尔代数简介
最简单的布尔代数式在二元集合{0,1}基础上的定义，我们用来表示这些运算的符号与C语言位级运算使用的符号是相匹配的。
包括NOT、AND、OR、EXCLUSIVE-OR
取反
| ~ | |
|---|---|
| 0 | 1 |
| 1 | 0 |
并
| & | 0 | 1 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
与
| | | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 1 |
亦或：无进位相加
| ^ | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
将布尔代数拓展位数，依然成立。
另外，布尔代数和整数算数运算有很多相似之处。
- & 对 | 的分配率
a\&(b|c)=(a\&b)|(a\&c)
- | 对 & 的分配率。
a|(b\&c)=(a|b)\&(a|c)
- ^的逆元(加法逆元：x+(-x)=0,x与-x互为逆元)
a异或的逆元是他本身
| ^逆元 | 重组 | 推导 |
|---|---|---|
| a^a=0 | (a^b)^a=b | (a^a)^b=0^b=b |
C语言逻辑运算和移位运算
- 逻辑运算
逻辑运算符&&和||与它们对应的&和|之间第二个重要的区别是，如果对第一个参数求值就能确定表达的结果，那么逻辑运算符将不再对第二个参数求值。
| 被零除 | 空指针 |
|---|---|
| a&&5/a | p&&*p++ |
- 移位运算
- 左移：在右端补0
- 逻辑右移和算术右移
| 右移运算>> | 左移运算<< | |
|---|---|---|
| 无符号数 | 逻辑右移 | 右补0 |
| 有符号数 | ++算术右移++ | 右补0 |
| 正数 | 左补0 | 右补0 |
| 负数 | ++左补1++ | 右补0 |
当移动一个w位的值，移位量为k % w。
整数表示
| 符号 | 类型 | 含义 |
|---|---|---|
$B2T_w$ |
函数 | 二进制数转补码 |
$B2U_w$ |
函数 | 二进制->无符号 |
$U2B_w$ |
函数 | 无符号->二进制 |
$U2T_w$ |
函数 | 无符号->补码 |
$T2B_w$ |
函数 | 补码->二进制 |
$T2U_w$ |
函数 | 补码->无符号 |
$TMin_w$ |
常数 | 最小补码值 |
$TMax_w$ |
常数 | 最大补码值 |
$UMax_w$ |
常数 | 最大无符号数 |
$+^t_w$ |
操作 | 补码加法 |
$+^u_w$ |
操作 | 无符号数加法 |
$*^t_w$ |
操作 | 补码乘法 |
$*^u_w$ |
操作 | 无符号数乘法 |
$-^t_w$ |
操作 | 补码取反 |
$-^u_w$ |
操作 | 无符号数取反 |
无符号编码的定义
深度为k的满二叉树的结点数计算，可以理解为k位且数位都是1的无符号数，计算它表示的大小
C/C++都支持有符号（默认）和无符号数，Java只支持无符号数。
- 无符号数编码的唯一性
- 函数
$B2U_w$是一个双射。
B2U_w(\vec x) \doteq \sum_{i=1}^{w-1}{x_i2^i}
- 要创建一个无符号常量，必须要加上后缀字符‘U’或‘u’。
- 隐式发生的转换：当一个运算数是无符号时的时候，另一个运算数也被隐式强制转换为无符号。
补码编码的定义
将最高位解释为负权，这样可以表示负值。
- 补码编码的唯一性
- 函数
$B2T_w$是一个双射。
B2T_w(\vec x)\doteq -x_{w-1}2^{w-1}+ \sum_{i=0}^{w-2}x_i2^i
| 1011 | -8+3 |
|---|---|
| 负数：-5 | 最大负数(1000)往回推(0011)个 |
| > 为什么 | TMin |
之所以有这样的不对称性，是因为一半的位模式(符号位设置为1的数)表示负数，而另一半(符号位设置为0的数)表示非负数。因为0是非负数，也就意味着能表示的正数比负数小一个。
为什么最大无符号数值刚好比补码的最大值的两倍大一点：
$UMax_w$=$2TMax$+1因为所有表示负数的位模式在无符号表示中都变成了正数，最高位的权是次高的两倍。
补码转成无符号数
对满足TMin_w\leq x\leq TMax_w的x有\\T2U_w(x)=
\begin{cases}
x+2^w, & x<0\\
x, & x\geq 0
\end{cases}
无符号数转换成补码
对满足0\leq u\leq UMax_w的x有\\U2T_w(u)=
\begin{cases}
u, & u\leq TMax_w\\
u-2^w, & u>TMax_w
\end{cases}
无符号数加法
算术运算溢出：指完整的整数结果不能放到数据类型的字长限制中去。
对满足0\geq x,y<2^w的x和y有：\\x+^u_wy=\\
\begin{cases}
x+y, & x+y<2^w 正常\\
x+y-2^w, & 2^w\leq x+y<2^{w+1} 溢出
\end{cases}
无符号数取反[加法逆元($-^u_w $)]
对满足 0\leq x<2^w的任意x，其w位的无符号逆元-^u_w由下式给出\\-^u_wx=\\
\begin{cases}
x, & x=0\\
2^w-x, & x>0
\end{cases}
补码加法
两个数相加，如果原数(原码)相加在正常的范围内，则发生的溢出和截断都不影响结果，补码的加法也会得到正确的结果。
正溢出和负溢出的补码加法截断后产生错误的结果。
对满足-2^{w-1}\leq x,y\leq 2^{w-1}-1的整数x和y，有:\\x+^t_wy=\\
\begin{cases}
x+y-2^w, & 2^{w-1}\leq x+y & 正溢出\\
x+y, &-2^{w-1}\leq x+y<2^{w-1} & 正常\\
x+y+2^w, &x+y<-2^{w-1} & 负溢出
\end{cases}
补码加法溢出函数
对满足
$TMin_w\leq x,y\leq TMax_w$的x和y，令$s\doteq x+^t_wy$。当且仅当x>0,y>0，但$s\leq 0$时，计算s发生了正溢出。当且仅当x<0,y<0时但$s\geq 0$时，计算s发生了负溢出。
//判断补码加法是否溢出
int tadd_ok(int x,int y){int sum=x+y;int neg_over= x<0 && y<0 && sum>=0;//负溢出信号int pos_over= x>=0 && y>=0 && sum<0;//正溢出信号，编码考虑所有值的情况return !neg_over && !pos_over;
}
//意图通过阿尔贝群原理判断两数相加是否溢出？
int tadd_ok(int x,int y){int sum=x+y;return (sum-x==y) && (sum-y==x);
}
//因为返回的式子是恒成立的(阿尔贝群)，所以此函数无效。
补码的非[加法逆元($-^t_w$)]
对w位的补码加法来说，
$TMin_w$是自己加法的逆，而对其他任何数字都有-x作自己的逆。
执行位级补码非的第一种方法是对每一位求补，在对结果加1。C语言中，-x与~x+1等效。
对满足TMin_w\leq x\leq TMax_x的x，其补码的非-^t_w下式给出:\\-^t_wx=\\
\begin{cases}
TMin_w, & x=TMin_w\\
-x, & x>TMin_w
\end{cases}\\
无符号乘法
对满足0\leq x,y\leq UMax_w的x和y有:\\x*^u_wy=(x\cdot y) mod 2^w补码乘法
对满足TMin_x\leq x,y\leq TMax_w的x和y有：\\x*^t_wy=U2Tw((x\cdot y) mod 2^w)
//检测两个数相乘而是否发生溢出
int tmult_ok(int x,int y){int p=x*y; return !x && p/y==x;
}//看似“阿尔贝”，实则是可行的
- 当
$x=0$时，肯定不会溢出，排除。 - 说明
$x$和$y$的整数乘积$x\cdot y$，可以写成$x\cdot y=p+t\cdot 2^w$，其中t不等于0当且仅当p的计算溢出。 - 说明
$p$可以写成这样的形式，$p=x\cdot q+r$，其中$|r|<|x|$。 - 说明
$q=y$时当且仅当$r=t=0$。
乘以常数
对于某个常数K的表达式x*K生成代码，编译器会将K的二进制表示表达为一组0和1交替的序列。
[(0…0)(1…1)(0…0)(1…1)]，例如14可以写成[(0…0)(111)(0)]，设n为1的开始位置：3，m为结束位置：1
则可用以下两种形式获得乘以14的结果。
形式A:(x<<n)+(x<<(n-1))+...+(x<<m)\\
形式B:(x<<(n+1))-(x<<m)
把每个这样连续的1的结果加起来，不用做任何乘法，我们就能计算出x*K。
计算机使用移位、加法、减法或是乘法指令，取决于这些指令的相对速度，而这些与机器高度相关。
除以2的幂的无符号除法
无符号数的右移都是逻辑右移。
C变量x和k有无符号数值x和k，且0\leq k<w，\\则C表达式x>>k产生数值\left \lfloor x/2^k\right \rfloor\\
除以2的幂的补码除法
C变量x(补码)和k有无符号数值x和k，且0\leq k<w，执行算术移位：\\
(x+(1<<k)-1)>>k产生数值\left \lfloor x/2^k\right \rfloor\\
写一个函数div16，对整数参数x返回x/16的值。
int div16(int x){int t=(x>>31) & 0xF;//逻辑‘与’得到偏置量0或0xF;return (x+t)>>4;
}
支付宝扫一扫
微信扫一扫
.png)
.png)
.png)
.png)
