CODEWITHSUNDEEP
cbit-manipulationc-preprocessor
18446744073709551615
18446744073709551615

Reputation: 16872

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

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

Upvotes: 1

Views: 780

Answers (3)

fearless_fool
fearless_fool

Reputation: 35239

Here's a compile-time solution that takes advantage of the GCC _builtin_clz function:

// Lowest Power of 2 greater than or equal to x.  Assumes integer x greater
// than 0
#define LPO2(x) (1<<((sizeof(x)*8)-__builtin_clz((x)-1)))

int main() {
    printf("%d\n", LPO2(7)); // => 8
    printf("%d\n", LPO2(8)); // => 8
    printf("%d\n", LPO2(9)); // => 16
}

Upvotes: 1

Blagovest Buyukliev
Blagovest Buyukliev

Reputation: 43558

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.

Upvotes: 2

18446744073709551615
18446744073709551615

Reputation: 16872

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))))))

Upvotes: 2

Related Questions