计算机常识

HeChuangJun约 2865 字大约 10 分钟

计算机的常识

1. 内存图
2. 字符编码表及字符与编码解码
3. ASCII码
4. 循环冗余校验CRC(Cyclic Redundancy Check)
5. 哈希算法
6. 位运算
7. 浮点数在计算机中的存储

1. 内存图

2. 字符编码表及字符与编码解码

生活中字符和计算机二进制的对应关系表

ASCII表。定长，单字节7位编码。各种英文字符对应的编码。
iso-8859-1/latin1:拉丁码表，定长单字节8位编码，1-xxxxxxx 负数。
GB2312:简体中文码表（汉字编码字符基本集）。定长，双字节编码。
GBK:（汉字内码扩展规范）向下兼容GB2312、定长。双字节编码，
unicode：兼容全球的字符集。国际标准码表:双字节编码。
UTF-8(unicode字符集)，非定长，以1-4字节为单位对Unicode进行编码
- 编程推荐使用UTF-8、windows默认GBK编码
  Java中的char类型用的就是这个码表。char c = 'a';占两个字节。
  Java中的字符串是按照系统默认码表来解析的。
  简体中文版字符串默认的码表是GBK。
  UTF-8:基于unicode，一个字节就可以存储数据，不要用两个字节存储，
  而且这个码表更加的标准化，在每一个字节头加入了编码信息(后期到api中查找)。
  文字--->(数字) ：编码。 “abc”.getBytes() byte[]
  (数字)--->文字 : 解码。 byte[] b={97,98,99} new String(b)

3. ASCII码

标准ASCII使用7位二进制数（剩下的1位二进制为0）总共128个字符（2^7）。表示所有的大写和小写字母，数字0 到9、标点符号，以及在美式英语中使用的特殊控制字符。由95个可打印字符（0x20-0x7E）和33个控制字符（0x00-0x1F，0x7F）组成。计算机区分二进制和ASCII取决于程序
Extended ASCII码：7bits->8bits。常见的数学运算符、带音标的欧洲字符、其他常用符、表格符等

4. 循环冗余校验CRC(Cyclic Redundancy Check)

作用：发现并纠正信息在存储或传输过程中连续出现的多位错误码，基于模2运算
模2运算：不考虑进位和错位
- 模2加法：奇数个1相加得1，偶数个1相加得0 0+0=1+1=0，1+0=0+1=1
- 模2减法：奇数个1相加得1，偶数个1相加得0 0-0=1-1=0 1-0=0-1=1
- 模2乘法：按普通乘法演算，部分积按模2加法运算
- 模2除法：按模2减求部分余数，每求一位商使余数减少一位，当部分余数的首位为1，上商1，当部分余数的首位为0时，上商0。当部分余数的位数小于除数的位数时，该余数即为最后余数。
CRC校验步骤
- 选择一个生成多项式，作为对接收的帧进行除法运算时的除数，生成多项式可以写为二进制形式；如x^5+x^3+x^2+1，写为二进制：101101。CRC的错误检测能力和位串的阶数r有关
  - 生成多项式的要求：
    - 最高位和最低位必须为1；
    - 当CRC码的任何一位发生错误时，新帧除生成多项式后余数不为0；
    - 不同位发生错误时，余数应该是不同的；
    - 对余数继续作模2除，应使余数循环
- 计算CRC校验码位数k=生成多项式最高位数-1，在要发送的数据帧后加k个0，除第一步用生成多项式转化的二进制数（使用模2除法），得到的余数即为CRC校验码（FCS）；模2除时，余数的位数必须只比除数少一位，不能省略0
- 把得到的校验码CRC加到原数据帧后，构成一个新数据帧发送到接收端，接收端将新帧除以之前选择的除数（模2除法），如果没有余数，则表明该数据帧在传输过程中没有出错，否则出错；
- 若某位出错，则余数不为0.对此余数补零后继续作模2除法，又得到一个不为0的余数。反复这样，将得到一个循环的余数队列，此时被校验码字循环左移直到最左边，对其中的错误位取反即可得到纠正后的编码

5. 哈希算法

哈希：把任意长度的字符串输入通过散列算法，变换成固定长度的哈希值；这种转换是一种压缩映射。同一散列函数计算出的散列值如果不同，那么输入值肯定也不同。但是，根据同一散列函数计算出的散列值如果相同，输入值不一定相同
哈希冲突：当两个不同的输入值，根据同一散列函数计算出相同的散列值的现象

6. 位运算

负数按补码形式参加按位与运算。
& 与两个位都为1时，结果才为1
| 或两个位都为0时，结果才为0、只要有一个为1，其值为1。
^ 异或两个位相同为0，相异为1
~ 取反 0变1，1变0
<< 左移各二进位全部左移若干位，高位丢弃，低位补0 若左移时舍弃的高位不包含1，则每左移一位，相当于该数乘以2。
右移各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移）操作数每右移一位，相当于该数除以2。
2^30次方=1>>>30
与运算的用途：
- 清零：如果想将一个单元清零，即使其全部二进制位为0，只要与一个各位都为零的数值相与，结果为零。
- 取一个数的指定位：比如取数 X=1010 1110 的低4位，只需要另找一个数Y，令Y的低4位为1，其余位为0，即Y=0000 1111，然后将X与Y进行按位与运算（X&Y=0000 1110）即可得到X的指定位。
- 判断奇偶：只要根据最未位是0还是1来决定，为0就是偶数，为1就是奇数。因此可以用if ((a & 1) == 0)代替if (a % 2 == 0)来判断a是不是偶数。
- 用于在整型变量上维护多种状态ReentrantReadWriteLock
或运算的用途：
- 对一个数据的某些位设置为1，比如将数 X=1010 1110 的低4位设置为1，只需要另找一个数Y，令Y的低4位为1，其余位为0，即Y=0000 1111，然后将X与Y进行按位或运算（X|Y=1010 1111）即可得到。
- 强行变成最接近的偶数(二进制最末位变成0) 对这个数 or 1 之后再减一就可以了，就能把这个数强行变成最接近的偶数使a的最低位为0，可以表示为：a & ~1。~1的值为 1111 1111 1111 1110，再按"与"运算，最低位一定为0
异或运算的用途：
- 1）翻转指定位：比如将数 X=1010 1110 的低4位进行翻转，只需要另找一个数Y，令Y的低4位为1，其余位为0，即Y=0000 1111，然后将X与Y进行异或运算（X^Y=1010 0001）即可得到。
- 与0相异或值不变：例如：1010 1110 ^ 0000 0000 = 1010 1110
- 交换两个数

void Swap(int &a, int &b){
    if (a != b){
        a ^= b;
        b ^= a;
        a ^= b;
    }
}

取反运算的用途：

使一个数的最低位为零。使a的最低位为0，可以表示为：a & ~1。~1的值为 1111 1111 1111 1110，再按"与"运算，最低位一定为0。因为" ~"运算符的优先级比算术运算符、关系运算符、逻辑运算符和其他运算符都高。

7. 浮点数在计算机中的存储

假设存储78.375, $(78.375)_{10} = (1001110.011)_{2} = 1.001110011 * 10^{6}$
- 整数部分： $(78)_{10} = (1001110)_{2}$
- 小数部分： $(0.375)_{10} = 3 / 8 = 1 / 4 + 1 / 8 = 2^{- 2} + 2^{- 3} = (0.01)_{2} + (0.001)_{2} = (0.011)_{2}$
在计算机中存储浮点数分为3部分
- 符号位（sign），用来区分正负，这里是 0，表示正数
- 指数（exponent），这里的指数是十进制的 6
- 小数（fraction），这里的小数部分是 001110011
指数位决定了大小范围，因为指数位能表示的数越大则能表示的数越大
小数位决定了计算精度，因为小数位能表示的数越大，则能计算的精度越大
float类型是32位，是单精度浮点表示法：1位符号位，8位指数位，23位小数位
double类型是64位。是双精度浮点表示法：1位符号位，11位指数位，52位小数位
指数有正负数，即指数是有符号整数，而有符号整数的计算是比无符号整数麻烦的。所以为了减少不必要的麻烦，在实际存储时需要把指数转换成无符号整数。
float的指数部分是8位，则指数的取值范围是-126到+127，为了消除负数带来的实际计算上的影响（比如比较大小，加减法等），在实际存储的时候，给指数加上一个偏移量，比如float的指数偏移量为127，这样就不会有负数出现了。比如指数是-3，则实际存储的是-3+127=124，即把124转换为二进制之后再存储。计算实际代表的十进制数的时候，再把指数减去偏移量即可。
double 类型，存储时指数偏移量是1023
为什么指数/阶码的取值范围是-126到+127呢?这里需要用到偏移量,以单精度为例,偏移量Bias=127.
- 当指数位不全是0也不全是1时(规格化的数值),IEEE规定,阶码计算公式为 e-Bias. 此时e最小值是1,则1-127= -126 ; e最大值是254,则254-127=127.可以看到,这种情况下取值范围是-126到127.
- 当指数位全部是0的时候(非规格化的数值),IEEE规定,阶码的计算公式为1-Bias,即1-127= -126.
- 当指数位全部是1的时候(特殊值),IEEE规定这个浮点数可用来表示3个特殊值,分别是正无穷,负无穷,NaN(not a number) . 小数位不为0的时表示NaN;小数位为0时,当符号位s=0时表示正无穷,s=1表示负无穷
浮点数范围计算公式：
- $f l o a t 最大值 = 1. \underset{23 个}{\underset{⏟}{11. .11}} * 2^{127} = (1 + 0. \underset{23 个}{\underset{⏟}{11. .11}}) * 2^{127} = [1 + (1 - 2^{- 23})] * 2^{127} = (2 - 2^{- 23}) * 2^{127} = 3.403 E 38$
- $f l o a t 最小值 = 0. \underset{23 个}{\underset{⏟}{00. .1}} * 2^{- 126} = 2^{- 23} * 2^{- 126} = 2^{- 149} = 1.4 E - 45 f$