学步园

问题描述

任意给定一个32位无符号整数n，求n的二进制表示中1的个数，比如n = 5（0101）时，返回2，n = 15（1111）时，返回4

这也是一道比较经典的题目了，相信不少人面试的时候可能遇到过这道题吧，下面介绍了几种方法来实现这道题，相信很多人可能见过下面的算法，但我相信很少有人见到本文中所有的算法。如果您上头上有更好的算法，或者本文没有提到的算法，请不要吝惜您的代码，分享的时候，也是学习和交流的时候。

普通法

我总是习惯叫普通法，因为我实在找不到一个合适的名字来描述它，其实就是最简单的方法，有点程序基础的人都能想得到，那就是移位+计数，很简单，不多说了，直接上代码，这种方法的运算次数与输入n最高位1的位置有关，最多循环32次。

int BitCount(unsigned int n)
{
    unsigned int c = 0 ; // 计数器
    while (n > 0)
    {
        if((n & 1) == 1) // 当前位是1
            ++c ; // 计数器加1
        n >>= 1 ; // 移位
    }
    return c ;
}

一个更精简的版本如下

int BitCount1(unsigned int n)
{
    unsigned int c = 0 ; // 计数器
    for (c = 0; n; n >>= 1) // 循环移位
        c += n & 1 ; // 如果当前位是1，则计数器加1
    return c ;
}

 快速法

这种方法速度比较快，其运算次数与输入n的大小无关，只与n中1的个数有关。如果n的二进制表示中有k个1，那么这个方法只需要循环k次即可。其原理是不断清除n的二进制表示中最右边的1，同时累加计数器，直至n为0，代码如下

int BitCount2(unsigned int n)
{
    unsigned int c = 0 ;
    for (c = 0; n; ++c)
    {
        n &= (n - 1) ; // 清除最低位的1
    }
    return c ;
}

为什么n &= (n – 1)能清除最右边的1呢？因为从二进制的角度讲，n相当于在n - 1的最低位加上1。举个例子，8（1000）= 7（0111）+ 1（0001），所以8 & 7 = （1000）&（0111）= 0（0000），清除了8最右边的1（其实就是最高位的1，因为8的二进制中只有一个1）。再比如7（0111）= 6（0110）+ 1（0001），所以7 & 6 = （0111）&（0110）= 6（0110），清除了7的二进制表示中最右边的1（也就是最低位的1）。

查表法

动态建表

由于表示在程序运行时动态创建的，所以速度上肯定会慢一些，把这个版本放在这里，有两个原因

1. 介绍填表的方法，因为这个方法的确很巧妙。

2. 类型转换，这里不能使用传统的强制转换，而是先取地址再转换成对应的指针类型。也是常用的类型转换方法。

int BitCount3(unsigned int n) 
{ 
    // 建表
    unsigned char BitsSetTable256[256] = {0} ; 

    // 初始化表 
    for (int i = 0; i < 256; i++) 
    { 
        BitsSetTable256[i] = (i & 1) + BitsSetTable256[i / 2]; 
    } 

    unsigned int c = 0 ; 

    // 查表
    unsigned char * p = (unsigned char *) &n ; 

    c = BitsSetTable256[p[0]] +  
        BitsSetTable256[p[1]] +  
        BitsSetTable256[p[2]] +  
        BitsSetTable256[p[3]]; 

    return c ; 
} 

先说一下填表的原理，根据奇偶性来分析，对于任意一个正整数n

1.如果它是偶数，那么n的二进制中1的个数与n/2中1的个数是相同的，比如4和2的二进制中都有一个1，6和3的二进制中都有两个1。为啥？因为n是由n/2左移一位而来，而移位并不会增加1的个数。

2.如果n是奇数，那么n的二进制中1的个数是n/2中1的个数+1，比如7的二进制中有三个1，7/2 = 3的二进制中有两个1。为啥？因为当n是奇数时，n相当于n/2左移一位再加1。

再说一下查表的原理

对于任意一个32位无符号整数，将其分割为4部分，每部分8bit，对于这四个部分分别求出1的个数，再累加起来即可。而8bit对应2^8 = 256种01组合方式，这也是为什么表的大小为256的原因。

注意类型转换的时候，先取到n的地址，然后转换为unsigned char*，这样一个unsigned int（4 bytes）对应四个unsigned char（1 bytes），分别取出来计算即可。举个例子吧，以87654321（十六进制）为例，先写成二进制形式-8bit一组，共四组，以不同颜色区分，这四组中1的个数分别为4，4，3，2，所以一共是13个1，如下面所示。

10000111 01100101 01000011 00100001 = 4 + 4 + 3 + 2 = 13

静态表-4bit

原理和8-bit表相同，详见8-bit表的解释

int BitCount4(unsigned int n)
{
    unsigned int table[16] = 
    {
        0, 1, 1, 2, 
        1, 2, 2, 3, 
        1, 2, 2, 3, 
        2, 3, 3, 4
    } ;

    unsigned int count = 0 ;
    while (n)
    {
        count += table[n & 0xf] ;
        n >>= 4 ;
    }
    return count ;
}

静态表-8bit

首先构造一个包含256个元素的表table，table[i]即i中1的个数，这里的i是[0-255]之间任意一个值。然后对于任意一个32bit无符号整数n，我们将其拆分成四个8bit，然后分别求出每个8bit中1的个数，再累加求和即可，这里用移位的方法，每次右移8位，并与0xff相与，取得最低位的8bit，累加后继续移位，如此往复，直到n为0。所以对于任意一个32位整数，需要查表4次。以十进制数2882400018为例，其对应的二进制数为10101011110011011110111100010010，对应的四次查表过程如下：红色表示当前8bit，绿色表示右移后高位补零。

第一次（n & 0xff）             10101011110011011110111100010010

第二次（(n >> 8) & 0xff）  00000000101010111100110111101111

第三次（(n >> 16) & 0xff）00000000000000001010101111001101

第四次（(n >> 24) & 0xff）00000000000000000000000010101011

int BitCount7(unsigned int n)

{

    unsigned int table[256] =

    {

        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,

        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,

        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,

        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,

        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

        2, 3, 3, 4, 3, 4, 4,