表示给定int的最小位数 [英] Minimum number of bits to represent a given `int`

问题描述

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

In C++, what's the fastest way to find out how many bits are needed to store a given int?

我可以尝试将数字除以2，但是分裂非常缓慢。有什么快速的方法吗？

I can try dividing the number with 2 many times but divisions are pretty slow. Is there any fast way?

编辑：

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

Thanks a lot for the answers guys. When I say an int my post, I mean any 4-byte int. For example, if I store 30665, I want to get as a result 15 bits.

推荐答案

您可以通过以下方式逐步破坏该值：

You can break the value progressively by halves to narrow it down faster.

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

编辑：抱歉，原始版本需要再增加一个条款。现在已修复。

Sorry, the original version needed one additional term. It's fixed now.

编辑2：按照注释中的建议以循环形式显示。

Edit 2: In loop form as suggested in the comments.

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 。

This algorithm returns 0 for an input of 0, meaning you don't need any bits at all to encode a value of 0. If you'd rather it return 1 instead, just change the return value to bits + 1.

这篇关于表示给定int的最小位数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！