宏计算存储数字n所需的位数

Question

假设我需要编写一个C宏，返回存储32位无符号整数所需的位数（1..32）。 （结果等于上取整（log2（n））。

我需要将其作为编译时计算的宏，而不是函数实现。

我可以这样做：

 #define NBITS(n) ((n)&(1<<31)?32:(n)&(1<<30)?31:...

它能正常工作，但是有点长。（这里速度不重要，计算在编译时完成）。

有没有更短的方法来编写这个宏？最短的方法？

- Andrei

---

它必须用C编写吗？在C++0x中，我可以提供可变参数模板来完成这个…遗憾的是，C预处理器似乎不允许递归宏。 - Kerrek SB

简单的C++将使用递归模板。 - Karoly Horvath

你需要精确的位数吗？更实际的解决方案是知道你需要多少字节进行存储，这样你就可以使用0xFF000000、0xFF0000、0xFF00和0xFF进行AND运算。 - Vinicius Kamakura

@Kerrek SB：这是一个关于C语言的问题。 - Andrei

请查看bithacks超链接，了解有关位操作的信息。 - Fredrik Pihl

Answer 1

#define NBITS2(n) ((n&2)?1:0)
#define NBITS4(n) ((n&(0xC))?(2+NBITS2(n>>2)):(NBITS2(n)))
#define NBITS8(n) ((n&0xF0)?(4+NBITS4(n>>4)):(NBITS4(n)))
#define NBITS16(n) ((n&0xFF00)?(8+NBITS8(n>>8)):(NBITS8(n)))
#define NBITS32(n) ((n&0xFFFF0000)?(16+NBITS16(n>>16)):(NBITS16(n)))
#define NBITS(n) (n==0?0:NBITS32(n)+1)
#include <iostream>
using namespace std;

int main(){
    cout << NBITS(0) << endl;
    cout << NBITS(1) << endl;
    cout << NBITS(2) << endl;
    cout << NBITS(3) << endl;
    cout << NBITS(4) << endl;
    cout << NBITS(1023) << endl;
    cout << NBITS(1024) << endl;
}

这好吗？

- Adi

---

我认为你仍然需要1位来存储值0。 - Dana Leonard

我认为这应该是C语言，而不是C++。 - nmichaels

对于任何感兴趣的人，我已经为一个相关问题撰写了有关如何实现这个功能的解释：http://stackoverflow.com/questions/29283276/calling-a-function-from-a-macro/29291166。 - Ulfalizer

Answer 2

这可以通过使用比您在问题中提出的更聪明的位测试，使用一种执行少量测试的宏来完成。宏P99_HIGH2来自P99，实现了一种技巧，正如其中一个评论中已经提到的那样。如果将其用于编译时表达式，则多次评估参数没有危险，因为这必须是整数常量表达式。

- Jens Gustedt

Answer 3

如果您不介意添加额外的语句（while循环），以下代码可以在c99中运行：

#define NBITS_32(n,out_len) 0; while (n && !(0x80000000 >> out_len & n)) out_len++; out_len = n ? abs(out_len - 32) : n


uint8_t len1 = NBITS_32(0x0F000000, len1);
uint8_t len2 = NBITS_32(0x00008000, len2);
uint8_t len3 = NBITS_32(0xFFFFFFFF, len3);
uint8_t len4 = NBITS_32(0x00000001, len4);

printf("%u\n%u\n%u\n%u\n", len1, len2, len3, len4);

输出：

28
16
32
1

- Joe

---

-1：该宏不符合问题所要求的编译时常量展开。 - Frerich Raabe

它会生效，但是宏会扩展为两个语句。因此，如果宏扩展为编译时常量（如Adi的解决方案），则无法执行类似于'int arr[NBITS_32(...)]'这样的操作。 - Frerich Raabe

我想了两秒钟后意识到这一点：）。谢谢，我会将其保留为参考，除非它被大量的反对票所否定。Adi的答案似乎不错。 - Joe

Answer 4

这不是 C 语言的解决方案，而是针对 C++ （c++11 或更高版本）的解决方案，使用 constexpr 而不是 MACRO 是一个好办法。

constexpr int log2(unsigned int word) {     
    return word ? (1 + log2(word>>1)) : 0; 
};

编译器将在编译时进行评估，并使用文字值（例如5）替换调用（例如log2（16）），前提是使用了-O2或-O3优化（因为递归调用）。

- codechimp

Answer 5

我认为C预处理器无法做到这一点。如果我没有弄错的话，您不能在宏中放置预处理器if语句。您所能做的就是编写一个带有空缺的代码片段，使用宏的参数填充这些空缺。

- Clement Bellot

---

我提供了一个工作示例。它可以正常运行并且是静态编译的，但是代码很长。当我已经提供了一个工作示例时，你怎么能认为这是不可能的呢？或者你想让我提供完整的rhs吗？ - Andrei

抱歉，我以为你在谈论C++，我假设你想直接获得宏输出给你位数，为此我期望会有一个函数。另外，根据你的编译器优化，你可以尝试将其放入for循环中。 - Clement Bellot

这个宏确实可以给你位数的数量。顺便说一下，你可以在宏中使用 if 语句，但是你使用它的地方必须是一个语句，不能在表达式中使用。 - Karoly Horvath

你可以使用if语句，但不能使用#if。我在考虑优化存储类型，在优化过程之前需要获取信息。 - Clement Bellot