2011-01-09 字节按位逆序

问题：给一个8位的字节，按位逆序。第一反应给了个简单的做法：

unsigned short intreverse_bit(unsigned short int b)
{
    unsigned short int r = 0;
    for (int i=0; i<8; i++) {
        b >> = 1
        r = (r << 1) | (b & 1);
    }
    return r;
}

每次循环，r左移一位，b取最后一位填充到r的最后一位上，这个解答需要做8次循环，32次操作（左移一次，加法一次，右移一次，按位与一次）。很明显还有更好的做法。

unsigned short int reverse_bit(unsigned short int b)
{
    b = b << 4 + b >> 4;    // &11110000, 56781234
    b = (b & 0x33) << 2 + (b & 0xCC) >> 2;    // &11001100, 78563412
    b = (b & 0x55) << 1 + (b & 0xAA) >> 1;    // &10101010, 87654321

    return b;
}

只需13次操作。

2011-01-18 更新： 发现了更赞的做法，一个比一个奇技淫巧。

第一种解法，还是常用的一个一个的移位的做法。

把输入和输出当作两个队列，每次取一位，然后一个出队一个入队，代码更精简，支持多字节整数。

unsigned int v;     // 要反转的输入，这里的实现支持是多于一个字节的可实现位操作的无符号整数
unsigned int r = v; // r 将会是v的按位反转的结果，下面的for循环会先做右移操作，这里的赋值可以先取得v的最低有效位
int s = sizeof(v) * CHAR_BIT - 1; // 反转后需要做的额外的移位操作次数，CHAR_BIT为8，指一个字节包含的bit数

for (v >>= 1; v; v >>= 1)
{
  r <<= 1;
  r |= v & 1; //取v的最低位的值，并置于r的最低位
  s--;
}
r <<= s; // v为0，s为v中剩余的高位为0的位数，填充到r的末尾

第二种解法，利用64位乘法和取模运算，三步操作解决

unsigned char b; // 反转这个8位的字节

b = (b * 0x0202020202ULL & 0x010884422010ULL) % 1023;

整个中间过程如下：

           0000001000000010000000100000001000000010 -> 0x0202020202
*                                          abcdefgh -> hgfe dcba
---------------------------------------------------
           000000h0000000h0000000h0000000h0000000h0
          000000g0000000g0000000g0000000g0000000g0
         000000f0000000f0000000f0000000f0000000f0
        000000e0000000e0000000e0000000e0000000e0
       000000d0000000d0000000d0000000d0000000d0
      000000c0000000c0000000c0000000c0000000c0
     000000b0000000b0000000b0000000b0000000b0
    000000a0000000a0000000a0000000a0000000a0
---------------------------------------------------
    000000abcdefghabcdefghabcdefghabcdefghabcdefgh0
&   00000010000100010000100010000100010000000010000
---------------------------------------------------
    000000a0000f000b0000g000c0000h000d00000000e0000
%   00000000000000000000000000000000000001111111111
---------------------------------------------------
    000000000000000000000000000000000000000hgfedcba

第一次乘法将字节复制成5份保存在一个64位整数里，第二次AND操作取出在正确位置（反转后的）上的位，每10位一组。这两次操作的结果是将每位放置到组中的正确位置上，注意下面每一位都在组中正确的相对位置上。

000000a 0000f000b0 000g000c00 00h000d000 00000e0000

最后一步的取模操作，将之前的结果以每10位一组合并起来。其中利用到了取模的一个特点，当a<b时，a % b = a，而(a + b ) % p = (a % p + b % p) %p，当a + b < p的时候，就有(a + b ) % p = a % p + b % p。而这五组二进制的数的总和也是小于或等于1111111111的，因此最终取模的过程类似于如下操作

    000000000a 0000000000 0000000000 0000000000 0000000000 % 1111111111 = 000000000a
               0000f000b0 0000000000 0000000000 0000000000 % 1111111111 = 0000f000b0
                          000g000c00 0000000000 0000000000 % 1111111111 = 000g000c00
                                     00h000d000 0000000000 % 1111111111 = 00h000d000
+                                               00000e0000 % 1111111111 = 00000e0000
------------------------------------------------------------------------------------
    000000000a 0000f000b0 000g000c00 00h000d000 00000e0000 % 1111111111 = 00hgfedcba

2011-01-20 补充： 之前的说明是我自己根据朴素的理解想明白的，但是hook同学知道了之后自己拿笔推了个公式出来，对于多项式(P(x))来说，(P(x)\mod (x-1) \equiv)各项参数之和 ，也就是同余： [ (anx^n+a{n-1}x^{n-1}+a{n-2}x^{n-2}+\cdots+a_1)\mod (x-1)=a_n+a{n-1}+a_{n-2}+\cdots+a_1]

hook的证明如下： 设 y=x-1，代入P(x)有 [(an(y+1)^n+a{n-1}(y+1)^{n-1}+a{n-2}(y+1)^{n-2}+\cdots+a_1)\mod y]，根据二项式展开式[ (a+b)^n=\sum{i=0}^{n}C{n}^{i}a^ib^{n-i} ]有 [ (a+1)^n=\sum{i=0}^{n}C{n}^{i}a^i ]，展开得 [ (a_n\sum{i=0}^{n}C{n}^{i}y^i + \cdots + a_1)\mod y = a_n *\sum{i=0}^{n}C{n}^{i}y^i\mod y+\cdots+a_1 \mod y ]，当(i\ne0)时(a_n\sum{i=0}^{n}C{n}^{i}y^i\mod y=0)，当(i=0)时(a_n\sum{i=0}^{n}C_{n}^{i}y^i\mod y=a_n)，因此得证。

我的朴素证法： 设 y = x - 1，代入P(x)有 [ (an(y+1)^n + a{n-1}(y+1)^{n-1} + \cdots + a1)\mod y = a_n(y+1)^n\mod y + a{n-1}(y+1)^{n-1}\mod y + \cdots + a1\mod y ]， 根据模运算法则 ( a^b\mod p = (a \mod p)^b\mod p) 以及 ( (a b)\mod p = ( (a\mod p) (b\mod p) )\mod p )，有 [ a_n(y+1)^n\mod y = (a_n\mod y) ((y+1)\mod y )^n\mod p = a_n 1^n = a_n ]， 因此有 [ (a_n(y+1)^n + a{n-1}(y+1)^{n-1} + \cdots + a1)\mod y = a_n + a{n-1} + \cdots + a_1 ]

第三种解法，仅用64乘法，4步解决

unsigned char b; // reverse this byte

b = ((b * 0x80200802ULL) & 0x0884422110ULL) * 0x0101010101ULL >> 32;

整个过程如下，乘法操作先将要反转的字节复制4份，然后AND操作将每2位分布到一个8位组中，最后乘法将结果叠加起来，中间的一个8位组正好包含完整的逆序结果，最后利用移位操作将这个完整的逆序8位组移至低8位。在将结果赋值回给b的时候，因为b是一个字节，因此近保留了有效的低8位，前面的无效数据全部被舍弃，正好是正确结果。

                                                                                        abcd efgh (-> hgfe dcba)
*                                                      1000 0000  0010 0000  0000 1000  0000 0010 (0x80200802)
-------------------------------------------------------------------------------------------------
                                            0abc defg  h00a bcde  fgh0 0abc  defg h00a  bcde fgh0
&                                           0000 1000  1000 0100  0100 0010  0010 0001  0001 0000 (0x0884422110)
-------------------------------------------------------------------------------------------------
                                            0000 d000  h000 0c00  0g00 00b0  00f0 000a  000e 0000
*                                           0000 0001  0000 0001  0000 0001  0000 0001  0000 0001 (0x0101010101)
-------------------------------------------------------------------------------------------------
                                            0000 d000  h000 0c00  0g00 00b0  00f0 000a  000e 0000
                                 0000 d000  h000 0c00  0g00 00b0  00f0 000a  000e 0000
                      0000 d000  h000 0c00  0g00 00b0  00f0 000a  000e 0000
           0000 d000  h000 0c00  0g00 00b0  00f0 000a  000e 0000
0000 d000  h000 0c00  0g00 00b0  00f0 000a  000e 0000
-------------------------------------------------------------------------------------------------
0000 d000  h000 dc00  hg00 dcb0  hgf0 dcba  hgfe dcba  hgfe 0cba  0gfe 00ba  00fe 000a  000e 0000
>> 32
-------------------------------------------------------------------------------------------------
                                            0000 d000  h000 dc00  hg00 dcb0  hgf0 dcba  hgfe dcba
&                                                                                       1111 1111
-------------------------------------------------------------------------------------------------
                                                                                        hgfe dcba

第四种解法，仅用32位操作，7步解决

b = ((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16;

中间过程如下：

           0000100000000010 -> x0802
*                  abcdefgh
---------------------------
           0000h000000000h0
          0000g000000000g0
         0000f000000000f0
        0000e000000000e0
       0000d000000000d0
      0000c000000000c0
     0000b000000000b0
    0000a000000000a0
---------------------------
    0000abcdefgh00abcdefgh0  -> b * 0x0802LU
&   00000100010000100010000  -> 0x22110
---------------------------
    00000b000f0000a000e0000  -> (b * 0x0802LU & 0x22110LU)

           1000000000100000 -> x8020
*                  abcdefgh
---------------------------
           h000000000h00000
          g000000000g00000
         f000000000f00000
        e000000000e00000
       d000000000d00000
      c000000000c00000
     b000000000b00000
    a000000000a00000
---------------------------
    abcdefgh00abcdefgh00000  -> b * 0x8020LU
&   00010001000010001000000  -> 0x0x88440
---------------------------
    000d000h0000c000g000000  -> (b * 0x8020LU & 0x88440LU)

                        0000 00b0 00f0 000a 000e 0000  -> (b * 0x0802LU & 0x22110LU)
|                       0000 d000 h000 0c00 0g00 0000  -> (b * 0x8020LU & 0x88440LU)
-----------------------------------------------------
                        0000 d0b0 h0f0 0c0a 0g0e 0000
*                       0000 0001 0000 0001 0000 0001  -> 0x10101LU
-----------------------------------------------------
                        0000 d0b0 h0f0 0c0a 0g0e 0000
              0000 d0b0 h0f0 0c0a 0g0e 0000
    0000 d0b0 h0f0 0c0a 0g0e 0000
-----------------------------------------------------
    0000 d0b0 h0f0 dcba hgfe dcba hgfe 0c0a 0g0e 0000
>> 16
-----------------------------------------------------
                        0000 d0b0 h0f0 dcba hgfe dcba
&                                           1111 1111
-----------------------------------------------------
                                            hgfe dcba

这几个解法取自这里，神一般的位操作，撰文留念。