32位整数的二进制位数解决办法

32位整数的二进制位数
求任意32位整数的二进制位数的算法
比如,4用二进制表示为100,二进制位数为3.
8表示为1000,二进制位数为4,等等
要求效率高,

------解决方案--------------------
#include <stdio.h>
#include <stdlib.h>

int main()
{
long l=4;
char tmp[40]={0};
itoa(l, tmp, 2);
printf( "%ld~%s, count=%d.\n ", l, tmp, strlen(tmp));
system( "PAUSE ");
return 0;
}
------解决方案--------------------
查表法应该更快：

int get_bit_num(unsigned int m) {
static const int TABLE[256] = {
0,
1,
2, 2,
3, 3, 3, 3,
4, 4, 4, 4, 4, 4, 4, 4,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8
};
const int size = sizeof(unsigned int);

for(int i = 0; i < size; ++i) {
const int low_bits = 8 * (size - i - 1);
unsigned int t = m > > low_bits;
if(TABLE[t]) {
return TABLE[t] + low_bits;
}
}
return 0;
}
------解决方案--------------------
typedef unsigned int UINT32;

const UINT32 GetBits( const UINT32 u32Num )
{
/* 这是我从 HugeCalc 源代码中抽取的，保证很快！*/

UINT32 u32Bits;
_asm
{
bsr eax, u32Num
mov [u32Bits], eax
}

return ++u32Bits;
}
------解决方案--------------------
突然想到完全二叉查找树，不知道效率如何

int search(long int n){
static long int tree[64]={ 0,
0xffff0000,0xff000000,0x0000ff00,/*第1,2层*/
0xf0000000,0x00f00000,0x0000f000,0x000000f0,/*3*/
0xc0000000,0x0c000000,0x00c00000,0x000c0000,/*4*/
0x0000c000,0x00000c00,0x000000c0,0x0000000c,/*4*/
0x80000000,0x40000000,0x08000000,0x04000000,/*5*/
0x00800000,0x00400000,0x00080000,0x00040000,/*5*/
0x00008000,0x00004000,0x00000800,0x00000400,/*5*/
0x00000080,0x00000040,0x00000008,0x00000004,/*5*/
32,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,/*6*/
16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1/*6*/
};
int i=1; /* root */
while (i <32) {
if(tree[i] & n)
i < <= 1; /*left child*/
else {
i < <= 1; /*right right*/
i ++;
}
}
return tree[i];
}
------解决方案--------------------
构建一个栈

while(!n)
{
n%2入栈;
n/=2;
}

逐个弹出栈,得答案