关于c:计算机如何表示整数

[TOC]

在计算机中，任何的数据都是用二进制：0 和 1 来示意。整数也不例外。生存中的 10，在 8 个字节的整数中示意为 00001010。然而这样子只能示意负数和零。怎么示意正数呢？于是有了符号位的概念。在 8 个字节的整数中，最高位为符号位，0 代表负数，1 代表正数。所以 -10 就能够用 10001010 来示意。然而，间接采纳符号位会带来一系列问题：

• 00000000 和 10000000 示意为 0 和 -0，那么用那个来示意 0，还是都是零？
• 加法问题。

对于加法问题，试着运算 1 - 1 的值：

1. 将 1 - 1 转换成 1 + (-1)
2. 转换成二进制：00000001 + 10000001
3. 运算后果为 10000010 转换成十进制为 -2

很显著，这个后果不对。为了解决这个问题，在计算机中引入补码（2’s complement）来解决。要解释为什么要应用补码，还得从无符号整型开始说起。

为了便于了解和不便，我用 3 个字节的整数来解说。但因为 C 语言最小都是 8 个字节，在代码验证方面应用 8 个字节。

无符号整型（unsigned integer）

3 个字节的无符号整型中，能够示意 2^3^ = 8 个数：

000 = 2^2 * 0 + 2^1 * 0 + 2^0 * 0 = 0+0+0 = 0
001 = 2^2 * 0 + 2^1 * 0 + 2^0 * 1 = 0+0+1 = 1
010 = 2^2 * 0 + 2^1 * 1 + 2^0 * 0 = 0+2+0 = 2
011 = 2^2 * 0 + 2^1 * 1 + 2^0 * 1 = 0+2+1 = 3
100 = 2^2 * 1 + 2^1 * 0 + 2^0 * 0 = 4+0+0 = 4
101 = 2^2 * 1 + 2^1 * 0 + 2^0 * 1 = 4+0+1 = 5
110 = 2^2 * 1 + 2^1 * 1 + 2^0 * 0 = 4+2+0 = 6
111 = 2^2 * 1 + 2^1 * 1 + 2^0 * 1 = 4+2+1 = 7

既然是整数，免不了要加减乘除。

在计算机中，只用加法能够实现的整数的四则运算：

• 减法，就是加上一个正数。
• 乘法，就是一直的做加法。
• 除法，就是一直的做减法，而减法又能够转换成加法。

然而这样会呈现问题：

• 两个无符号整数相加，超出了 3 个字节示意的范畴怎么办？比方：3 + 7。
• 两个无符号整数相减。转换成加上一个正数。既然是无符号整数，哪里来的正数？

要想解决这个问题，低头看看墙上的钟吧。

时钟零碎

假如当初是 4 点钟：

但实际上当初曾经六点钟了，你当初要把指针调到 6 点去。你能够这么做：

1. 顺时针调整 2 个小时：

2. 逆时针调整 10 个小时：

3. 顺时针调整 14 个小时，逆时针调整 22 个小时…

把上述过程用数学来示意：顺时针旋转几小时等于加上几个小时。逆时针则为减去几个小时。有：

4 + 2 = 6
4 - 10 = 6
4 + 14 = 6
4 - 22 = 6

时钟的一圈是 12 个小时。也就是说，在时钟零碎中，向上溢出和向下溢出，都通过模 12 来解决问题

$$
4 – 10 \equiv 4 + (-10) \equiv 4 + (-10 \bmod 12) \equiv 4 + 2 \equiv 6 \pmod{12}
\\
$$

下面能够说成，4 与 -10 同余

正数怎么取余

整数取余咱们都理解，始终把 被余数 减去 余数 直到小于 0 即可。同理，正数取余咱们能够把 被余数 加上 余数 晓得大于 0 即可。

依据下面思路，很快咱们能够写出代码：

/**
 * number 被余数
 * mod 余数
 */
int min_mod(int number, int mod)
{if (number >= 0) {while (number - mod >= 0) {number = number - mod;}
    return number;
  }
  else {while (number + mod < 0) {number = number + mod;}
    return number + mod;
  }
}

下面尽管好了解，然而代码执行效率不高，工夫复杂度为 O(n)。

咱们将余数（remainder）退出除法中，有：

$$
\frac{divident}{divisor} = quotient \dots remainder
$$

转换一下:

$$
divident = quotient \times divisor + remainder \qquad 1
$$

替换一下程序，能够得出余数为：

$$
remainder = divident – quotient \times divisor \qquad 2
$$

其中商（quotient）是被除数（divident）与除数（divisor）相除向下取整（floor）的后果：

$$
quotient = \lfloor \frac{divident}{divisor} \rfloor
$$

注：$\lfloor \rfloor$ 为向下取整的符号。如，$\lfloor 3.5 \rfloor = 3$，$\lfloor -1.3 \rfloor = 2$。

15/12 等于 1.25 向下取整就成了 1。-10/12 等于 0.833.. 向下取整为 -1。向下取整能够了解为取一个更凑近负无穷的整数。

插一句，C/C++/Java 中，正数除法都是向上取整。也就是 -10/12 等于 0。python 中，正数除法为向下取整。

联合 1 式和 2 式，能够得出：

$$
remainder = divident – divisor \times \lfloor \frac{divident}{divisor} \rfloor
$$

当初将上述代码能够优化成一句代码：

int one_step_mod(int number, int mod)
{return number - (mod * (int)floor(number * 1.0 / mod));
}

别忘记加上 math.h 头文件。

另外，试着想想 * 1.0 起什么作用？不加行不行？

借助时钟的实现解决无符号整型问题

了解了时钟的运行，咱们再来看看无符号的两个问题：

• 两个无符号整数相加，超出了 3 个字节示意的范畴怎么办？比方：2 + 7。
• 两个无符号整数相减。转换成加上一个正数。既然是无符号整数，哪里来的正数？

如果把 3 个字节的无符号整数看成时钟的话，它长这样：

那么无符号整数也同样能够通过同余运算解决上述问题：

相加超过范畴而导致上溢出

两个无符号整数相加，如果超出范围，间接模 2^n^ 即可：

$$
2 + 7 \equiv 9 \bmod 8 \equiv 1 \pmod 8
$$

体现在钟表上，就是将指针顺时针旋转 7 个小时。

加上一个正数

整数相减，相当于加上一个正数。先将正数转换成 2^n^ 下的最小整数，在进行加法运算：

$$
2 – 7 \equiv 2 + (-7 \bmod 8) \equiv 2 + 1 \equiv 3 \pmod 8
$$

体现在钟表上，就是将指针逆时针旋转 7 个小时。

总结

计算机用同余运算解决上溢出与正数。无符号整型的加法运算实际上等价于模 2^n^ 的加法运算。

代码验证

talk is cheap, show me your code.

讲了这么多，再通过代码来验证这一过程：

须要留神的是，C 语言中，最小的数据类型为 8 个字节，与上述的 3 个字节有小许差别。

int main()
{
    uint8_t two = 2;
    uint8_t last = 255;
    printf("%d \n", two);  // 2
    printf("%d \n", last); // 255
    uint8_t temp = two + last; // 顺时针旋转
    printf("%d \n", temp); // 1
    temp = two - last; // 逆时针旋转
    printf("%d \n", temp); // 3
    temp = -2;
    printf("%d \n", temp); // 254
    return 0;
}

别忘了引入 stdint.h 头文件。

学完了无符号整数，看看上面这道题你是否给出正确答案：

int main()
{
    uint8_t a = -128;
    uint8_t b = a / -1;
    printf("%d", b); // what is it?
    return 0;
}

有符号整型(signed integer)

如果仅仅应用符号位来示意 3 个字节的有符号整数，能够示意 2^3^ -1 = 7 个数：

000 = (2^1 * 0 + 2^0 * 0) *  1 =   0+0  =  0
001 = (2^1 * 0 + 2^0 * 1) *  1 =   0+1  =  1
010 = (2^1 * 1 + 2^0 * 0) *  1 =   2+0  =  2
011 = (2^1 * 1 + 2^0 * 1) *  1 =   2+1  =  3
100 = (2^1 * 0 + 2^0 * 0) * -1 = -(0+0) =  0
101 = (2^1 * 0 + 2^0 * 1) * -1 = -(0+1) = -1
110 = (2^1 * 1 + 2^0 * 0) * -1 = -(2+0) = -2
111 = (2^1 * 1 + 2^0 * 1) * -1 = -(2+1) = -3

后面说过，如果仅仅应用符号位来示意有符号整型，会有以下问题：

• 0 的示意。
• 加法无奈算出后果。

仔细观察，你会发现它仅仅能够示意正数，其余什么都干不了：四则运算（也就是加法）会出错，两个 0 的问题。

蹩脚的示意办法

要想晓得它是如何引入这个问题的，将这个蹩脚的示意办法转换成时钟，可能你就明确了：

从上图中，咱们能够发现，它并不遵循同余运算。仔细观察 101 也就是 -1 这个中央，在无符号整型中，它示意 5。在有符号整型中，因为最高位被符号位的占据，最大的负数为 011 也就是 3。所以 101 只能示意为正数。为了保障同余运算，只有找到另一个数与 5 对于 8 同余即可。

与 5 对于 8 同余的数有很多：13, 21, -3...。这个数还要满足一个条件：最大的正数。所以为：5 - 8 = -3。

补码的引入

通过这种形式，将下面蹩脚的时钟改成遵循同余运算的示意办法：

你可能曾经发现了，这套规范就是咱们常说的补码。

因为遵循同余定理，补码零碎曾经不存在那两个问题了：

• 补码零碎中只有一个 0，不存在歧义。
• 1-1 => 1 + (-1) => 001 + 111 => 000 => 0，加法运算也没有问题。

所以为什么要有补码？因为要保障同余运算。而同余运算，就是整数运算的外围原理。

补码的示意

依据下面的图，很好示意补码：

• 负数和零，没有变动，不必批改。
• 而正数，比方 -1，就是逆时针转动一个小时，依据同余定理，逆时针转动一个小时就代表顺时针转动 7 个小时：

$$
-1 \equiv 7 \pmod 8
$$

也就是说，当符号位为 1，比方 111，在正整数（7）的根底上逆时针旋转 8 个小时就是补码：

补码
----
000 = (2^2 * 0 + 2^1 * 0 + 2^0 * 0)     = 0+0 =  0
001 = (2^2 * 0 + 2^1 * 0 + 2^0 * 1)     = 0+1 =  1
010 = (2^2 * 0 + 2^1 * 1 + 2^0 * 0)     = 2+0 =  2
011 = (2^2 * 0 + 2^1 * 1 + 2^0 * 1)     = 2+1 =  3
100 = (2^2 * 1 + 2^1 * 0 + 2^0 * 0) - 8 = 4-8 = -4
101 = (2^2 * 1 + 2^1 * 0 + 2^0 * 1) - 8 = 5-8 = -3
110 = (2^2 * 1 + 2^1 * 1 + 2^0 * 0) - 8 = 6-8 = -2
111 = (2^2 * 1 + 2^1 * 1 + 2^0 * 1) - 8 = 7-8 = -1

公式示意为：

$$
f(补) =
\begin{cases}
x & 符号位 = 0\\
x-8 & 符号位 = 1
\end{cases}
$$

其中，x = 4a + 2b + c。

如果用程序来示意：

int main()
{
    int n;
    puts("Please input a number, represent a few bytes:");
    scanf("%d", &n);
    int count = 1 << n;

    for (int i = 0; i < count; i++) {if (i >= (1 << n - 1)) { // 如果这个数的符号位为 1
            printf("%d", i - count);
        }
        else printf("%d", i);
    }
    return 0;
}

反码（1’s complement）的误区

在下面解说补码的过程中，并没有提到反码。那为什么有些文章说到补码时，要提到反码？而且咱们常说的反码加上一等于补码又是怎么来的，反码真的能够解决原码相加的问题吗？

先来看看反码的定义：

负数的反码等于其原码，而正数的反码则能够通过保留其 符号位 ，将原码的 数值位 取反失去。

在 3 个字节的有符号整数中，有：

原码  反码
---------
000 = 000 =  0
001 = 001 =  1
010 = 010 =  2
011 = 011 =  3
100 = 111 = -0
101 = 110 = -1
110 = 101 = -2
111 = 100 = -3

你会发现，它怎么和仅仅引入符号位的有符号整数那么眼生。那反码解决了那两个问题了吗？

很显然的是，反码中也有两个零。

那么加法呢？人们最喜爱举的例子为：

$$
1 – 1 = 1 + (-1) = 001_{正} + 101_{正} = 001_{反} + 110_{反} = 111_{反} = -0 = 0
$$

下面的式子能够运算出正确后果。所以在有些文章中就认为反码解决了原码的相加问题。

真的是这样的吗？再来看看一个例子：

$$
-1 + (-2) = 101_{正} + 110_{正} = 110_{反} + 101_{反} = 011_{反} = 3
$$

问题呈现了，加法运算也不成立。

可见，网络上的文章不太靠谱。看文章，抱着狐疑的态度还是很有必要的。

也就是说，反码和原码一样，并不适宜作为有符号整数的示意办法。这也是很多人的误区，认为反码与补码有关系。其实一点关系也没有，尽管是反码加上一等于补码。

那反码加上一等于补码，这又是怎么来的呢？

这是一条论断。

反码加上一等于补码

在 3 个字节中，原码应用 abc~2~ 来示意：

$$
f(原) = \begin{cases}
2^{1} \times b + 2^{0} \times c \\
(2^{1} \times b + 2^{0} \times c) \times (-1)
\end{cases} = \begin{cases}
2b + c & a = 0\\
– (2b +c) & a = 1
\end{cases}
$$

原码转换成反码，正数的符号位不变，其余位取反：

$$
f(反) = \begin{cases}
2^{2} \times a + 2^{1} \times b + 2^{0} \times c \\
2^{2} \times a + 2^{1} \times (1 – b) + 2^{0} \times (1 – c)
\end{cases} = \begin{cases}
2b + c & a = 0\\
-(2b +c) + 7 & a = 1
\end{cases}
$$

原码转换成补码。负数不变。正数，比方 -3 就是 0 - 3，当初能够用负数示意 3，而又依据同余定理 0 - 3 等于 8 - 3，所以原码转补码的正数示意办法为：8 - 负数：

$$
f(补) = \begin{cases}
f(原) \\
f(原) + 8
\end{cases} = \begin{cases}
2b + c & a = 0\\
8 – (2b + c) & a = 1
\end{cases}
$$

当符号位为 0，也就是负数的时候，两者相等。合乎负数时，原反补码雷同。

当符号位为 1，也就是正数。因为要保障符号位为 1，所以 符号位并不参加计算，所以反码和补码的计算就转换成了 2 个字节的无符号加法运算。既然是加法运算，同样遵循同余运算，这里时对于 4 同余。

$$
f(反) + 1 = -(2b + c) + 8 = -(2b + c) \pmod 4 \qquad 3
$$

$$
f(补) = 8 – (2b + c) = -(2b + c) \pmod 4 \qquad 4
$$

联合 3 式与 4 式，有：

$$
f(反) + 1 = f(补)
$$

所以，反码加上一等于补码是这么来的。它并不能作为论断证实反码和补码有任何关系，只是能够通过这种办法，在原码的根底上疾速的得出补码而已。

代码验证

int main()
{
    int8_t two = 2;
    int8_t last = 127;
    printf("%d \n", two);      // 2
    printf("%d \n", last);     // 127
    int8_t temp = two + last; // 顺时针旋转
    printf("%d \n", temp);     // -127
    temp = two - last;         // 逆时针旋转
    printf("%d \n", temp);     // -125
    return 0;
}

下面的思考题换成有符号整数，还是那个后果吗？

int main()
{
    int8_t a = -128;
    int8_t b = a / -1;
    printf("%d", b); // what is it?
    return 0;
}

参考资料

https://zh.wikipedia.org/wiki…

https://www.cnblogs.com/zhang…

https://zh.wikipedia.org/wiki…

https://zh.wikipedia.org/wiki…

https://blog.csdn.net/woodpec…

http://www.ruanyifeng.com/blo…