Макрос для вычисления количества битов, необходимых для хранения числа n

Question

Допустим, мне нужно написать макрос C , который возвращает количество бит (1..32), необходимое для хранения 32-разрядного целого числа без знака.(Результат равен потолку (log2 (n)).

Мне он нужен как вычисляемый во время компиляции макрос, а не функция.

Я мог бы сделать

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

этоработает, но довольно долго. (Скорость здесь не имеет значения, вычисления выполняются во время компиляции).

Есть ли более короткий способ написать этот макрос? Кратчайший?

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

это хорошо?

Answer 2

Это не решение для C, но для C ++ (c ++ 11 или выше), вместо этого используется constexpr вместо MACRO.

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

Компилятор выполнит оценку во время компиляции и заменит вызов (например, log2 (16)) на буквальное значение (например, 5), при условии, что используется оптимизация -O2 или -O3 (из-за рекурсивного вызова).

Answer 3

Это можно сделать с помощью макроса, который выполняет немного меньше тестов, чем вы предлагаете в своем вопросе, используя более умное битовое тестирование для нескольких битов одновременно. Макрос P99_HIGH2 из P99 реализует такую ​​хитрость, как уже упоминалось в одном из комментариев. Если это используется для выражений времени компиляции, нет никакой опасности в оценке аргумента несколько раз, так как в любом случае это должно быть целочисленное константное выражение.

Answer 4

Если вы не возражаете против дополнительных операторов (while 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

Answer 5

Я не думаю, что препроцессор C способен это сделать.Если я не ошибаюсь, вы не можете поместить препроцессор if в макрос.Все, что вы можете сделать, это кусок кода с отверстиями, с параметрами макроса, заполняющего отверстия.