有没有内置函数可以快速统计一个int占用了多少位？

Question

我正在计算 int 占用了多少位，例如count(10)=4、count(7)=3、count(127)=7等
我已经尝试过暴力破解（<<ing a 1 直到它严格大于数字）并使用 floor(log2(v))+1，但两者都太慢了我的需要。
我知道有一个 __builtin_popcnt 函数可以快速计算 int 中有多少 1，但是我找不到适合我的应用程序的内置函数，有没有这样的功能还是我忽略了什么？

编辑：我正在使用 g++ 版本 9.3.0
选择Edit2:mediocrevegetable1的答案是因为它是time.However中唯一可以与g++一起使用的答案，未来的读者也可以尝试chris的答案以获得更好的兼容性或者希望编译器能够给出更有效的实施。

Answer 1

添加了 C++20 std::bit_width (live example):

#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> header 中也有许多类似的功能。你可以 see them all here.

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

此方法return最后设置位的从零开始的索引
这意味着如果没有设置任何位
，它也将return归零为了解决这个问题，可以先检查 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));
}

有没有内置函数可以快速统计一个int占用了多少位？

Is there a built-in function that quickly counts how many bits an int takes up?

c++

built-in