找出特定整数有多少二进制数字
可能重复：
计算快速基数2天花板
在C / C ++中将特定整数从十进制转换为二进制时，找出特定整数有多少二进制数字的最快方法是什么？
防爆。 47 （10） = 101111 （2）
所以47有六位数以二进制表示。
在我最喜欢的比特杂乱的黑客攻击集中呈现的最快的解决方案是使用乘法和查找在O（lg（N））运算中找到N位整数的对数基数2 。 它需要13条指令才能找到数字中的最高设置位。
uint32_t v; // find the log base 2 of 32-bit v int r; // result goes here static const int MultiplyDeBruijnBitPosition[32] = { 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 }; v |= v >> 1; // first round down to one less than a power of 2 v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16; r = MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27]; 要想快速有趣地执行此操作而无需调用数学函数，请检查以下内容：
for (digits = 0; val > 0; val >>= 1) digits++;
作为奖励，这应该煮至内存负载和2个正在使用的寄存器，以获得额外的惊人效果。
如果您在性能方面寻找“最快”的方式，则需要采用特定于平台的方法。
有些架构实际上有一个指令可以做到这一点。
在x86上，您有bsr指令。
在MSVC中，它可以访问：
inline int bitlength(unsigned long x){ if (x == 0) return 0; unsigned long index; _BitScanReverse(&index,x); return (int)(index + 1); }
GCC有__builtin_clz()内在函数 – 它做了类似的事情。
传统的方式
int count = 32; for(int i = 1 << 31; i != 0; i >>= 1, count--) if((number & i) != 0) return count;
您可以通过优化获得更多的乐趣。
编辑2这是我能想到的最快的代码，无需使用位扫描反向操作码。 您可以使用更大的（256条目）LUT并删除最后的IF语句。 在我的测试中，这比在另一篇文章中描述的重复的OR-SHIFT然后LUT方法更快。
int[] Log2_LUT = new int[16]{0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4}; int Log2 (number) { int count = 0; if((number & 0xFFFF0000) != 0) { number >>= 16; count += 16; } if((number & 0x0000FF00) != 0) { number >>= 8; count += 8 } if((number & 0x000000F0) != 0) { number >>= 4; count += 4; } return count + Log2_LUT[number]; }
或者，如果您的x86或x86-64位架构可以使用BSR（位扫描反向）操作码。 你可以找到它的c ++内在的http://msdn.microsoft.com/en-us/library/fbxyd7zd%28v=vs.80%29.aspx
您的问题也与此类似。 计算存储数字所需位数的最快方法是什么
编辑为什么log2的答案不是最佳的…在数学上正确，复杂的浮点运算（正弦，余弦，tan，日志）是现代计算机上执行速度最慢的操作。 由于必须将整数转换为浮点数并且必须将其置于天花板/底板上，这一点更加复杂。
尝试base-2对数：
ceil(log2(n))
尝试使用对数：
ceil(log2(x))
如果速度比可移植性更重要，那么一些编译器提供“计数前导零”function。 这可编译为某些处理器上的单个机器指令，包括现代x86和ARM。 例如，GCC：
CHAR_BIT * sizeof x - __builtin_clz(x)
如果整数至少为1 ，则所需的位为：
floor(log2(x)) + 1
一种方法是……
unsigned int count_bits(unsigned int n) { unsigned int count = 0; if ( n <= 1 ) return 1; do count++; while( n >>= 1 ); return count; }