<算法>分享一个很6666的算法(逆序二进制串)

发表于 算法 2017-04-10 阅读数: 92

来自于LeetCode第190题Reverse Bits,支持率最高的一个答案。https://discuss.leetcode.com/topic/9811/o-1-bit-operation-c-solution-8ms

题目如下:

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).

意思是对一个二进制串进行逆序操作。PS:(LeetCode 是以类的形式提交答案的,uint32_t是32位无符号整形的意思)正常人的解法是这样的:

class Solution{

public:

    uint32_t reverseBits(uint32_t n){

        uint32_t result = 0;

        for(int i = 0;i < 32;++i){

            result = (result << 1) + ((n>>i)& 1);

        }

        return result;

    }

};

意思是对二进制数的每一位右移,让它和1对比,相同则result + 1(result在每次加一或者不加前会左移一个位).

然而有些人却不这样想,他们的代码是这样的:

class Solution {public:

    uint32_t reverseBits(uint32_t n) {

        n = (n >> 16) | (n << 16);

        n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);

        n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);

        n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);

        n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);        

        return n;

    }

};

0xff00ff00就是 1111 1111 0000 0000 1111 1111 0000 0000.0x00ff00ff就是 0000 0000 1111 1111 0000 0000 1111 1111.

0xf0f0f0f0就是 1111 0000 1111 0000 1111 0000 1111 0000.0x0f0f0f0f就是 0000 1111 0000 1111 0000 1111 0000 1111.

0xcccccccc就是 1100 1100 1100 1100 1100 1100 1100 1100.0x33333333就是 0011 0011 0011 0011 0011 0011 0011 0011.

0xaaaaaaaa就是 1010 1010 1010 1010 1010 1010 1010 1010.0x55555555就是 0101 0101 0101 0101 0101 0101 0101 0101.

(PS:你应该知道,一个十六进制就相当于4个二进制)

怎么理解这个算法呢?我们看个例子就知道了。

如对3进行操作:0000 0000 0000 0000 0000 0000 0000 0011

第一步:n = (n >> 16) | (n << 16);

得:0000 0000 0000 0011 0000 0000 0000 0000

第二步:n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);

0000 0000 0000 0011 0000 0000 0000 00001111 1111 0000 0000 1111 1111 0000 0000

结果是:0000 0000 0000 0000 0000 0000 0000 0000再右移8位:0000 0000 0000 0000 0000 0000 0000 0000

0000 0000 0000 0011 0000 0000 0000 00000000 0000 1111 1111 0000 0000 1111 1111

结果是:0000 0000 0000 0011 0000 0000 0000 0000再左移8位:0000 0011 0000 0000 0000 0000 0000 0000

再取或得:0000 0011 0000 0000 0000 0000 0000 0000

第三步:n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);

同理得:0011 0000 0000 0000 0000 0000 0000 0000

第四步: n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);

得:1100 0000 0000 0000 0000 0000 0000 0000

最后一步: n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);    

               n = 1100 0000 0000 0000 0000 0000 0000 00000xaaaaaaaa  : 1010 1010 1010 1010 1010 1010 1010 1010.              &得到: 1000 0000 0000 0000 0000  0000 0000 0000.

0x55555555  :     0101 0101 0101 0101 0101 0101 0101 0101.            &得到: 0100 0000 0000 0001 0100 0000 0000 0000

最终取或得结果 : 1100 0000 0000 0000 0000 0000 0000 0000

也就是类似这样的移位:abcdefgh -> efghabcd -> ghefcdab -> hgfedcba怎么样,这算法是不是很6?

欢迎关注微信公众号:幻象客https://www.huanxiangke.com

欢迎进入极致分享:https://alltoshare.com

幻象客 二维码

Add comment