C macro to get the smallest power of two greater than a given number

Question

I need a C macro to get the smallest of power two greater than a given number.

For example, FIRSTFREEBIT(0x16) (binary 1_0110) must be equal to 0x20.

I am going to use it as:

#include <someheader.h> // defines SOME_X and SOME_Y
enum {
     x = SOME_X,
     y = SOME_Y,
     z = FIRSTFREEBIT(x|y),
     t = z << 1,
};

A similar, but slightly different SO question: Algorithm for finding the smallest power of two that's greater or equal to a given value

[this](http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2) — The Paramagnetic Croissant, May 30 '14 at 12:31
http://stackoverflow.com/questions/671815/what-is-the-fastest-most-efficient-way-to-find-the-highest-set-bit-msb-in-an-i or http://www.hackersdelight.org/hdcodetxt/nlz.c.txt - you just have to encode it as a macro. — cup, May 30 '14 at 12:40
Should (binary 1_0000) return 0x10 or 0x20? Base on "smallest of power two greater than", sounds like you want 0x20. — chux - Reinstate Monica, May 30 '14 at 13:49
@chux yes, I want FIRSTFREEBIT(0x10) to be 0x20, because I want a bit that has not yet been used. — 18446744073709551615, Jun 02 '14 at 06:40
@rici: if `SOME_X` is 2 and `SOME_Y` is 4, `x` must be 2, `y` must be 4, `z` must be 8, and `t` must be 16. That is, `z` must be a value with the first-yet-unused bit set, rather than the number of that bit. — 18446744073709551615, Jun 02 '14 at 06:44

score 2 · Answer 1 · answered May 30 '14 at 12:29

2

Here's my code, you are welcome to invent something better:

#define __OR_RSHIFT__(n,x) ((x)|(x)>>n)
#define FIRST_UNUSED_BIT(x) (1+__OR_RSHIFT__(16,__OR_RSHIFT__(8,__OR_RSHIFT__(4,__OR_RSHIFT__(2,__OR_RSHIFT__(1,x))))))

answered May 30 '14 at 12:29

18446744073709551615

16,368
4
94
127

5

Identifiers starting with two underscores are reserved by language standard for internal needs. You should not use them. – Vovanium May 30 '14 at 12:40

Blagovest Buyukliev · Answer 2 · 2014-05-30T13:36:48.393

2

Look at the __builtin_clz GCC intrinsic. It will give you the number of leading zero bits, which could be used to determine the position of the first bit set. Then do a left bit shift of 1, times the position.

edited May 30 '14 at 13:36

answered May 30 '14 at 12:36

Blagovest Buyukliev

42,498
14
94
130

The best thing is that it works at compile-time! But: it should be `1+__builtin_ffs(x)` – 18446744073709551615 May 30 '14 at 13:12
oops! `__builtin_ffs(0x5)=0x1`, that is, it must be a different function! – 18446744073709551615 May 30 '14 at 13:31
Ah yes, the `ffs` function returns the position of the first least significant bit that is set. `__builtin_clz` returns the number of leading zero bits and could do your job. – Blagovest Buyukliev May 30 '14 at 13:34
It is `1<<0x20-__builtin_clz(x)` – 18446744073709551615 May 30 '14 at 13:47
Also make sure to handle the case when `x` is zero, because `clz` would return an undefined result in that case. – Blagovest Buyukliev May 30 '14 at 13:50

C macro to get the smallest power of two greater than a given number

2 Answers2

Linked