517编程普及组数学之二进制

wsq1272024-04-162024-05-19

写在最前

二进制是计算机内部运算中采用的进制，在这样的进制系统下，只有 $0,1$ 两个数字，计算机内部的所有运算（包括位运算)都是在二进制的基础上进行的。

第一位是符号位，0 表示正数，1 表示负数，其余位是数值位，正常二进制。

$[+11]=[00001011]原$

$[-11]=[10001011]原$

原码是人脑最容易理解和计算的表示方式。

正数的反码是其本身；

负数的反码是在其原码的基础上，符号位不变，其余各个位取反。

$[+11]=[00001011]原=[00001011]反$

$[-11]=[10001011]原=[11110100]反$

正数的补码是其本身；

负数的补码是在其反码的基础上 $+1$。

$[+11]=[00001011]原=[00001011]补$

$[-11]=[10001011]原=[11110101]补$

具体演变过程，我不细讲了，感兴趣自行 Bing。

我们只需要知道，在计算机中，数字是以补码的形式存在的。

$2 - 1 = 2 + (-1) = [0000 0010]原+ [1000 0001]原= [1000 0011]原= -3$

如果用原码表示，让符号位也参与计算，显然对于减法来说，结果是不正确的。

$2 - 1 = 2 + (-1) = [0000 0010]原+ [1000 0001]原= [0000 0010]反+ [1111 1110]反= [0000 0000]反= [0000 0000]原= 0$

发现用反码计算减法，仍然是有问题的。

$2 - 1 = 2 + (-1) = [0000 0010]原+ [1000 0001]原= [0000 0011]补 [1111 1111]补= [0000 0001]补= [0000 0001]原= 1$

而用补码计算，运算结果是正确的。

运算	C++ 运算符	数学符号	解释
与	`&`	$	只有两个对应位都为 $1$ 时才为 $1$
或	`	`	\|
异或	`^`	$\oplus$	只有两个对应位不同时才为 $1$

注意：与逻辑与 $\and$ 和逻辑或 $\or$ 区分。

异或运算的逆运算是它本身，也就是说两次异或同一个数最后结果不变，即 $a\oplus b\oplus b=a$。

字面意思，当前位是 $1$ 取反后则是 $0$，反之同理。

取反暂时并没有数学符号，他在 C++ 中的运算符为 ~。

位移包括左移和右移：

对于位移，溢出的位将被舍弃，而原先没有数的位置会用 $0$ 替补。

还有一个很好玩的东西叫做 lowbit，它的作用是求出一个数最低位的 1 在从右往左第几位。

实现起来很简单(x&-x)，有没有感觉很神奇？甚至不相信？

让我们验算以下，以 $x=14$ 为例：

原理：对于 $x$，$-x$ 用反码表示就是全部取反了，包括符号位，而补码则是再加一，而加一后最后一个 0 也就是原码中最后一个 1 就会变成 1 和原来的 & 后就会得到这一位。