c - 如何确定一个数字的有用位数？

Question

我正在编写一个函数，它确定 16 位整数的有用位数。

int16_t
f(int16_t x)
{
    /* ... */
}

例如，数字“00000010 00100101”有 10 个有用位。我想我应该使用一些按位运算符，但我不知道如何。我正在寻找一些方法来做到这一点。

score 2 · Accepted Answer

如果您使用的是 gcc（或与 gcc 兼容的编译器，例如 ICC），那么您可以使用内置的内在函数，例如

#include <limits.h>

int f(int16_t x)
{
    return x != 0 ? sizeof(x) * CHAR_BIT - __builtin_clz(x) : 0;
}

这假设您只需要最后一个前导零位右侧的位数。

对于 MSVC，您可以_BitScanReverse进行一些调整。

否则，如果您需要它是可移植的，那么您可以实现自己的通用clz功能，请参见例如http://en.wikipedia.org/wiki/Find_first_set

score 2 · Accepted Answer

这些称为位扫描操作，在英特尔架构上有汇编指令（您可以直接从 C 调用），请参见此处。如果您使用的是 MS 编译器，请从这里开始。

score 0 · Accepted Answer

对数计算将某个数字表示为某个基数所需的位数：

让[x]be x，四舍五入到下一个整数。

然后是表示base[log_b(x)]所需的位数。xb

因此，如果您想知道xC 中某些有效位的数量，那么ceil(log2(x))会告诉您。

由于没有算法可以在恒定时间内告诉您二进制表示的前导零的数量，因此计算对数实际上可能比天真的迭代更快。

3 回答 3