是否有一个内置函数可以快速计算int占用了多少位?

Question

我试图计算int占用了多少位，例如:count(10)=4,count(7)=3,count(127)=7等。
我尝试过强制使用(<<使用1，直到它严格大于数字)并使用floor(log2(v))+1，但两者对于我的需求来说都太慢了。
我知道存在一个__builtin_popcnt函数，可以快速计算int中有多少1s，但是我很难找到适合我的应用程序的内置函数，是否没有这样的函数或者我忽略了什么?

编辑:我正在使用g++版本9.3.0
Edit2:mediocrevegetable1的答案被选中是因为它是当时唯一可用的g++。但是，将来的读者也可以尝试一下chris的答案，以获得更好的兼容性，或者希望编译器能够提供更有效的实现。

Answer 1

c++ 20新增std::bit_width(实例):

#include <bit>
#include <iostream>
int main() {
std::cout 
<< std::bit_width(10u) << ' ' // 4
<< std::bit_width(7u) << ' ' // 3
<< std::bit_width(127u); // 7
}

对于Clang主干，例如-O3 -march=skylake，一个函数只调用bit_width就会产生以下程序集:

count(unsigned int):
lzcnt   ecx, edi
mov     eax, 32
sub     eax, ecx
ret

在这个新的<bit>头文件中也有许多类似的函数。你可以在这里看到。

Answer 2

您可以使用GCC内置函数__builtin_clz，该函数给出前导零:

#include <climits>
constexpr unsigned bit_space(unsigned n)
{
return (sizeof n * CHAR_BIT) - __builtin_clz(n);
}

Answer 3

可以使用asm

int index;
int value = 0b100010000000;
asm("bsr %1, %0":"=a"(index):"a"(value)); // now index equals 11

此方法返回最后一个设置位
的基于零的索引，这意味着如果没有设置位，它也将返回零
为了解决这个问题，可以先检查value是否为零
如果value为零，这意味着没有设置位
如果value不为零，这意味着index + 1是value使用的位数

Answer 4

有一个标准库函数。不需要自己写任何东西。https://en.cppreference.com/w/cpp/utility/bitset/count

#include <cassert>
#include <bitset>
int main()
{
std::bitset<32> value = 0b10010110;
auto count = value.count();
assert(count == 4);
}

经过下面的反馈，认为这是不正确的答案。我不知道是否有内置功能。但是这个编译时的constexpr会给出相同的结果。

#include <cassert>
static constexpr auto bits_needed(unsigned int value)
{
size_t n = 0;
for (; value > 0; value >>= 1, ++n);
return n;
}
int main()
{
assert(3 == bits_needed(7));
assert(4 == bits_needed(10));
assert(4 == bits_needed(9));
assert(16 == bits_needed(65000));
}