Comment on page
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的末尾
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 ]
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
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