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 >> = 1r = (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, 56781234b = (b & 0x33) << 2 + (b & 0xCC) >> 2; // &11001100, 78563412b = (b & 0x55) << 1 + (b & 0xAA) >> 1; // &10101010, 87654321return 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的末尾
unsigned char b; // 反转这个8位的字节b = (b * 0x0202020202ULL & 0x010884422010ULL) % 1023;
整个中间过程如下：
0000001000000010000000100000001000000010 -> 0x0202020202* abcdefgh -> hgfe dcba---------------------------------------------------000000h0000000h0000000h0000000h0000000h0000000g0000000g0000000g0000000g0000000g0000000f0000000f0000000f0000000f0000000f0000000e0000000e0000000e0000000e0000000e0000000d0000000d0000000d0000000d0000000d0000000c0000000c0000000c0000000c0000000c0000000b0000000b0000000b0000000b0000000b0000000a0000000a0000000a0000000a0000000a0---------------------------------------------------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 = 000000000a0000f000b0 0000000000 0000000000 0000000000 % 1111111111 = 0000f000b0000g000c00 0000000000 0000000000 % 1111111111 = 000g000c0000h000d000 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 ]
unsigned char b; // reverse this byteb = ((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 00000000 d000 h000 0c00 0g00 00b0 00f0 000a 000e 00000000 d000 h000 0c00 0g00 00b0 00f0 000a 000e 00000000 d000 h000 0c00 0g00 00b0 00f0 000a 000e 00000000 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
b = ((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16;
中间过程如下：
0000100000000010 -> x0802* abcdefgh---------------------------0000h000000000h00000g000000000g00000f000000000f00000e000000000e00000d000000000d00000c000000000c00000b000000000b00000a000000000a0---------------------------0000abcdefgh00abcdefgh0 -> b * 0x0802LU& 00000100010000100010000 -> 0x22110---------------------------00000b000f0000a000e0000 -> (b * 0x0802LU & 0x22110LU)
1000000000100000 -> x8020* abcdefgh---------------------------h000000000h00000g000000000g00000f000000000f00000e000000000e00000d000000000d00000c000000000c00000b000000000b00000a000000000a00000---------------------------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 00000000 d0b0 h0f0 0c0a 0g0e 00000000 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
这几个解法取自这里，神一般的位操作，撰文留念。
