C/C++之若x大于y, 一定有-x小于-y吗

在数学中, 若 $x > y$, 则肯定有 $-x < -y$, 但在 C/C++ 中 "若 $x > y$, 则 $-x < -y$" 这一结论未必成立, 因为 C/C++ 中的取负操作实际上与数学中的取负操作是有区别的, 在下文中用 $-$ 表示数学中的取负操作, 用 $-^t$ 表示 C/C++ 中符号数的取负操作 (C/C++ 中的无符号数实际上也是支持取负操作的, 可以记做 $-^u$).

我们先看下面的代码 (可以打开该链接运行该段代码: http://coliru.stacked-crooked.com/a/aad124cf4cb32205):

#include <iostream>
#include <climits>

int main()
{
    signed int x = 0;
    signed int y = INT_MIN;
    std::cout << (x > y) << std::endl;
    std::cout << (-x < -y) << std::endl;

    std::getchar();
    return 0;
}

其输出的是 1 和 0, 而不是期望的 1 和 1, 这一结果不符合常识, 下面分析之.

设符号数的编码方式为 two's complement (这是绝大多数计算机系统中符号数的编码方式), 其位数为 $n$, 则有:
$$\begin{aligned} -^tx &= \begin{cases} -2^{n-1} & x = -2^{n-1} \\ -x & x > -2^{n-1} \end{cases}\\ &= (-x + 2^{n-1}) \bmod 2^n - 2^{n-1} \end{aligned}$$
当 $x \neq -2^{n-1}$ 且 $y = -2^{n-1}$ 时 (这时 $x > y$),
$$\begin{cases} -^tx = -x\\ -^ty = -2^{n-1} \end{cases}$$

因为 $-x > -2^{n-1}$, 所以 $-^tx > -^ty$, 即出现 $x > y$ 且 $-^tx > -^ty$.

实际上如果 $x$ 和 $y$ 都不为 $-2^{n-1}$, "若 $x > y$, 则 $-^t x < -^t y$" 这一结论是没问题的. 但这个前提让这个结论显得不那么优雅, 所以引出下面的结论: 对于符号数 $x$ 和 $y$, 若 $x > y$, 则 $\sim x < \sim y$. 证明如下:

设 $x$ 和 $y$ 是 $n$ 位的符号数, 即 $x, y \in \{-2^{n-1}, \cdots, 2^{n-1} - 1\}$, 则 $-1 - x, -1 - y \in \{-2^{n-1}, \cdots, 2^{n-1} - 1\}$, 即 $-1 - x$, $-1 - y$ 也在 $n$ 位符号数的取值范围内. 所以当 $x > y$ 时, $-1 - x < -1 - y$, 又因为 $\sim x = -1 - x$ 和 $\sim y = -1 - y$ (证明详见: https://www.zhihu.com/question/408097261/answer/1351647550), 所以 $\sim x < \sim y$ .

对于无符号数也有类似的结论: 对于无符号数 $x$ 和 $y$, 若 $x > y$, 则 $\sim x < \sim y$.

设 $x$ 和 $y$ 是 $n$ 位的无符号数, 即 $x, y \in \{0, \cdots, 2^n - 1\}$, 则 $2^n - 1 - x, 2^n - 1 - y \in \{0, \cdots, 2^n - 1\}$, 即 $2^n - 1 - x$, $2^n - 1 - y$ 在 $n$ 位无符号数的取值范围内. 所以当 $x > y$ 时, $2^n - 1 - x < 2^n - 1 - y$, 又因为 $\sim x = 2^n - 1 - x$ 和 $\sim y = 2^n - 1 - y$ (证明详见: https://www.zhihu.com/question/408097261/answer/1351647550), 所以 $\sim x < \sim y$ .

综上: 对于整型 $x$ 和 $y$, 若 $x > y$, 则不一定有 $-^t x < -^t y$, 但一定有 $\sim x < \sim y$.

参考

  • CSAPP

更新记录

  • 20210611, 发布
  • 20211226, 修改部分内容
版权归属: 采石工
本文链接: https://quarryman.cn/article/20210611
版权声明: 除特别声明外, 文章采用《署名-非商业性使用-相同方式共享 4.0 国际》许可协议.