快速取相反数算法的数学原理

算法

C语言中，快速对一个数取反可以通过执行下面的代码实现：

int x = 5;
int neg_x = ~x + 1;

下证 。

推导

一个 位二进制串 ，补码数值由下式定义：

最高位权重为 ，其余位权重保持 不变。

以 8 位为例：

设 的每一位为 ，按补码权重规则展开：

取反后每一位变成 ，结果仍按补码权重规则展开：

分配展开：

中间求和为等比数列：

代入上式后， 与 抵消：

两边加 1：

若直接对 的权重表达式取负，得到：

发现两式右侧完全一致，故有：

得证。