算法-二进制

某种程度上讲，二进制也算一种算法？

前言

二进制从定义上讲只是一种数字表示方式。

与你们人类使用的十进制不同，二进制表示法中只有0和1两个数位。

例如，十进制下的 $19$ 在二进制下就表示为 $10011$（注：所有二进制数均省略二进制表示法）。

十进制转换为二进制

二的幂分解

首先需要了解常用的二进制整数（即 $2$ 的幂）：$2,4,8,16,32,\cdots$。

对于一个十进制数，从大到小分解：$19=16+2+1=2^4+2^1+2^0$，所以就表示为 $10011$。

倒序取余

这个方法更常用一些，但是原理不容易理解。具体操作过程如下：

1. 对于一个数 $N_0$，取它除以 $2$ 的商 $N_1$ 和余数 $r_0$。
2. 对得到的 $N_1$ 重复第一步操作，得到商 $N_2$ 和余数 $r_1$。
3. 重复操作至商 $N_n=0$。
4. 找到所有余数 $r_0,r_1,\cdots,r_{n-1}$（共 $n$ 个余数）。
5. 将余数倒序书写：${r_{n-1}},\cdots,r_1,r_0$，得到的就是 $N_0$ 的二进制表示法。

二进制转换为十进制

例如一个二进制数是 $11010$，从右到左依次是第 $0,1,2,3,4$ 位。

所以，十进制表示法就是：

$$1 \times 2^4+1 \times 2^3+0 \times 2^2+1 \times 2^1+0 \times 2^0$$

补码表示法

为了使用0和1表示负数，我们使用补码表示法。

具体是这样的：$2$ 在二进制（一个字节）中是 $0000\ 0010$，为使 $-2+2=0$，只需要让 $-2$ 用 $1110\ 1110$ 表示（忽略溢出位）即可。

对于任意的一个正数，对其取反再加 $1$ 就得到了对应负数的补码表示法。

那么反过来，一个负数先减 $1$ 再取反就是对应的正数。

位操作/位运算

接下来进入程序部分！

首先，定义两个二进制数。

int a = 0b11010;
int b = 0b110100;
int ans = 0; // 用来表示运算结果

对于一般的编程语言，常见的位运算包括：

• 与：两个数都为 $1$ 时，结果才为 $1$。

// Hint:
/*
     11010
  & 110100
  --------
    110000
*/
ans = a & b; // 0b110000

• 或：两个数只要有一个数为 $1$，结果就为 $1$。

// Hint:
/*
     11010
  | 110100
  --------
    111110
*/
ans = a | b; // 0b111110

• 非：$0$ 变成 $1$，$1$ 变成 $0$，即取反。

int具有 $32$ 个二进制位，需要把所有的 $0$ 都取反！

// Hint:
/*
  ~  00000000 00000000 00000000 00011010
  --------------------------------------
     11111111 11111111 11111111 11100101
*/
ans = ~a; // 0b11111111111111111111111111100101

思考：如果a的类型是short或者long long，结果会有不同吗？

• 异或：两个数相同的时候结果为 $0$，不同则为 $1$（最常用）。

// Hint:
/*
     11010
  ^ 110100
  --------
    101110
*/
ans = a ^ b; // 0b101110

• 左移：将数字整体左移 $n$ 位（注意：不要让它溢出！）

// Hint:
/*
     11010 <- 0
  ---------
     110100
*/
ans = a << 1; // 0b110100
// Hint:
/*
     11010 <- 000
  ------------
     110100000
*/
ans = a << 3; // 0b110100000

• 右移：将数字整体右移 $n$ 位。

// Hint:
/*
  0 -> 11010
  ---------
       1101
*/
ans = a >> 1; // 0b1101
// Hint:
/*
  000 -> 11010
  ---------
         11
*/
ans = a >> 3; // 0b11

补充

• lowbit

$\mathrm{lowbit}$ 函数可以获得一个数字的二进制表示中，最低位的 $1$ 及其后面的 $0$ 表示的数。

例如：

• $\mathrm{lowbit}(3)=\mathrm{lowbit}((11)_2)=1$
• $\mathrm{lowbit}(6)=\mathrm{lowbit}((110)_2)=2$
• $\mathrm{lowbit}(100)=\mathrm{lowbit}((110\ 0100)_2)=4$

实现方式：lowbit(x)=x & (-x)。

• __builtin_ffs

这个函数是内置函数，可以直接使用。

作用为：获取最低位的 $1$ 所在的位置（从 $1$ 开始）。

例如：

• $\mathrm{\_\_builtin\_ffs}(2)=\mathrm{\_\_builtin\_ffs((10)_2)}=2$
• $\mathrm{\_\_builtin\_ffs}(3)=\mathrm{\_\_builtin\_ffs((11)_2)}=1$
• $\mathrm{\_\_builtin\_ffs}(100)=\mathrm{\_\_builtin\_ffs((110\ 0100)_2)}=3$
• $\mathrm{\_\_builtin\_ffs}(1024)=\mathrm{\_\_builtin\_ffs((100\ 0000\ 0000)_2)}=11$