了解有多少二进制数字某个整数有 [英] Find out how many binary digits a particular integer has

问题描述

可能重复：
  计算快速日志基地2天花板

什么是找出有多少二进制数字某个整数具有当它从十进制转换成二进制的C / C最快的方​​式++？

What is the fastest possible way to find out how many binary digits a particular integer has when it is converted from decimal to binary in C/C++?

例。 47 <子>（10） = 101111 <子>（2）

Ex. 47₍₁₀₎ = 101111₍₂₎

所以47有6位重新psented二进制$ P $。

So 47 has 6 digits represented in binary.

推荐答案

最快的解决方案，这是psented在我喜欢收集位摆弄黑客是找到N位整数的中澳日志基地2（ LG（N））与乘法和查找操作。它需要13条指令找到一个数的最高设置位。

The fastest solution that's presented at my favorite collection of bit twiddling hacks is Find the log base 2 of an N-bit integer in O(lg(N)) operations with multiply and lookup. It requires 13 instructions to find the highest set bit in a number.

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

这篇关于了解有多少二进制数字某个整数有的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！