求快速算整数比特位数算法

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;

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

12 个解决方案

#1

0到0x8000000总归还是递增排列的，所以可以二分
x86上有_BitScanReverse

#2

引用 1 楼 bluewanderer 的回复:

0到0x8000000总归还是递增排列的，所以可以二分
x86上有_BitScanReverse

不好意思，没看明白，求细节~ 

#3

#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;
		}
	}
}

#4

要快肯定查表三...

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];
}

#5

表是好东西TxT...

#6

期待各种答案，先谢谢楼上两位啊，明天结贴。。。

#7

能用_BitScanReverse尽量用那个，应该是个最多两个周期的指令。对应机器指令bsr。GCC上可能名字不一样，_BitScanReverse是VC上的。如果要兼容多种CPU，就用查表了。如果要兼容多种CPU而且内存不够用的话就只能用我那个二分将就了应该x_x...

#8

速度稳定的方法

int count(register   unsigned   int   x)
{
      x = (x & 0x55555555) + ((x >> 1) & 0x55555555); 
      x = (x & 0x33333333) + ((x >> 2) & 0x33333333); 
      x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F); 
      x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF); 
      x = (x & 0x0000FFFF) + ((x >>16) & 0x0000FFFF); 
      return(x   &   0x0000003f);
}

#9

引用 8 楼 mstlq 的回复:

速度稳定的方法

C/C++ code

int count(register   unsigned   int   x)
{
      x = (x & 0x55555555) + ((x >> 1) & 0x55555555); 
      x = (x & 0x33333333) + ((x >> 2) & 0x33333333); 
  ……

这个计算结果不对哦~
用这个方法，不同的数字的结果如下：
num = 1, bits = 1
num = 2, bits = 1
num = 3, bits = 2
num = 4, bits = 1
num = 5, bits = 2
num = 25, bits = 3
num = 1024, bits = 1

#10

引用 8 楼 mstlq 的回复:

速度稳定的方法

C/C++ code

int count(register   unsigned   int   x)
{
      x = (x & 0x55555555) + ((x >> 1) & 0x55555555); 
      x = (x & 0x33333333) + ((x >> 2) & 0x33333333); 
  ……

你这个是计算有多少个1的吧？哈哈

#11

我写了个程序测试了一下，下面是测试结果：

（以下皆为某一相同计算量的前提下）
我最开始的方法：处理器时间为 220000
bluewanderer的二分法：处理器时间为 80000
mLee79的查表方法：处理器时间为 30000

mLee79的方法获胜。非常感谢bluewanderer和mLee79

#12

请教查表算法