二进制位的翻转和二进制表示中1的个数

落日映苍穹つ 2022-08-05 12:06 182阅读 0赞

本帖转自[http://blog.csdn.net/todototry/archive/2007/04/23/1575900.aspx][http_blog.csdn.net_todototry_archive_2007_04_23_1575900.aspx]

但是更加详细的说明如下：

这两个函数极很是巧妙，作了并行计算。

# **问题1: 将某数的二进制中各位翻转** #

unsigned char reverse8( unsigned char c )
    {
        c = ( c & 0x55 ) << 1 | ( c & 0xAA ) >> 1;
        c = ( c & 0x33 ) << 2 | ( c & 0xCC ) >> 2;
        c = ( c & 0x0F ) << 4 | ( c & 0xF0 ) >> 4;
        return c;
    }

unsigned int Bit_Reverse(unsigned int v)
    {
        v = ((v >> 1) & 0x55555555) | ((v << 1) & 0xaaaaaaaa);
        v = ((v >> 2) & 0x33333333) | ((v << 2) & 0xcccccccc);
        v = ((v >> 4) & 0x0f0f0f0f) | ((v << 4) & 0xf0f0f0f0);
        v = ((v >> 8) & 0x00ff00ff) | ((v << 8) & 0xff00ff00);
        v = ((v >> 16) & 0x0000ffff) | ((v << 16) & 0xffff0000);
        return v;
    }

算法是这样的: 首先是2位2位为一组，交换前一半和后一半。再4位4位为一组，交换前一半和后一半。再8位为一组，交换前一半和后一半。

可能还有点说不清楚。我举个例子。  
将1 2 3 4 5 6 7 8 反转。  
(1)2个2个为一组，交换前一半和后一半, 变成。  
2 1 4 3 6 5 8 7  
(2)4个4个为一组，交换前一半和后一半， 变成  
4 3 2 1 8 7 6 5  
(3)再8个为一组，交换前一半和后一半, 变成  
8 7 6 5 4 3 2 1  
反转成功。  
这样的算法本来很是简单，很容易用数学归纳法证明其正确。这函数， 巧妙就巧妙在作了并行计算，分组，它一次就计算完了。

先看第一个语句。c = ( c & 0x55) << 1 | ( c & 0xAA ) >> 1;  
0x55其实就是01010101, 0xAA就是10101010  
假设 c=abcdefgh  
c & 0x55 = 0b0d0f0h, c & 0xAA = a0c0e0g0  
跟着，前者左移一位, b0d0f0h0, 后者右移一位, 0a0c0e0g, 再一个|运算，就两位两位交换了位置。  
想象一下，你有一个长纸条，分成一格一格，每格写一个字，假如你将纸条每隔一格剪一个小洞，滑一格，覆盖在原来的纸条上，你就会看到两个两个字交换了位置。  
(注: |运算可以换成+运算，想一想为什么)

第二个语句。 c = ( c & 0x33 ) << 2 | ( c & 0xCC ) >> 2;  
0x33 = 00110011, 0xCC=11001100。

第三个语句。c = ( c & 0x0F ) << 4 | ( c & 0xF0 ) >> 4;  
0x0f = 00001111, 0xF0=11110000.

这两个语句的作用也是 分组，将一半位变成0，移位滑动，跟着再组合，就分组交换了位置。  
不防想象两个小纸条剪洞叠加。

这方法应该可以推广。

理解了问题1，也就很容易理解问题2了.

# **问题2: 判断32位整数二进制中1的个数。** #

unsigned long func(unsigned long x)
    {
        x = (x & 0x55555555UL) + ((x >> 1) & 0x55555555UL);
        x = (x & 0x33333333UL) + ((x >> 2) & 0x33333333UL);
        x = (x & 0x0f0f0f0fUL) + ((x >> 4) & 0x0f0f0f0fUL);
        x = (x & 0x00ff00ffUL) + ((x >> 8) & 0x00ff00ffUL);
        x = (x & 0x0000ffffUL) + ((x >> 16) & 0x0000ffffUL);
        return x;
    }

和问题1一样，也是采用了分组并行计算。

基本方法是: 2位2位为一组，相加，看看有几个1。再4位4位为一组，相加，看看有几个1......  
还是说的不太明白。接着分析。

为了简单说明，先看看8位的情形。相应地，函数里面的语句变成。  
x = (x & 0x55) + ((x >> 1) & 0x55); (1)  
x = (x & 0x33) + ((x >> 2) & 0x33); (2)  
x = (x & 0x0f) + ((x >> 4) & 0x0f); (3)  
return x;

假设x=abcdefgh. 0x55=01010101  
x & 0x55 = 0b0d0f0h. (x>>1) & 0x55 = 0a0c0e0g。相加。就可以知道2位2位一组1的个数。

比如x=11111111  
x= (x & 0x55) + ((x >> 1) & 0x55); 之后x=10101010。你2位2位地看，10=2, 就是2 2 2 2, 就是说各组都是2个1。  
比如x=00101001  
x= (x & 0x55) + ((x >> 1) & 0x55); 之后x=00010101。你2位2位地看，就是0 1 1 1, 前1组只有0个1，后面的组都是1个1。

好啦。再来看。0x33=00110011。  
x=abcdefgh.  
x=(x & 0x33)+((x >> 2)&0x33); 相当于, 00ab00ef + 00cd00gh。  
因为语句(1)之后。ab指示了头两位有多少个1，cd指示了下两位有多少个1。相加00ab+00cd就指示前4位有多少个1。这样就是4位4位为一组。注意这样的分组，组与组之间永远都不会产生进位的。正因为不会产生进位，才可以分开来看。

好啦。下面的过程都是一样的，不再多说。  
8位，16位，32位都一样。

[http_blog.csdn.net_todototry_archive_2007_04_23_1575900.aspx]: http://blog.csdn.net/todototry/archive/2007/04/23/1575900.aspx