（学习笔记）2.3 整数运算（2.3.3 补码的非&2.3.4 无符号乘法）

文章目录

• 线索栏
• 笔记栏
• • 1. 补码的非：定义与公式
  • 2. 公式推导（基于补码加法）
  • 3. 练习题2.33
  • 4. 位级补码非的两种计算技巧
  • • 1）方法一：取反加一
    • 2）方法二：找到最右边的1
• 总结栏

线索栏

笔记栏

1. 补码的非：定义与公式

（1）定义：在 w位补码加法

+

w

t

+_w^t

+wt​​下，一个数 x的加法逆元（即 −x）称为其“补码的非”，记为

−

w

t

​

x

−_w^t ​x

−wt​​x。它满足

x

+

w

t

​

(

−

w

t

​

x

)

=

0

x+_w^t ​(−_w^t ​x)=0

x+wt​​(−wt​​x)=0。 （2）核心公式 (2.15)：

x

+

w

t

y

=

{

T

M

i

n

w

,

x

=

T

M

i

n

w

−

x

,

x

>

T

M

i

n

w

x +_w^t y =\\begin{cases}TMin_w, & x= TMin_w\\\\-x , & x>TMin_w\\end{cases}

x+wt​y={TMinw​,−x,​x=TMinw​x>TMinw​​ （3）关键特殊性：对于

w

w

w位补码，最小值

T

M

i

n

w

TMin_w

TMinw​（位模式为 1后跟

w

−

1

w−1

w−1个 0）是自身的加法逆元。即

−

w

t

​

(

T

M

i

n

w

​

)

=

T

M

i

n

w

−_w^t ​(TMin_w​)=TMin_w

−wt​​(TMinw​​)=TMinw​​。这是因为对其取负会产生数学值

2

w

−

1

2^{w−1}

2w−1，超出了

w

w

w位补码的正数表示范围，发生溢出后结果恰好等于自身。

2. 公式推导（基于补码加法）

对于

x

=

T

M

i

n

w

=

−

2

w

−

1

x=TMin_w=−2^{w−1}

x=TMinw​=−2w−1： （1）数学上，

T

M

i

n

w

​

+

T

M

i

n

w

​

=

−

2

w

−

1

+

(

−

2

w

−

1

)

=

−

2

w

TMin_w​+TMin_w​=−2^{w−1}+(−2^{w−1})=−2^w

TMinw​​+TMinw​​=−2w−1+(−2w−1)=−2w。 （2）在

w

w

w位补码加法中，

−

2

w

−2^w

−2w会发生负溢出。根据补码加法公式(2.13)：

x

+

w

t

​

y

=

x

+

y

+

2

w

x+_w^t ​y=x+y+2^w

x+wt​​y=x+y+2w（当

x

+

y

<

T

M

i

n

w

x+y<TMin_w

x+y<TMinw​​）。 （3）因此，

T

M

i

n

w

​

+

w

t

​

T

M

i

n

w

​

=

(

−

2

w

)

+

2

w

=

0

TMin_w ​+_w^t​TMin_w​=(−2^w)+2^w=0

TMinw​​+wt​​TMinw​​=(−2w)+2w=0。得证

T

M

i

n

w

TMin_w

TMinw​ ​是自身的逆元。 对于

x

>

T

M

i

n

w

x>TMin_w

x>TMinw​​： 此时

−

x

−x

−x这个数学值在

w

w

w位补码的表示范围

[

T

M

i

n

w

,

T

M

a

x

w

​

]

[TMin_w,TMax_w​]

[TMinw​,TMaxw​​]内，可以直接表示，且满足

(

−

x

)

+

x

=

0

(−x)+x=0

(−x)+x=0。

3. 练习题2.33

比较补码非与无符号非（练习题2.28的结果）： 对于同一个位模式，其补码的逆元与无符号的逆元的位级表示（十六进制）完全相同。 例如，位模式 0xD(1101)： 解释为补码值-3，其逆元是3 (0x3)。 解释为无符号值13，其逆元是 16−13=3(0x3)。 原因：两种运算在硬件层面都通过 ~x + 1实现，位模式结果自然相同，只是解释不同。这再次体现了“位+上下文”。

4. 位级补码非的两种计算技巧

1）方法一：取反加一

（1）操作：对

x

x

x的每一位取反（按位非，~

x

x

x），然后加1。 （2）C语言等价表达：

−

x

-x

−x与 ~

x

+

1

x + 1

x+1的结果完全相同。 （3）原理：设

x

x

x的位向量为

x

x

x。∼

x

x

x的值为

2

w

−

1

−

x

2^{w−1}−x

2w−1−x。再加1得到

2

w

−

x

2^w−x

2w−x，这正好是

x

x

x在模

2

w

2^w

2w下的加法逆元，即补码非的位模式。 （4）示例：5(0101) → 取反 1010(-6) → 加1 1011(-5)。

2）方法二：找到最右边的1

（1）操作： 找到

x

x

x的二进制表示中最右边（最低有效位）的一个1。设其位置为

k

k

k（从0开始计数）。 对这个1左侧的所有位（位

k

+

1

k+1

k+1到

w

−

1

w−1

w−1）进行取反，右侧的所有位（位 0到

k

−

1

k−1

k−1，都是0）以及这个1本身保持不变。 （2）原理：这本质上是“取反加一”的优化版本。加一操作会使最低位的1变为0，其后的0变为1（进位链）。取反操作会将进位链左侧的位全部翻转，而链本身在“取反加一”后保持不变。此方法直接定位了进位链的终点（最右边的1）。 （3）示例：-4(1100)。 最右边的1在位置2（…100）。 左侧位（位3）取反：1→0。 （4）结果：0100(4)。

总结栏

本节核心是掌握补码的加法逆元（非）的计算与理解。

理解补码非，不仅是为了计算负数，更是洞悉计算机整数表示与运算自洽性的关键——系统为每个数（除 TMin外）都定义了唯一的逆元，使得在这个有限范围内，加法运算保持了良好的代数结构。