求快速算整数比特位数算法解决思路

求快速算整数比特位数算法
int bits_of_num(unsigned long num)
{
  int i = 0;
  while(num)
  {
  i++;
  num >>= 1;
  }
  return i;
}

以上函数计算整数num的二进制比特位数。
如：num = 25, 其二进制数 bin(num) = 11001，有5位，则 bits_of_num(25) = 5;
  num = 100，其二进制数 bin(num) = 1100100，有7位，则 bits_of_num(100) = 7;

现求比上述函数更快的算法。万分感谢！


[解决办法]

C/C++ code

#pragma hdrstop#include <intrin.h>#include <iostream>using namespace std;#define __breaker 4// 因为代码比较复杂，未必就能比直接循环查找快int bitscan(int in_x){    int l = 0, r = 32;    if (in_x == 0)    {        return -1;    }    for (;;)    {        if (r - l <= __breaker)        {            break;        }        else        {            int m = l + r >> 1;            int t = 1 << m;            if ((unsigned int)in_x > (unsigned int)t)            {                l = m;            }            else if ((unsigned int)in_x < (unsigned int)t)            {                r = m;            }            else            {                return m;            }        }    }    for (; r-- > l;)    {        int t = 1 << r;        if ((unsigned int)in_x >= (unsigned int)t)        {            return r;        }    }}int main(){    for (int i = 1; i; i++)    {        unsigned long r;        // 直接调用CPU指令的方法        _BitScanReverse(&r, i);        if (r != bitscan(i))        {            cout << "wrong" << endl;            break;        }    }}
[解决办法]
C/C++ code
要快肯定查表三...int foobar( uint32 x ){#define XTAB1(  a )        ((a)>=128?8:(a)>=64?7:(a)>=32?6:(a)>=16?5:(a)>=8?4:(a)>=4?3:(a)>=2?2:(a))#define XTAB4(  a )        XTAB1( a+0 ) , XTAB1( a+1 ) , XTAB1( a+2 ) , XTAB1( a+3  )#define XTAB16( a )        XTAB4( a+0 ) , XTAB4( a+4 ) , XTAB4( a+8 ) , XTAB4( a+12 )    static const int tab[] = {        XTAB16(0x00) , XTAB16(0x10) , XTAB16(0x20) , XTAB16(0x30) ,        XTAB16(0x40) , XTAB16(0x50) , XTAB16(0x60) , XTAB16(0x70) ,        XTAB16(0x80) , XTAB16(0x90) , XTAB16(0xA0) , XTAB16(0xB0) ,        XTAB16(0xC0) , XTAB16(0xD0) , XTAB16(0xE0) , XTAB16(0xF0)             };    return  x&0xff000000?24+tab[x>>24]:            x&0x00ff0000?16+tab[x>>16]:            x&0x0000ff00? 8+tab[x>> 8]:                            tab[x>> 0];}