补数与补码

始于《C++ Primer》中对超出无符号数范围的数的转换，转为无符号数后值为{num} mod {count}， {num}即为原来的数，{count}为无符号数据类型可代表的数的总和，如：
unsigned char可表示0~255共256个数, unsigned char a = -1，实际上a的值为255，由-1 mod 256得出

#模运算

商余定理：
给出任何整数A和一个正整数B，存在唯一整数Q和R，满足：

A = B * Q + R，其中0 <= R < B

A除以B，Q是商，R是余数。以另一种形式书写就是A mod B = R

求A mod B时，R = A - B * Q，求出商Q即可。而由于有多种取整方法，R的值随着取整方法的不同而变化

ceil()，floor()，int()，round()分别为向上取整，向下取整，向零取整以及四舍五入

此处只讨论floor()和int()。并且正数取整时，这两个方法得到的结果相同，因此只讨论负数，即A < 0时

• 向下取整，|Q| > |A/B|，即BQ < A，一个负数减去一个更小的负数得到R > 0
• 向零取整，|Q| < |A/B|，即BQ > A，R < 0

#运算性质

• (A + B) mod C = (A mod C + B mod C) mod C
• (A - B) mod C = (A mod C - B mod C) mod C
• (A * B) mod C = (A mod C * B mod C) mod C
• A^B mod C = ((A mod C)^B) mod C

#同余

A与B模C同余，表示A mod C = B mod C，记作$A\equiv B\pmod{C}$

• C|(A-B)，"|"符号意味整除，C能整除(A-B)，即$\frac{A-B}{C}=K$，与下面相同
• A = B + K * C，A与B之间相差K个C。(K为整数)

同时，一个数X。当A ≡ B(mod C)时，A与B相差K倍的C，有：

(X + A) ≡ (X + B) mod C

#补数

假设现在时间为10点整，要想让时针指向2点，有两种方式：

1. 顺时针拨动4个小时
2. 逆时针拨动8个小时

钟表时间以12为模，在模的范围内，两个相加等于模的数互为补数(complement)

在模的范围内做减法，即逆时针转动8个小时(-8 mod 12 = 4)与做加法，即顺时针转动4个小时(4 mod 12 = 4)得到的结果相同

-8与4同余，有(X + (-8)) mod 12 = (X + 4) mod 12

因此可通过同余，令减法变成加法

在0~99中，以100为模，(30 + (- 40)) mod 100 = (30 + 60) mod 100，"60"可以替代"-40"进行加法运算，但是如果60用来表示-40， 它也有原本的值，造成二义性

为解决该问题，将模范围内的数划分，049区间的表示原来的值，而与之对应的补数来表示其负数，例如99的补数为1即 99表示-1。当然，牺牲了一半的值表示负数，在以100为模的范围内，5099的这些正数就无法表示了。要想取到50~99，可在 更大的模中划分

取模为C，一个半模以下的正整数A，补数为B。B用来表示-A，同时 B - (-A) = C - A + A = C，即B与(-A) mod C同余

#二进制

二进制中划分范围后，半模以下的数最高位为0，半模以上的数最高位为1。这就是补码最高位为符号位的原因

符号位的0, 1并不是为了表示正负，只是半模以上数的二进制最高位为1，该数为正数，用它表示其补数的相反数

假设有一个8位二进制数，它可表示2的8次方共256个数，即0255其模为256。因此0127表示正数， 而128255表示对应补数的相反数，如255的补数为1，即255表示-1。同时，128的补数为128即128用来表示-128， 故8位二进制数的可表示范围为-128127

#补码

-1的原码为1000 0001故其补码为1111 1111对应255，正好是其绝对值的补数。也可得出-128的补码为 其补数128的二进制形式1000 0000

#取反加一

n位二进制数，以2^n为模，取半模以下的数A，补数B = 2^n - A，B表示-A，即B的二进制为-A的补码

A的最高位为0，令其$k_i$代表其余n-1位，$k_i$的值为0或者1

$A=k_0*2^0+k_1*2^1+...+k_{n-1}*2^{n-2}+0*2^{n-1}$$2^n-1=1*2^0+1*2^1+...+1*2^{n-2}$$B=(1-k_0)*2^0+(1-k_1)*2^1+...+(1-k_{n-2})*2^{n-2}+1$

对照B与A的表达式，B为A取反后加1

$(1-k_i)$相当于对$k_i$取反