search
Ctrlk

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 更新： 发现了更赞的做法，一个比一个奇技淫巧。

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

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

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

整个中间过程如下：

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

最后一步的取模操作，将之前的结果以每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的，因此最终取模的过程类似于如下操作

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 ]

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

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

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

中间过程如下：

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

上一页2011-01-09 行列有序矩阵求第K个数下一页2011-01-01 编程之美 1.2 中国相帅问题的一个简洁解法

最后更新于