如何获取整数的位大小

问题描述 投票：0回答：6

我当然知道一种方法：

/// <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。

但我想（希望）有一种更快的方法。但我想不出（或谷歌）一个好的、流畅的（快速的）算法。

c# bit
6个回答
3
投票

不是最快的，但可能是最短的：

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;
}
2
投票

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

话虽这么说，这篇标准的 Bit twiddling 文章中有一些有趣的方法： Bit Twiddling Hacks

包括你采取的天真的方法（展开确实有帮助）：

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# 中可能会变慢。你的代码纯粹使用了一些局部变量，这实际上还不错，如果你想确保另一种方法更好，请先对其进行基准测试）

2
投票

这并不短，但速度很快（对整个整数范围进行平均）

    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方法。需要注意的是，所有可能的 int 值中 99.6% 的最高有效位将位于前 8 个最高有效位（共 32 个）中。这只需要一个右移操作、两个加法操作（其中一个可能被编译器优化为增量）、一个 !=0 测试和一个数组引用。因此，对于大多数可能的值来说，速度非常快。要覆盖第二个 8 个最高有效位，需要进行额外的右移和 !=0 测试，这覆盖了 99.998% 的可能 int 值。演员的花费并不多。

您可以通过将 msbPos256 值增加 1 来减少 +1 操作。当我编写 HighBitPosition 函数时，我对 HighBitPosition 函数比 SignificantBits 函数更感兴趣，这就是为什么我这样做（我添加 SignificantBits 作为事后的想法）。

IIRC，当我测试各种技巧时，这比我最初使用的 DeBruijn 技术更快。

1
投票

如果您正在寻找最高位组，请参阅查找第一个组。一种可能的实现（不处理零输入）是：

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版本开始就包含了这个功能。

0
投票

我只是将其添加为此处其他答案的替代方案，尽管它们似乎已经解决了您的问题。

此方法使用位移位来计算前导零的数量，然后从 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;
    }
0
投票

当我最初发布这个问题时，我的解决方案的答案还不存在：

public static int Size(int bits)
    => 32 - System.Numerics.BitOperations.LeadingZeroCount(bits);

感谢微软添加

System.Numerics.BitOperations
。这公开了一些针对此类事物的说明。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.