如何在C++中获取整数的位数？

Question

这个问题和统计32位整数中置位的数量不是重复的。请参见下面Daniel S.的评论。

--

假设有一个变量int x;，它的大小为4个字节，即32位。

然后我给这个变量赋值x = 4567（二进制10001 11010111），在内存中它看起来像这样:

00000000 00000000 00010001 11010111

是否有一种方法可以获取有用的位数长度？在我的示例中，位长度为13（我用粗体标记了它们）。 如果使用 sizeof(x) 它会返回4，即整个int的大小。如何获得表示整数所需的最小位数，而不包含前导的0？

- qazerty23

---

这是一个常见的问题。你试过谷歌搜索吗？ - Maxim Egorushkin

如何计算32位整数中设置位的数量 - ha9u63a7

对数（以2为底）？ - CompuChip

你想要尝试计算前导零吗？ - Dmitry Grigoryev

这个问题并不是关于如何计算32位整数中集合位的数量的重复。用户jww之前已经提到过。这里的问题是要求比特长度，即最高有效位索引+1，而链接的问题是要求popcount，即汉明重量。这些是不同的事情。链接是错误的且令人困惑的。 - Daniel S.

Answer 1

unsigned bits, var = (x < 0) ? -x : x;
for(bits = 0; var != 0; ++bits) var >>= 1;

这应该能满足你的需求。

- grimble

---

太好了！简短、简单且完全可移植！只有一个小问题，如果是负数，则由于符号位会出现问题。 - Christophe

可以通过编写 var = (x < 0) ? -x : x 来解决。 - CompuChip

我期望“-1”具有长度32（或sizeof(int)*CHAR_BIT)），而不是1。 - MSalters

如果将-1转换为unsigned，结果将为32。（假设使用二进制补码表示有符号数） - grimble

请解释一下？（如果原始解决方案没有三元运算符，那么这很重要） - grimble

有趣的边角情况是 var = 0，此时 bits = 0。从技术上讲这是正确的，尽管很少有人会将零写成 '' 而不是 '0'。 - knia

Answer 2

警告：接下来涉及数学。如果你不喜欢，可以跳过直接看总结。

实际上你要找的是二进制中最高位的1。我们来看一下二进制数字10001 11010111的真实含义：

x = 1 * 2^(12) + 0 * 2^(11) + 0 * 2^(10) + ... + 1 * 2^1 + 1 * 2^0

其中*表示乘法，^表示指数。

你可以将其写为

2^12 * (1 + a)

如果精确地说，0 < a < 1（即 a = 0/2 + 0/2^2 + ... + 1/2^11 + 1/2^12）。

如果你取这个数字的对数（以2为底），用log2表示，你会得到：

log2(2^12 * (1 + a)) = log2(2^12) + log2(1 + a) = 12 + b.

由于 a < 1，因此我们可以得出结论： 1 + a < 2，因此 b < 1。

换句话说，如果你对 log2(x) 向下取整，你将得到最重要的2的幂（在这种情况下是12）。由于幂从0开始计数，所以所需的位数比这个幂多一个，即13。因此：

简而言之：

表示数字 x 所需的最小位数为：

numberOfBits = floor(log2(x)) + 1

- CompuChip

---

数字上是正确的，但效率非常低。 - MSalters

@MSalters 为什么效率低？ - Hritik

log2 是一个浮点运算，它计算小数点后的许多位。Floor() 然后将它们舍弃。 - MSalters

我们想要的是一种只使用整数位运算来实现这个功能的方法。 - BD107

Answer 3

自C++20以来，便携式的现代方式应该使用std::countl_zero，例如

#include <bit>

int bit_length(unsigned x)
{
    return (8*sizeof x) - std::countl_zero(x);
}

无论是gcc还是clang，在x86上为此代码发出单个bsr指令（带有零分支），因此它应该非常优化。

请注意，std::countl_zero只接受无符号参数，所以决定如何处理原始的int参数留给读者作为练习。

- Useless

Answer 4

许多处理器都提供了一种直接计算前导零位数的指令（例如，x86有lzcnt/bsr，ARM有clz）。通常，C++编译器提供了一个内部函数来访问其中的一个指令。然后可以使用前导零位数来计算位数。

在GCC中，内置函数被称为__builtin_clz。它计算32位整数的前导零的数量。
然而，有一个关于__builtin_clz的警告。当输入为0时，结果是未定义的。因此，我们需要特别处理这种情况。下面的函数使用(x == 0) ? 32 : ...来处理这个特殊情况，当x为0时，结果为32：

uint32_t count_of_leading_0_bits(const uint32_t &x) {
    return (x == 0) ? 32 : __builtin_clz(x);
}

然后可以从前导零的数量计算比特长度：

uint32_t bitlen(const uint32_t &x) {
    return 32 - count_of_leading_0_bits(x);
}

请注意，其他 C++ 编译器有不同的内置函数用于计算前导零位的数量，但您可以通过在互联网上搜索快速找到它们。这里提供了 如何使用 MSVC 内置函数获取与此 GCC 代码等效的代码？ 的链接，以获取相应的 MSVC 内置函数。

- Daniel S.

---

也许可以用更快的方法替换掉处理特殊情况的 x==0 解决方案。如果能提供编译器探查器的结果就更好了。欢迎在我的答案中添加内容。 - Daniel S.

从C++20开始，有一个countl_zero函数，直接转换为bsr(加上处理零)，因此不需要GCC内置函数。 - Useless

Answer 5

您正在寻找数字中设置的最高位。让我们先不考虑负数。我们如何找到它？好的，让我们看看在整个数字变为零之前需要设置多少个零位。

00000000 00000000 00010001 11010111
00000000 00000000 00010001 11010110
                                  ^
00000000 00000000 00010001 11010100
                                 ^
00000000 00000000 00010001 11010000
                                ^
00000000 00000000 00010001 11010000
                               ^
00000000 00000000 00010001 11000000
                              ^
00000000 00000000 00010001 11000000
                             ^
00000000 00000000 00010001 10000000
                            ^
...
                       ^
00000000 00000000 00010000 00000000
                      ^
00000000 00000000 00000000 00000000
                     ^

完成！经过13位的操作，我们已经全部清除了它们。那么我们该如何做呢？表达式1<<pos是将1位向左移动pos个位置。因此，我们可以检查if (x & (1<<pos))，如果为真，则删除它：x -= (1<<pos)。我们也可以在一个操作中完成这个步骤：x &= ~(1<<pos)。~得到的是补码：所有的位都是1，而pos位设置为0，而不是相反。x &= y将y的零位复制到x中。

现在我们该如何处理有符号数呢？最简单的方法是忽略它：unsigned xu = x;

- MSalters