文章目录

• 预备知识
• • 模2范畴内的取反
  • 证明二进制补码规律
  • 模k同余
• 🎈负数的补码与原码和反码在二进制串的结构上的关系
• • 高位部分
  • • 例
  • 允许移位(正确移位)的条件
  • • 补码
    • 两数相加进位规律
  • 二进制数其他规律

预备知识

模2范畴内的取反

• KaTeX parse error: Undefined control sequence: \set at position 27: …,我们有规律: \\ y\in\̲s̲e̲t̲{0,1} \\ 1-y=\b…

• KaTeX parse error: Undefined control sequence: \set at position 27: …,我们有规律: \\ y\in\̲s̲e̲t̲{0,1} \\ 1+y= \…

  • 例如:真值x<0原码T(x)=1.x1x2⋯xn(小数点前面的1表示符号位为负号)反码A(x)=1.x1‾x2‾⋯xn‾补码C(x)=A(x)+2−n=1.x1‾x2‾⋯xn‾+2−n例如:真值x<0 \\原码T(x)=1.x_1x_2\cdots{x_n} \\(小数点前面的1表示符号位为负号) \\反码A(x)=1.\overline{x_1}\ \overline{x_2}\cdots{\overline{x_n}} \\补码C(x)=A(x)+2^{-n}=1.\overline{x_1}\ \overline{x_2}\cdots{\overline{x_n}}+2^{-n} 例如:真值x<0原码T(x)=1.x1​x2​⋯xn​(小数点前面的1表示符号位为负号)反码A(x)=1.x1​​ x2​​⋯xn​​补码C(x)=A(x)+2−n=1.x1​​ x2​​⋯xn​​+2−n

  • KaTeX parse error: Undefined control sequence: \set at position 228: …line{x_m};(m\in\̲s̲e̲t̲{1,\cdots,n}) \…

  • 例如:A(x)=0.1111C(x)=A(x)+2−4=0.1111+0.0001=1.0000可见x1⋯x4所有bit看起来都被取反了(最极端的进位连锁反应)此处m=1例如:A(x)=0.1111 \\C(x)=A(x)+2^{-4}=0.1111+0.0001=1.0000 \\可见x_1\cdots{x_4}所有bit看起来都被取反了(最极端的进位连锁反应) \\此处m=1 例如:A(x)=0.1111C(x)=A(x)+2−4=0.1111+0.0001=1.0000可见x1​⋯x4​所有bit看起来都被取反了(最极端的进位连锁反应)此处m=1

  • 又比如T(x)=0.01100A(x)=0.10011C(x)=A(x)+2−5=0.10011+0.00001=0.10100此处m=3记C(x)=0.x1x2x3x4x5可以看到x的补码C(x)的x1x2位置和x的原码x1xm−1位置的数码一致(x1⋯xm−1)(m=3)xm⋯xn和x的原码的xm⋯xn是一致的(m=3,n=5)又比如 T(x)=0.01100 \\ A(x)=0.10011 \\ C(x)=A(x)+2^{-5}=0.10011+0.00001=0.10100 \\此处m=3 \\记C(x)=0.x_1x_2x_3x_4x_5 \\可以看到x的补码C(x)的x_1x_2位置和x的原码 \\x_1x_{m-1}位置的数码一致(x_1\cdots{x_{m-1}})(m=3) \\x_m\cdots{x_n}和x的原码的x_m\cdots{x_n}是一致的(m=3,n=5) 又比如T(x)=0.01100A(x)=0.10011C(x)=A(x)+2−5=0.10011+0.00001=0.10100此处m=3记C(x)=0.x1​x2​x3​x4​x5​可以看到x的补码C(x)的x1​x2​位置和x的原码x1​xm−1​位置的数码一致(x1​⋯xm−1​)(m=3)xm​⋯xn​和x的原码的xm​⋯xn​是一致的(m=3,n=5)

证明二进制补码规律

• 用C(x)表示x的补码;用C(x)表示x的补码;用C(x)表示x的补码;

  • 证明C(−x)=−C(x)证明C(-x)=-C(x)证明C(−x)=−C(x)

    • 当x>0当x>0当x>0

      • KaTeX parse error: Undefined control sequence: \set at position 579: …ine{x_i}(x_i\in\̲s̲e̲t̲{0,1}) \end{ali…

        • 由于二进制(模2),x+2=2+x≡xmod2;−C(x)=−x=−0.x1x2⋯xn≡2−0.x1x2⋯xn(mod2)=1+(1−0.x1x2⋯xn)=1+0.x1‾x2‾⋯xn‾+2−n=1.x1‾x2‾⋯xn‾+2−n可见C(−x)=−C(x)=1.x1‾x2‾⋯xn‾+2−n由于二进制(模2),x+2=2+x\equiv x\mod{2}; \\-C(x)=-x=\ -0.x_1x_2\cdots{x_n} \equiv{2-0.x_1x_2\cdots{x_n}}(\mod{2}) \\=1+(1-0.x_1x_2\cdots{x_n}) \\=1+0.\overline{x_1}\ \overline{x_2}\cdots{\overline{x_n}}+2^{-n} \\=1.\overline{x_1}\ \overline{x_2}\cdots{\overline{x_n}}+2^{-n} \\\\ 可见C(-x)=-C(x)=1.\overline{x_1}\ \overline{x_2}\cdots{\overline{x_n}}+2^{-n} 由于二进制(模2),x+2=2+x≡xmod2;−C(x)=−x= −0.x1​x2​⋯xn​≡2−0.x1​x2​⋯xn​(mod2)=1+(1−0.x1​x2​⋯xn​)=1+0.x1​​ x2​​⋯xn​​+2−n=1.x1​​ x2​​⋯xn​​+2−n可见C(−x)=−C(x)=1.x1​​ x2​​⋯xn​​+2−n

      • 类似的可以证明x<0x<0x<0的情况

模k同余

• x≡ymodk或写作:x≡y(modk)表达的是:(x−y)%k=0(这不同于:x%k=y%k,比如4.1−2.1%≡2(mod2))x\equiv{y}\mod{k} \\或写作:x\equiv{y}(\mathrm{mod}\ k) \\表达的是: (x-y)\%k=0 \\(这不同于:x\%k=y\%k,比如4.1-2.1\%\equiv2(\mathrm{mod}\ 2)) x≡ymodk或写作:x≡y(mod k)表达的是:(x−y)%k=0(这不同于:x%k=y%k,比如4.1−2.1%≡2(mod 2))

🎈负数的补码与原码和反码在二进制串的结构上的关系

• 补码的左右移位的填补规则依赖于如下规律

• 下面仅讨论定点小数的情况,整数的情况手法类似,结论适用

• 对于x<0x<0x<0;

  • 机器字长为n+1;符号位占走1位,有n位留给数值位

  • 原码T(x)=1.x1x2⋯xm⋯xnT(x)=1.x_1x_2\cdots{x_m}\cdots{x_n}T(x)=1.x1​x2​⋯xm​⋯xn​

    • 假设从低位到高位观察T(x)的小数部分,第一个值为1的位值出现在xmx_mxm​这个位置上

    • 换句话说,如果没有精度/机器字长补齐要求,那么xm+1⋯xnx_{m+1}\cdots{x_n}xm+1​⋯xn​这部分的小数位都是0,它们可以不写

  • 反码C1(x)=1.x1‾x2‾⋯xm‾⋯xn‾反码C_1(x)=1.\overline{x_1}\ \overline{x_2} \cdots{\overline{x_m}}\cdots{\overline{x_n}\ }反码C1​(x)=1.x1​​ x2​​⋯xm​​⋯xn​​ 

    • 1.x1‾x2‾⋯xm‾⋯xn‾=1.x1‾x2‾⋯xm−1‾0▲1⋯11⏟xm+1‾⋯xn‾1.\overline{x_1}\ \overline{x_2} \cdots{\overline{x_m}}\cdots{\overline{x_n}\ } =1.\overline{x_1}\ \overline{x_2} \cdots{\overline{x_{m-1}}}\underset\blacktriangle{0} \underbrace{1\cdots{11}}_{\overline{x_{m+1}}\cdots\overline{x_n}} 1.x1​​ x2​​⋯xm​​⋯xn​​ =1.x1​​ x2​​⋯xm−1​​▲0​xm+1​​⋯xn​​1⋯11​​

  • 补码C(x)=c0.c1⋯cn=x0.c1⋯cnC(x)=c_0.c_1\cdots{c_n}=x_0.c_1\cdots{c_n}C(x)=c0​.c1​⋯cn​=x0​.c1​⋯cn​:

    • $$
      C(x)
      =C_1(x)+2^{-n}
      =1.\overline{x_1}\ \overline{x_2}
      \cdots{\overline{x_{m-1}}}\underset\blacktriangle{0}
      \underbrace{1\cdots{11}}{\overline{x{m+1}}\cdots\overline{x_n}}
      +2^{-n}
      \=1.\overline{x_1}\ \overline{x_2}
      \cdots{\overline{x_{m-1}}}\underset\blacktriangle{1}
      \underbrace{{0}\cdots{00}}{\overline{x{m+1}}\cdots\overline{x_n}}

      $$

  • 🎈可见,xmx_mxm​是无论是T(x)还是C(x)T(x)还是C(x)T(x)还是C(x)

    • 从低位开始向高位扫描的过程中最早出现的码值1都是同一个位置(xmx_mxm​)出

  • 🎈同时:

    • 我们把真值x的补码C(x)的数值位分为两部分:

      • c1⋯cm−1=x1‾x2‾⋯xm−1‾c_1\cdots{c_{m-1}}=\overline{x_1}\ \overline{x_2}\cdots \overline{x_{m-1}}c1​⋯cm−1​=x1​​ x2​​⋯xm−1​​
        • 即,这部分和反码相同
        • 记A=c1⋯cm−1A=c_1\cdots{c_{m-1}}A=c1​⋯cm−1​
      • cm⋯cn{ c_m}\cdots{c_n}cm​⋯cn​=xm⋯xnx_m\cdots{x_n}xm​⋯xn​
        • 部分和原码相同
        • 记B=cm⋯cnB=c_m\cdots{c_n}B=cm​⋯cn​

    • casesA:如果真值二进制数值位部分没有1(全为0),那么这种情况下,真值x=0x=0x=0

      • 实际上这种情况(x=0)(x=0)(x=0)已经不是负数的范畴,仅作为回顾
      • T(x)=±1.0⋯0T(x)=\pm1.0\cdots{0}T(x)=±1.0⋯0
      • A(x)=±1.1⋯1A(x)=\pm1.1\cdots{1}A(x)=±1.1⋯1
      • C(x)=0.0⋯0C(x)=0.0\cdots{0}C(x)=0.0⋯0
      • 可以看到,这种情况下,补码数值位部分的各个bit和原码的数值位部分一致!
      • 这类情况属于极端情况
        • m<0或m>n,都属于这类情况
        • 可以理解为A的长度是0,B的长度为n:A的长度是0,B的长度为n:A的长度是0,B的长度为n:

    • casesB:否则,真值的数值位二进制数码表示中有1

      • 即,m∈[1,n]m\in[1,n]m∈[1,n]

      • m⩽1时,无论x的正负,补码和原码具有一样的形式(C(x)=T(x))m\leqslant{1}时,无论x的正负,补码和原码具有一样的形式(C(x)=T(x))m⩽1时,无论x的正负,补码和原码具有一样的形式(C(x)=T(x))

        • 这种情况下可以在分为两种具体情况:
          • m=0m=0m=0
            • m=0m=0m=0要和符号位区分开来,意思是数值位最高位到最低位全部为0
            • 即C(x)=x0.0⋯00;x=0C(x)=x_0.0\cdots{00};x=0C(x)=x0​.0⋯00;x=0(定点小数)
              • 或C(x)=x0,0⋯0;x=0C(x)=x_0,0\cdots0;x=0C(x)=x0​,0⋯0;x=0(定点整数)
          • m=1m=1m=1
            • 意思是数值位最高位为1,其余数值位全为0
            • 即C(x)=x0.10⋯00C(x)=x_0.10\cdots{00}C(x)=x0​.10⋯00,x=±12x=\pm\frac{1}{2}x=±21​
              • 或C(x)=x0,10⋯00C(x)=x_0,10\cdots{00}C(x)=x0​,10⋯00,x=±2n−1,n是数值位位数x=\pm{2^{n-1}},n是数值位位数x=±2n−1,n是数值位位数

      • m⩾n+1m\geqslant{n+1}m⩾n+1

        • 这种情况归为casesA

  • 🎈上面两个结论对于x>0x>0x>0的是时候也显然是成立的(因为x>0x>0x>0时,原码补码反码一致!)

高位部分

• 一般的,我们对补码C(x)C(x)C(x)所对应的真值大小比较感兴趣
  • 这关乎到溢出判断和规格化操作的判断
• 然而体现数的大小,主要看从高位比较到低位
• 🎄下面的讨论比较啰嗦,个人认为上面的讨论更加有品位,而且更加体现概率统计的习惯
• 根据上述结论,数值位第一位开始到第m-1位x1⋯xm−1x_1\cdots{x_{m-1}}x1​⋯xm−1​这部分是x的反码A(x)相同
  • 对这部分每位取反,即可得到原码在这部分位置的取值(也就是高位小数位的取值)
• 设:C(x)=x0.x1⋯xnC(x)=x_0.x_1\cdots{x_n}C(x)=x0​.x1​⋯xn​
  • x1⋯xnx_1\cdots{x_n}x1​⋯xn​至少有一个bit取1(x≠0x\neq{0}x​=0)
    • x1=0x_1=0x1​=0
      • x2⋯xn中至少有一个1x_2\cdots{x_n}中至少有一个1x2​⋯xn​中至少有一个1
        • T(x)=x0.1⋯,∣x∣⩾12T(x)=x_0.1\cdots,|x|\geqslant{\frac{1}{2}}T(x)=x0​.1⋯,∣x∣⩾21​
    • x1=1x_1=1x1​=1
      • x2⋯xnx_2\cdots{x_n}x2​⋯xn​至少有一个bit取1
        • T(x)=x0.0⋯;∣x∣<12T(x)=x_0.0\cdots;|x|<\frac{1}{2}T(x)=x0​.0⋯;∣x∣<21​
      • 否则
        • T(x)=C(x)=x0.10⋯00;∣x∣=12T(x)=C(x)=x_0.10\cdots{00};|x|={\frac{1}{2}}T(x)=C(x)=x0​.10⋯00;∣x∣=21​
  • x1⋯xnx_1\cdots{x_n}x1​⋯xn​全部取0,x=0x=0x=0

例

• 将小数xxx的小数数值部分,从高位到低位分别编为x1⋯xnx_1\cdots{x_n}x1​⋯xn​
  • KaTeX parse error: Undefined control sequence: \set at position 16: x_i代指第i位小数,i\in\̲s̲e̲t̲{1,2,\cdots{,n}…
  • x=x0.x1⋯xnx=x_0.x_1\cdots{x_n}x=x0​.x1​⋯xn​
• x=−0.11011,小数位数为n=5;x=-0.11011,小数位数为n=5;x=−0.11011,小数位数为n=5;
  • 最低位的1出现在m=5(即x5)处最低位的1出现在m=5(即x_5)处最低位的1出现在m=5(即x5​)处
  • 原码T(x)=1.11011T(x)=1.11011T(x)=1.11011
  • 补码C(x)=1.00100+2−5=1.00100+0.00001=1.00101C(x)=1.00100+2^{-5}=1.00100+0.00001=1.00101C(x)=1.00100+2−5=1.00100+0.00001=1.00101
• x=−0.01⋯,小数点尾数大于2,小于等于nx=-0.01\cdots,小数点尾数大于2,小于等于nx=−0.01⋯,小数点尾数大于2,小于等于n
  • T(x)=1.01⋯T(x)=1.01\cdotsT(x)=1.01⋯
  • C(x)=1.1⋯C(x)=1.1\cdotsC(x)=1.1⋯
    • 根据上面的规律(同一个真值x的原码和补码和反码在结构上的关联:)
      • m⩾2m\geqslant{2}m⩾2
      • 设C(x)=x0,b1b2⋯bn设C(x)=x_0,b_1b_2\cdots{b_n}设C(x)=x0​,b1​b2​⋯bn​
      • C(x)的最低位1应该出现在第m位小数(xm=1)C(x)的最低位1应该出现在第m位小数(x_m=1)C(x)的最低位1应该出现在第m位小数(xm​=1)
      • 更重要的是,同时有b1⋯bm+1=x1‾⋯xm−1‾b_1\cdots{b_{m+1}}=\overline{x_1}\cdots{\overline{x_{m-1}}}b1​⋯bm+1​=x1​​⋯xm−1​​
        • 本例中,m⩾2m\geqslant{2}m⩾2,那么m−1⩾1m-1\geqslant{1}m−1⩾1
        • 随意,至少能够保证b1=x1‾b_1=\overline{x_1}b1​=x1​​,即b1=1b_1=1b1​=1
        • 从而,得到C(x)=1.1⋯C(x)=1.1\cdotsC(x)=1.1⋯的断言

允许移位(正确移位)的条件

• 讨论在什么情况下移位不会导致数据丢失而发生错误

补码

• 左移:
  • 当符号位和最高数据位一致的时候,进行补码左移1位不会操作数据丢失
    • 可以分类讨论
    • 也可以反方向讨论:
      • x≠0x\neq{0}x​=0:
        • 只有在真值x的最高位有效数据位不会丢失的左移,对应补码的左移行为x的最高位有效数据位不会丢失的左移,对应补码的左移行为x的最高位有效数据位不会丢失的左移,对应补码的左移行为
        • x=x0,x1x2⋯x=x_0,x_1x_2\cdotsx=x0​,x1​x2​⋯
          • x1=1时,左移1bit会发生错误x_1=1时,左移1bit会发生错误x1​=1时,左移1bit会发生错误(丢失高位数据)
          • x1=0时,左移1bit不会导致关键数据丢失x_1=0时,左移1bit不会导致关键数据丢失x1​=0时,左移1bit不会导致关键数据丢失(类似于对非规格化数做一次左归操作)
            • 这种情况下,对应到补码的移动,需要讨论正负两种大类情况
              • x0=0x_0=0x0​=0
                • 即x=+0.01...;C(x)=T(x)=0.01⋯即x=+0.01...;C(x)=T(x)=0.01\cdots即x=+0.01...;C(x)=T(x)=0.01⋯
                • 可见,x1=0x_1=0x1​=0
              • x0=1x_0=1x0​=1
                • x=−0.01...;C(x)=1.1⋯x=-0.01...;C(x)=1.1\cdotsx=−0.01...;C(x)=1.1⋯
                • 可见,x1=1x_1=1x1​=1
        • 可见,当真值x不为0时,符号位和最高数据位一致的时候,进行补码左移1位不会操作数据丢失
      • x=0时,C(x)中,x1对应为0x=0时,C(x)中,x_1对应为0x=0时,C(x)中,x1​对应为0
        • 由于x=0,所以左移位操作丢失0不会造成错误
      • 综上,只要C(x)=c0.c1⋯满足c0=c1,那么左移1位不会造成错误综上,只要C(x)=c_0.c_1\cdots满足c_0=c_1,那么左移1位不会造成错误综上,只要C(x)=c0​.c1​⋯满足c0​=c1​,那么左移1位不会造成错误

两数相加进位规律

• 两个n位数相加,结果位数不超过n+1位

  • 推导

  • x+y⩽∣x+y∣⩽∣x∣+∣y∣两个最大的n位r进制数的求和结果:记q=r−1(就是表示最大的数码)例如:如果r=10(十进制),那么q=9)最小n位数:rn−1=10⋯00⏟n−1个0⏞n位数最大的n位数:rn−1=q⋯qq⏟n个q最小n+1位数:rn例如n=2,10和99分别是最小2位数和最大两位数2个最大n位数相加:A=(rn−1)+(rn−1)=2(rn−1)最大n位数的r倍B=r(rn−1)=q⋯qq⏟n个q0(A0⋯00​​​n位数​最大的n位数:rn−1=n个qq⋯qq​​最小n+1位数:rn例如n=2,10和99分别是最小2位数和最大两位数2个最大n位数相加:A=(rn−1)+(rn−1)=2(rn−1)最大n位数的r倍B=r(rn−1)=n个qq⋯qq​​0(A

二进制数其他规律

• PC_二进制数的性质/模2的性质/进位计数法/进制数之间的通用转换办法/任意进制数间的转换原理(python)/二进制幂展开表示法_xuchaoxin1375的博客-CSDN博客_将十进制小数转换为r进制小数的方法是