表示给定“int”的最小位数

Question

在 C++ 中，找出存储给定 int 需要多少位的最快方法是什么？

我可以尝试将数字除以 2 多次，但除法很慢。有什么快捷的方法吗？

编辑：

非常感谢各位的回答。当我说int我的帖子时，我的意思是任何 4 字节的整数。例如，如果我存储 30665，我希望得到 15 位的结果。

Answer 1

在 C++20 中，您只需要使用std::bit_width()或其等效项

return std::numeric_limits<decltype(x)>::digits - std::countl_zero(x);

如果您使用较旧的 C++ 标准，则使用boost::multiprecision::msb()它自动映射到当前编译器的适当内在函数，例如__builtin_clz()或_BitScanReverse()...或者使用#ifdef并根据当前编译器手动切换实现

return boost::multiprecision::msb(x);               // Cross-platform

int index;
return _BitScanReverse(&index, n)) ? index + 1 : 1; // MSVC, ICC
return 32 - _lzcnt_u32(n);                          // ICC
return 32 - __builtin_clz(X));                      // GCC, Clang

Answer 2

您可以将值逐渐分成两半，以更快地缩小范围。

int bits_needed(uint32_t value)
{
    int bits = 0;
    if (value >= 0x10000)
    {
        bits += 16;
        value >>= 16;
    }
    if (value >= 0x100)
    {
        bits += 8;
        value >>= 8;
    }
    if (value >= 0x10)
    {
        bits += 4;
        value >>= 4;
    }
    if (value >= 0x4)
    {
        bits += 2;
        value >>= 2;
    }
    if (value >= 0x2)
    {
        bits += 1;
        value >>= 1;
    }
    return bits + value;
}

查看实际效果：http://ideone.com/1iH7hG

编辑：抱歉，原始版本需要一个附加术语。现在已经修好了。

编辑2：按照评论中的建议采用循环形式。

int bits_needed(uint32_t value)
{
    int bits = 0;
    for (int bit_test = 16; bit_test > 0; bit_test >>= 1)
    {
        if (value >> bit_test != 0)
        {
            bits += bit_test;
            value >>= bit_test;
        }
    }
    return bits + value;
}

该算法返回0的输入0，这意味着您根本不需要任何位来编码 的值0。如果您希望它返回1，只需将返回值更改为bits + 1.