编程之美-求二进制1的个数

水深无声 2022-08-06 14:08 245阅读 0赞

一个在常见的题目，但是看到编程之美的时候才发现，方法真多，今天来总结一下：

解法一

可以举出一个八位的二进制例子来进行分析。对于一个二进制操作，我们知道，除以一个2，原来的数字将会减少一个0，如果除的过程中有余，那么就表示当前位置有一个1.

以10 100 010为例：

第一次除以2时，商为 1 010 001，余为 0。

第二次除以2时，商为 101 000，余为1。

因此可以根据整型除法的特点求解，代码如下：

public int countBit1(int n) {
    		int num = 0;
    		while (n != 0) {
    			if (n%2 == 1) {
    				num++;
    			}
    			n /= 2;
    		}
    		return num;
    	}

解法二  
显然解法二不是最优的，熟悉计算机的都知道，除法的底层是怎么实现的，当然是按移位来完成的，所以移位版的代码

public int countBit2(int n) {
    		int num = 0;
    		while (n != 0) {
    			if ((n & 0x01) == 1) {
    				num++;
    			}
    			n >>>= 1;
    		}
    		return num;
    	}

代码是不是有点长，在简化下：

public int countBit21(int n) {
    		int num = 0;
    		while (n != 0) {
    			num += (n & 1);
    			n >>= 1;
    		}
    		return num;
    	}

解法三

看完上面那个算法，都算是很多人的极限了，在也想不出了好的办法了。分析上面那个算法的复杂度，如果是一个8Bit的整型，需要遍历8次，32Bit的，需要遍历32次。

我们的目的是计算出1的个数，但是我们为啥要去遍历0呢？比如8bit的32： 00 100 000，我们在浪费在了判断是否为0，所以思路来了，直捣黄龙，算法复杂度只与1的个数有关，上代码：

public int countBit3(int n) {
    		int num = 0;
    		while (n != 0) {
    			n &= (n-1);//每一次去掉最右边的一个1（二进制）
    			num++;
    		}
    		return num;
    	}

解法四

到此为止，还有没有更高效的方法？《编程之美》给出的方法是用空间换时间，直接给出Table表，然后直接查询。在频繁使用此函数，此思路也是可取的。但是这个表示怎么生成的？难不成是一个一个数的么？肯定不是，上代码：

static const unsigned char BitsSetTable256[256] = 
    {
    #   define B2(n) n,     n+1,     n+1,     n+2
    #   define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)
    #   define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)
       B6(0), B6(1), B6(1), B6(2)
    };
    // To initially generate the table algorithmically:
    BitsSetTable256[0] = 0;
    for (int i = 0; i < 256; i++)
    {
       BitsSetTable256[i] = (i & 1) + BitsSetTable256[i / 2];
    }

为啥突然改C版本了，因为这段代码太难了，也没细看，多层递归。牛逼的读者可以解答一下。

解法五

是不是疯了，还有解法？对，最后一个大招。。。

public int countBit4(int v) {
    		int c; // store the total here
    		int S[] = {1, 2, 4, 8, 16}; // Magic Binary Numbers
    		int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF};
    
    		c = v - ((v >> 1) & B[0]);
    		c = ((c >> S[1]) & B[1]) + (c & B[1]);
    		c = ((c >> S[2]) + c) & B[2];
    		c = ((c >> S[3]) + c) & B[3];
    		c = ((c >> S[4]) + c) & B[4];
    		return c;
    	}

有没有感觉要疯，给个link自己看吧，大招实在是太多了。。。

[http://graphics.stanford.edu/~seander/bithacks.html\#CountBitsSetParallel][http_graphics.stanford.edu_seander_bithacks.html_CountBitsSetParallel]

[http_graphics.stanford.edu_seander_bithacks.html_CountBitsSetParallel]: http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel