[A03]原码反码补码与位运算

[hylerrix]

一、机器数和真值

• 机器数(computer number)是数字在计算机中的二进制表示形式
• 机器数有 2 个特点：一是符号数字化，二是其数的大小受机器字长的限制
• 比如：十进制中的 +6，计算机字长为 8 位，转换成二进制就是 00000110，如果是 -6 ，就是 10000110
• 这里的 00000110 和 10000110 便是机器数
• 因为第一位是符号位(正数该位为 0，负数该位为 1，0 分 +0 和 -0)，所以：
  • 8位二进制数的取值范围就是: [1111 1111, 0111 1111]
  • 机器数的形式值就不等于真正的数值。
  • 为区别起见，将带符号位的机器数对应的真正数值称为机器数的真值。
  • 比如：0000 0001的真值 = +000 0001 = +1, 1000 0001的真值 = –000 0001 = –1

二、原码，反码和补码的基础概念

对于一个数, 计算机要使用一定的编码方式进行存储。原码, 反码, 补码是机器存储一个具体数字的编码方式

[+1] = [00000001]原 = [00000001]反 = [00000001]补
[-1] = [10000001]原 = [11111110]反 = [11111111]补

1. 原码：原码就是符号位加上真值的绝对值, 即用第一位表示符号, 其余位表示值
2. 反码：正数的反码是其本身；负数的反码是在其原码的基础上, 符号位不变，其余各个位取反
3. 补码：正数的补码就是其本身；负数的补码即是在反码的基础上 +1

由此可见，正数的原码反码补码都是自身，负数的反码，补码都无法直观看出其数值，需要转换成原码再计算其数值

三、为什么要使用原码，反码和补码

对于计算机，加减乘数已经是最基础的运算, 要设计的尽量简单，而让计算机辨别"符号位"显然会让计算机的基础电路设计变得十分复杂。于是人们开始探索将符号伪参与运算，并且只保留加法的方法

若用原码计算十进制减法：1-1=0，结果是不正确的：

1 - 1 = 1 + (-1) = [00000001]原 + [10000001]原 = [10000010]原 = -2

使用反码时，结果的真值部分正确：

1 - 1 = 1 + (-1) = [0000 0001]原 + [1000 0001]原= [0000 0001]反 + [1111 1110]反 = [1111 1111]反 = [1000 0000]原 = -0

而反码的问题在于 0 上，反码中会有 [0000 0000]原=+0 和 [1000 0000] 原=-0两个编码表示0，于是出现了解决这一问题的补码 [1000 0000补(8 位二进制机器数中，补码还能够多表示一个最低数 -128=[1000 0000]补 ）：

1-1 = 1 + (-1) = [0000 0001]原 + [1000 0001]原 = [0000 0001]补 + [1111 1111]补 = [0000 0000]补=[0000 0000]原

四、原码，补码，反码再深入

• 再次推荐张子秋有关原码反码补码的博客，里面还讲了同余的概念与负数取模，自己也就不摘抄了。。
• x mod y 等于 x 减去 y 乘上 x 与 y 的商的下界
• 一个数的反码, 实际上是这个数对于一个膜的同余数，而这个膜并不是我们的二进制, 而是所能表示的最大值
• 由于 0 的特殊情况, 没有办法表示128, 所以补码的取值范围是 [-128, 127]

五、数据溢出测试

六、位运算的运算说明

& 按位 与「AND」

功能：对应的两个二进位 均为1 时，结果为 1，否则为 0
例子：9&5 = 1001&0101 = 0001，即 9&5=1
*规律：二进制中与 1& 保持原位，与  0& 为0

| 按位 或「OR」

功能：对应的两个二进位 只要有一个为1 时，结果为 1，否则为 0
例子：9|5 = 1001|0101 = 1101，即 9|5=13

^ 按位 异或「XOR,EOR」

• 功能：对应的两个二进位 不相同 为 1，否则为 0
• 例子：9^5 = 1001^0101 = 1100，即 9^5=12
• 规律：
  • 同一整数 相异或 为0，例：5^5=0
  • 不同整数 相异或 结果和顺序无关，例：5^6^7 = 5^7^6
  • 任何数 和 0 异或 结果不变，例：x^0 = x
  • 综上，x^y^x = x^x^y = 0^y = y

~ 按位 取反「NOR」

• 功能：对整数的 每一位取反，符号也位取反「取反：0取反为1，1取反为0」
• 例子：~9 = -10(因为负数是补码存储的)

~9=~[00001001]原=[11110110]补=[11110101]反=[10001010]原=-10

<< 左移(shl)

• 格式：整数<<左移个数
• 例子：x << n
• 实质：x * 2n
• 操作：把 x 的二进制位 向左移动 n 个单位，高位丢弃，低位补0

>> 右移(shr)

• 格式：整数>>右移个数
• 例子：x >> n
• 实质：x / 2n
• 操作：把 x 的二进制位 向右移动 n 个单位，低位丢弃，符号位不变
• 注意：符号位也跟着移动, 右移不改变整数的正负, 最后符号位要调整为原来的数值
• 正数 符号位为 0, 最高位补 0
• 负数 符号位为 1, 最高位补 1

七、位运算的简单应用

##（& 按位 与「AND」)奇偶判断

• 取模判断：a%2?printf(“奇数\n”):printf(“偶数\n”);
• 与壹判断：a&1?printf(“奇数\n”):printf(“偶数\n”);

##（^ 按位 异或「XOR,EOR」)数值转换

• 借助第三方变量：temp = a;a = b;b = temp;
• 不借助额外空间，数学法：a = b - a;b = b - a;a = b + a;
• 不借助额外空间，位运算：a = a ^ b;b = a ^ b;a = a ^ b;

(<< 左移 和 >> 右移)优化乘除法效率

• a shl b 的值等于a乘以2的b次方
• a shr b 比如二分查找、堆的插入操作等等

• Hello，我是韩亦乐，现任本科软工男一枚。软件工程专业的一路学习中，我有很多感悟，也享受持续分享的过程。如果想了解更多或能及时收到我的最新文章，欢迎订阅我的个人微信号：韩亦乐。我的简书个人主页中，有我的订阅号二维码和 Github 主页地址；[我的知乎主页]中也会坚持产出，欢迎关注。
• 本文内部编号经由我的 Github 相关仓库统一管理；本文可能发布在多个平台但仅在上述仓库中长期维护；本文同时采用【知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议】进行许可。