回忆一个面试题.

记得公司面试的第一面时有个面试题.

当时回答出来了.

昨天还是前天的时候偶然间想到那个面试官,又想起来当时的那个题来.

不知道怎么解决了.

囧呀.

上网查了一下,记于此处.

有1G的二进制的文件,为得出其中1的个数,每32位取出一次.设计每次读出32位时,对于该32位数据的处理算法.

即:求32位2进制数据当中1的个数.

 

分析:

 

0101 1101  1000 1101  0100 0101  1110 1011

 

数1的个数

二进制数,每一位上的数字都可以当做该位置上1的个数来看.

那么,这个问题就可以从本质上改写成:

32位2进制数,各位之和.

也就是设计一个计算32位二进制数据,每位之和的算法,

这个问题与之前的问题是等价的,但是给人的思路可是差的远吆.

 

一个经典的解决方式,针对32位数据,采用相反与分而治之的思路:

 

1.求相邻两位的和.

2.将相邻的两位作为一个整体,求相邻四位的和.(可以当做,把步骤1得到的结果转化成四进制数,再进行类似步骤1的操作)

3.把相邻的四位作为一个整体,求相邻八位的和.

4.把相邻的八位作为一个整体,求相邻十六位的和.

5.把相邻的十六位作为一个整体,求三十二位的和.

 

 

 

这边有一个流传很广的经典的算法呀.

 

这个是C的代码呀.

/*   
* return number of bits set 
*/ 
#include <stdio.h> 
#include <stdlib.h> 

unsigned int bitcount32(unsigned int x) 
{ 
    x = (x & 0x55555555UL) + ((x >> 1) & 0x55555555UL); // 看一下,5555的二进制,求得相邻两位的和 
    x = (x & 0x33333333UL) + ((x >> 2) & 0x33333333UL); // 求得相邻四位的和
#if 1 
    // Version 1 这个好理解一点.再看一下Version 2 
    x = (x & 0x0f0f0f0fUL) + ((x >> 4) & 0x0f0f0f0fUL); // 求得相邻八位的和 
    x = (x & 0x00ff00ffUL) + ((x >> 8) & 0x00ff00ffUL); // 求得相邻十六位的和
    x = (x & 0x0000ffffUL) + ((x >> 16) & 0x0000ffffUL); //三十二位的和 
    return x; 
#else 
    // Version 2 
    x = (x + (x >> 4)) & 0x0f0f0f0fUL; // 0-7 in 4 bits, 八位的1的个数,最多有八个,可以在四位当中存储. 
    x += x >> 8; // 0-15 in 8 bits 十六位的1的个数,最多有16个,可以在八位当中存储.
    x += x >> 16; // 0-31 in 8 bits 32位的1的个数,最多有32个,可以在八位当中存储 
    return x & 0xff;//取后八位,因为正确的结构保留在后八位.

    //可以画一下二进制的图.它比Version 1要简单,但是所作的一半工作在逻辑上是不必要的.从硬件角度来说,又是没任何差别的.
#endif 
} 

int main() 
{ 
    short nVal; 
    int nCount; 
    printf("Input a value:"); 
    scanf("%d", &nVal); 
    nCount = bitcount32(nVal); 
    printf("BitCount:%d\n", nCount); 
    system("pause"); 
    return 0; 
}