How to calculate the next highest power of 2
I know that I'm hardly the first person to write a blog post on this but I thought I might anyway, so here goes.How?
The are a few ways to find the highest power of two. I am going to show you 2 ways using code I found on the interwebs (here (Acius' Snippets) and here (Luigi Rizzo's FreeBSD post)).Via a bad function
This method only works for 8-bit numbers and is a bit crap all up.UINT16 next_power_of_2(UINT8 x) {
UINT16 npo2 = x - 1;
for (UINT8 i = 0; i < 16; i++) {
npo2 = npo2 | (npo2 >> i);
}
return npo2 + 1;
}
Now let's forget that one.Via a better function
This method defines a function that finds the next highest power of two. Apparently it is the "Hacker's Delight" algorithm.Here it is written in C.
unsigned clp2(unsigned x) {
x = x - 1;
x = x | (x >> 1);
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >>16);
return x + 1;
}
(From here (Acius' Snippets))
Via an inline hash-define
Sometimes in C you need (or would like) to know the next highest power of two without having to call a function (e.g. at compile time). The following set of macros perform the same logic as the function above, but do it in a single, compile-time statement.#define b2(x) ( (x) | ( (x) >> 1) ) #define b4(x) ( b2(x) | ( b2(x) >> 2) ) #define b8(x) ( b4(x) | ( b4(x) >> 4) ) #define b16(x) ( b8(x) | ( b8(x) >> 8) ) #define b32(x) (b16(x) | (b16(x) >>16) ) #define next_power_of_2(x) (b32(x-1) + 1)
(From here (Luigi Rizzo's FreeBSD post))
How does it work?
It is a little tricky at first glance to figure out what this algorithm is doing. The three main things it does are:- It subtracts 1 from the input to ensure that if the input is a power of 2 (i.e. 4), it doesn't calculate the "next power" to be too large (i.e. in the case of 4, it would return 8 when 4 is actually sufficient).
- It uses a binary divide-and-conquer to cascade the most-significant-bit of the input into all of the bits of lesser significance.
- It adds 1 to get the resulting number to roll-over into the next highest power of 2.
The following is a little pictorial representation of how it works for the number 4098.
Why might it be useful?
Calculating the next highest power of 2 can be extremely handy in programming, especially in C/EmbeddedSystems programming, as powers of 2 are the increments of storage you can allocate in your program.For example, in a piece of embedded C code I was writing, I created a struct for holding some generic records:
struct my_record
{
u8_t flags;
u8_t record[MY_RECORD_LENGTH];
u8_t padding[PADDING_SIZE];
}__attribute__((__packed__));
I was allowing consumers of this package to define their own "MY_RECORD_LENGTH" but I wanted to determine the PADDING_SIZE to ensure that the length of "struct my_record" was a power of 2 (to remain aligned to power-of-2 byte boundaries). I used the C macro version of the "next power of 2" function along with the known lengths in my_record to create another compile-time value that would be just the right length, as so:
#define PADDING_SIZE (next_power_of_2(1 + MY_RECORD_LENGTH) - (1 + MY_RECORD_LENGTH))
