一道面试题（如何解决）

一道面试题（怎么解决）
写一个函数将一个DWORD类型,2进制,位数为1的个数返回出来？
用什么方法写啊，有那位高手指导一下？

------解决方案--------------------

C/C++ code


//假定你的环境下unsigned int 为32位,否则换个unsigned long也行
char table16[16] = { 0,1,1,2, 1,2,2,3, 1,2,2,3, 2,3,3,4} ;
char table256[256];
void    SetData()
{
    for (int i = 0; i < 16; i++)
        for (int j = 0; j < 16; j++)
            table256[i*16+j] = table16[i] + table16[j];
}

unsigned int bitcount32_1(unsigned int 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; 
}

unsigned int bitcount32_2(unsigned int x)
{
    x = x - ((x >> 1) & 0x55555555UL);  
    x = (x & 0x33333333UL) + ((x >> 2) & 0x33333333UL);  
    
    x = (x + (x >> 4)) & 0x0f0f0f0fUL;  
    x += x >> 8; 
    x += x >> 16;  
    
    return x & 0x3f; 
}

unsigned int bitcount32_3(unsigned int x)
{
    return table16[x&0xf]+table16[(x>>4)&0xf]+table16[(x>>8)&0xf]+table16[(x>>12)&0xf] +
        table16[(x>>16)&0xf]+table16[(x>>20)&0xf]+table16[(x>>24)&0xf]+table16[(x>>28)&0xf];
}

unsigned int bitcount32_4(unsigned int x)
{
    return table256[x&0xff] + table256[(x>>8)&0xff]+
        table256[(x>>16)&0xff] + table256[(x>>24)&0xff];
}

一道面试题（如何解决）

相关推荐