如何获取整数的位数

Question

当然，我知道一种方法来实现这个：

当然，我知道一种方法来实现这个：

/// <summary>Gets the number of bits needed to represent the number.</summary>
public static int Size(int bits)
{
    var size = 0;
    while(bits != 0)
    {
        bits >>= 1;
        size++;
    }
    return size;
}

因此，Size（15）返回4，Size（16）返回5。

但我猜（希望）有一种更快的方法。 但是我想不出（或谷歌）一个漂亮，平滑（和快速）的算法。

- Corniel Nobel

---

通过将 int 分成 4 或 8 位的块，可以显着加快最坏情况（大值）的速度，但会降低平均情况（小值）的速度。如果最高有效位块不为 0，则可以仅从该块获取大小并忽略其他块。 - itsme86

@CaptainObvlious OP 希望得到代码中显示的有效位数。 - Weather Vane

你是在寻找类型本身的大小还是实际使用了多少位？ - EJoshuaS - Stand with Ukraine

C、C++ 和 C# 是有不同解决方案的不同编程语言。 - Baum mit Augen

@CaptainObvlious OP 想知道特定值需要多少位，而不是 int 类型的大小。 - itsme86

Answer 1

可能不是最快的，但很可能是最短的方法：

public static int Size(int bits) {
  return (int) (Math.Log(bits, 2)) + 1;
}

通过将while转换为for，可以缩短您的代码：

public static int Size(int bits) {
  int size = 0;

  for (; bits != 0; bits >>= 1)
    size++;

  return size;
}

- Dmitry Bychenko

---

我正在寻找一个快速的解决方案，而不是一个更短的。 ;) - Corniel Nobel

Answer 2

虽然这段话有点长，但是它很快（在整个int范围内平均）

    internal static readonly byte[] msbPos256 = new byte[] {
        255, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
        5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
        6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
        6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
        7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
        7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
        7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
        7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7};

    public static int SignificantBits(this int value) {
        return HighBitPosition((uint)value) + 1;
    }

    public static int HighBitPosition(this ushort value) {
        byte hiByte = (byte)(value >> 8);
        if (hiByte != 0) return 8 + msbPos256[hiByte];
        return (sbyte)msbPos256[(byte)value];
    }
    public static int HighBitPosition(this uint value) {
        byte hiByte = (byte)(value >> 24);
        if (hiByte != 0) return 24 + msbPos256[hiByte];
        hiByte = (byte)(value >> 16);
        return (hiByte != 0) ? 16 + msbPos256[hiByte] : HighBitPosition((ushort)value);
    }

调用SignificantBits方法。需要注意的是，99.6%的int值可能会在32位中的前8个最高有效位（即32位中的前8位）之一具有最高有效位。这只需要进行右移操作、两个加法操作（其中一个可能会被编译器优化为递增操作）、一个!=0测试和一个数组引用。因此，对于大多数可能的值，速度非常快。要覆盖第二个8个最高有效位，需要进行额外的右移、!=0测试，这可以覆盖99.998%的可能int值。转换成其他类型不会带来太大开销。

您可以通过将msbPos256值增加1来省略+1操作。当我写这段代码时，我更感兴趣的是HighBitPosition函数而不是SignficantBits函数，这就是我为什么以我现在的方式添加了SignificantBits的原因。

如果我没记错，在测试各种技巧时，这比我最初用于此的DeBruijn技术更快。

- hatchet - done with SOverflow

Answer 3

首先，我真的怀疑这是您正在寻找的瓶颈。（过早优化是万恶之源）

话虽如此，在这篇斯坦福位操作技巧文章中有一些有趣的方法： 位操作技巧

包括您采取的朴素方法（展开确实会有所帮助）：

unsigned int v; // 32-bit word to find the log base 2 of
unsigned int r = 0; // r will be lg(v)

while (v >>= 1) // unroll for more speed...
{
  r++;
}

或者这个使用 O(log n)：

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

还有更多的内容。

但是请注意，在C/C++中更快的可能在C#中变得更慢。你的代码仅纯粹使用了一些本地变量，这实际上不错，如果你想确保另一种方法更好，请先进行基准测试。

- Work of Artiz

---

这不是瓶颈，我只是想知道它是否存在。对于我使用的算法，我只调用它一次。;) - Corniel Nobel

Answer 4

如果你正在寻找最高位设置的方法，请参见查找第一个设置。一种可能的实现（不处理零输入）如下所示：

table[0..31] = {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}
function lg_debruijn (x)
    for each y in {1, 2, 4, 8, 16}: x ← x | (x >> y)
        return table[(x * 0x07C4ACDD) >> 27]

如果您想计算1位的数量（有时称为种群计数），请查看汉明重量。一种可能的解决方案是：

int popcount_4(uint64_t x) {
    int count;
    for (count=0; x; count++)
        x &= x-1;
    return count;
}

有时，这种功能甚至具备语言支持：

某些C编译器提供了内部函数，提供位计数功能。例如，GCC（自2004年4月3.4版本以来）包括一个内置函数__builtin_popcount，如果可用，则使用处理器指令，否则使用高效的库实现。LLVM-GCC自2005年6月1.5版本以来就包含了这个函数。

- AlexD

---

这不是OP想要的。他们明确表示Size(16)应该是5。这个函数将返回1（即人口计数，正如你所说）。 - itsme86

Answer 5

我只是在这里提供另一种选项，虽然其他答案似乎已经回答了你的问题。

这种方法使用位移来计算前导零的数量，然后从32中减去该数量以找出剩余的空间。

    static int NecessaryBits(int num)
    {
        const int mask = Int32.MinValue;
        int leadingZeros = 0;
        for(; leadingZeros < 32; leadingZeros++)
        {
            if( (num & mask) != 0)
                break;
            num <<= 1;
        }
        return 32 - leadingZeros;
    }

- Cody

---

这跟我的算法没什么不同，是吧？;) - Corniel Nobel

@CornielNobel，这个想法和你的基本相同，但是你是从右边开始搜索，而我是从左边开始搜索。你必须扫描整个序列才能找到最后一个1，而我只要找到第一个1就可以退出了。虽然它们都是“O(n)”，但在实践中，我的方法平均会更快一些。 - Cody

好观点，我没想到。虽然我认为在实践中，你会搜索更小的数字。所以我认为我的方法会更快。 - Corniel Nobel