位运算: 基本知识

硬件加速的二进制算法

求最高有效位

• 定义末位为第零位

• __builtin_clz()：原理bsr(bit scan reserve,逆向位扫描)，可视作O(1)，能求出前导零个数

  参数为零时返回结果未定义

  最高有效位为31-__builtin_clz()

• __lg()：直接给出，实际上编译后代码与上述方法一致

  且该方法是log2()的优替，快速返回一个整数的以$2$为底对数的下取整

与运算

基本性质

• 与运算只保留两个操作数共同拥有的$1$

掩码

• 判奇偶性：$A\&1=1?奇:偶$

• 模$2^n$：$A\%2^n=A\&((1<<n)-1)$

• 判断二进制码子集：若$B$是$A$的子集，则$A\&B=B$

计$1$的个数

• 调用库函数：C++:__builtin_popcount()、Java:Integer.bitCount()

• 暴力算法：

  c++

  while (x) {
      ans += x & 1;
      x >>= 1;
  }

• Brian Kernighan算法：跳过最右$1$和末位中间的零，直接对该一计数

  $k=x\&(x-1)$的性质是：$k$和$x$相差最右边的$1$

  迭代直到$x=0$，循环次数即一的个数

  c++

  while (x) {
      x &= x - 1;
      ++ans;
  }

• 分治算法(Java bitCount()所用方法)：

  • 问题难点在于不知道哪里有$1$，也就无从统计

    暴力算法是遍历所有位(优化后的BK算法也是O(n))使$1$加起来，换言之，就是将$n$位数分成$n$组

    那么，分治算法的思想是遍历所有两位，将其分为$\frac n2$组，使$1/2$加起来

    c++

    while (x) {
        // 这里需要先以每两位为一组, 求得1的个数, 覆盖回x
        ans += x & 3; // 3 == 0b0000....0011
        x >>= 2;
    }

    那么首先就要知道每个组是$0/1/2$中的哪个数：

  • 将整数以每两位为一组划分，要求出每组的$1$的个数，就是要求每组中所有位的加和

    其对应关系为$\begin{matrix}原码&(1的个数)_2\\00&00\\01&01\\10&01\\11&10\end{matrix}$，那么如何将这个计量关系快速算出，且每组间互不影响？

    首先，取掩码$\rm 0b0101..0101$，即$\rm 0x55..5$，相与后能将每组中位于奇位置的$1$保留，偶位置全为零

    让原整数右移一位，则原本处于偶位置的$1$移到奇位置，原本处于奇位置的$1$移位相与后为零(故不影响其它组)

    将两次相与的结果相加，每组中$1$的个数就得到了，因为加和最大为$2$，故每组是独立的

  • 当然，分治算法不能满足于如此，这样还需遍历$\frac n2$次

    既然一次合并就能降低一半复杂度了，尝试继续合并，最后$ans=x\&(全1)=x$

    重复上述过程，但以每四位为一组划分：

    类似上述掩码，取$\rm 0b0011..0011$，即$\rm 0x33..3$，结果为$x\&M+(x>>2)\&M$

    形象表达：将$x$看作四进制数，每两位四进制数(即每四位为一组)为一组，求每组所有位的加和；即$\begin{matrix}(原码)_4&(所有位的加和)_4\\00&00\\01/10&01\\02/20/11&02\\21/12&03\\22&10\end{matrix}$，因为加和最大为$4$，故每组间独立计算，互不影响

    重复每$2n$一组的划分，直到只剩下一组，对这一组完成最后的统计后，则剩余整数就是所求

    以$32$位整数为例，最终一次运算应以$32$位为一组，$M={\rm 0x0000ffff}、x=x\&M+(x>>16)\&M$，此时$x$就是所求

  • c++

    // 对int/unsigned int  32位整数:
    x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
    x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);
    x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff); // 此时x为所求
    

• 分治算法在位运算上的优化(我也没想到这还能优化)：

  • 对第一步：每组中原码和统计后码值的关系可优化为原码减去偶数位值：节省一次与运算

    $\begin{matrix}原码&计算过程&1的个数\\00&00-0&00\\01&01-0&01\\10&10-1&01\\11&11-1&10\end{matrix}$，即x -= (x >> 1) & 0x55555555

  • 对第三步：因为经过前两步后，以每$8$位为一组时，组中所有位加和最多为$8$，最多占四位，因此可以先让高位和低位相加后再相与(相与为了去除组间的影响)：

    x = (x + (x >> 4)) & 0x0f0f0f0f

    根据这个思路，第一、二步无法通过这种方法优化，第一步最多占两位，第二步最多占三位，因此不能先加再与；第三步以后均可通过该方法优化

  • 对更后面的步骤(第四步及以后)：每组加和的最大值所需位数远小于每组位数的一半，例如第四步中，每组加和最大为$16$，占五位；而每组位数的一半为$8$

    因此从上一个组移到下一个组的位不会有影响，例如：

    ​ 第三步后：$\rm0x\ 0a_0\ 0a_0..0a_0$，$a_0\le1000$，若后续不和掩码相与

    ​ 第四步后：$\rm0x\ 0a_0bb_0\ aa_1bb_0..aa_1bb_0$

    ​ $bb_0=a_{0h}+a_{0l}\le10000、aa_1=a_{0up}+a_{0h}\le10000$

    ​ 第五步后：$\rm0x\ 0a_0bb_0\ aa_2cc_0\ aa_3cc_0..aa_3cc_0$

    ​ $cc_0=bb_{0h}+bb_{0l}\le100000、aa_2=0a_0+aa_1\le11000、aa_3=aa_1+aa_1\le100000$

    ​ 若和掩码相与：第四步$\rm0x00bb00bb..00bb$、第五步$\rm0x000000cc..000000cc$

    上述$cc$(有效位)只要在八位之内，多余位就可在最后一步和掩码相与后除去

    换言之，只要在计数之前除去多余位即可；由于$32$位整数本就只用$6$位，因此第四、五步可以不与：

    c++

    x -= (x >> 1) & 0x55555555;
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0f0f0f0f;
    x += x >> 8;
    x += x >> 16;
    x &= 0x3f; // 最后保留末6位即可
    // 推广到64位, 因为有效位为7, 故:
    // (在第五步之后)
    x += x >> 32;
    x &= 0x7f;

  • 和乘法的结合：和上述思想类似，因为有效位只有六位，在第三步后每组八位，就可在第三步后将末三组移到最高八位相加(末三组总和不超过六位，故不会影响最高组)

    即：$(x+x<<8+x<<16+x<<24)>>24$，分配律到乘法

    即：$(x\cross\rm0x1010101)>>24$，乘法得出的高位应强制转换成int来舍去它们

    乘法效率其实不如上述优化强，但代码更简洁：

    c++

    unsigned int y = x;
    y -= (y >> 1) & 0x55555555;
    y = (y & 0x33333333) + ((y >> 2) & 0x33333333);
    y = (((y >> 4) & 0x0f0f0f0f) * 0x1010101) >> 24;

异或运算

基本性质

• 异或运算后，两操作数相同位得零、不同位得一

• 异或运算是一种对称加密：$A=(A\oplus B)\oplus B、B=(A\oplus B)\oplus A$

  • 不通过第三个变量交换两个整数：$A\oplus B\rightarrow A、A\oplus B\rightarrow B、A\oplus B\rightarrow A$
  • $A\oplus\bar A=全1、A\oplus A=0$

• 满足差分性质：

汉明距离

• 汉明距离：两个整数中不同位的个数

• 计算一：调用库函数

  c++

  __builtin_popcount(x ^ y);