算法-二进制

Posted on Edited on Word count in article: 795

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

前言

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

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

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

十进制转换为二进制

二的幂分解

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

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

倒序取余

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

  1. 对于一个数 N0N_0，取它除以 22 的商 N1N_1 和余数 r0r_0。
  2. 对得到的 N1N_1 重复第一步操作，得到商 N2N_2 和余数 r1r_1。
  3. 重复操作至商 Nn=0N_n=0。
  4. 找到所有余数 r0,r1,⋯ ,rn−1r_0,r_1,\cdots,r_{n-1}（共 nn 个余数）。
  5. 将余数倒序书写：rn−1,⋯ ,r1,r0{r_{n-1}},\cdots,r_1,r_0，得到的就是 N0N_0 的二进制表示法。

二进制转换为十进制

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

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

1×24+1×23+0×22+1×21+0×201 \times 2^4+1 \times 2^3+0 \times 2^2+1 \times 2^1+0 \times 2^0

补码表示法

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

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

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

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

位操作/位运算

接下来进入程序部分！

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

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

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

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

    1
    2
    3
    4
    5
    6
    7
    8
    // Hint:
    /*
         11010
      & 110100
      --------
        110000
    */ 
    ans = a & b; // 0b110000

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

    1
    2
    3
    4
    5
    6
    7
    8
    // Hint:
    /*
         11010
      | 110100
      --------
        111110
    */ 
    ans = a | b; // 0b111110

  • 非：00 变成 11，11 变成 00，即取反。

    int具有 3232 个二进制位，需要把所有的 00 都取反！

    1
    2
    3
    4
    5
    6
    7
    // Hint:
    /*
      ~  00000000 00000000 00000000 00011010
      --------------------------------------
         11111111 11111111 11111111 11100101
    */ 
    ans = ~a; // 0b11111111111111111111111111100101

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

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

    1
    2
    3
    4
    5
    6
    7
    8
    // Hint:
    /*
         11010
      ^ 110100
      --------
        101110
    */ 
    ans = a ^ b; // 0b101110

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    // Hint:
    /*
         11010 <- 0
      ---------
         110100
    */ 
    ans = a << 1; // 0b110100
    // Hint:
    /*
         11010 <- 000
      ------------
         110100000
    */ 
    ans = a << 3; // 0b110100000

  • 右移：将数字整体右移 nn 位。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    // Hint:
    /*
      0 -> 11010 
      ---------
           1101
    */ 
    ans = a >> 1; // 0b1101
    // Hint:
    /*
      000 -> 11010
      ---------
             11
    */ 
    ans = a >> 3; // 0b11

补充

  • lowbit\mathrm{lowbit}

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

    例如：

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

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

  • __builtin_ffs\mathrm{\_\_builtin\_ffs}

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

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

    例如：

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