0

I want to create a function that returns the next multiple of 2^p.

Here's an attempt, but not sure if it works...:

#define P 20
#define ALIGN_FORWARD(x, alignment) ((((int)x) + ((alignment)-1)) & (~((alignment)-1)))

int round_up(int x) 
{
  return ALIGN_FORWARD(x, P);
}
Lee Taylor
  • 7,761
  • 16
  • 33
  • 49
SuperString
  • 21,593
  • 37
  • 91
  • 122
  • Why don't you run it and test it and see whether it works? – indiv Sep 17 '14 at 01:04
  • 2
    `(1<

     – Sergey Kalinichenko Sep 17 '14 at 01:05
  • code it as straight code, test it and then (only just then) covert it to a macro – lboshuizen Sep 17 '14 at 01:05
  • @dasblinkenlight No, this is not an exponentiation function but a rounding function. However, it can't be done without count-leading-zeroes (or some repetition), and you do need such an exponentiation function to get from leading-zeroes to the result. – Potatoswatter Sep 17 '14 at 01:13
  • possible duplicate of [Write a C function that round up a number to next power of 2](http://stackoverflow.com/questions/14813008/write-a-c-function-that-round-up-a-number-to-next-power-of-2) – phuclv Mar 11 '15 at 05:50

1 Answers1

2

This snippet first fills up all bits below the highest set bit. After v |= v >> 1 the first two bits can be copied and so on. Finally the value is incremented by one.

uint32_t v = ...;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v += 1;

The unsigned part of uint32_t is important, because otherwise the result would be always 0, because the sign bit gets extended by the shift operation. If the value is a uint64_t, then you have to add a further shift, if it is a uint16_t, then you have to remove a shift.

For an input of 8 the result would be 16. You need to test if the input is a power of two if you don't like that. Knowing that the binary representation of a power of two is one character shorter when you decrement it (8=0b1000, 7=0b111), you can use this guard:

if ((v & (v - 1)) > 0) {
    …
}

(Reproduced from memory. Original from https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2, which contains many more interesting tricks.)

Kijewski
  • 25,517
  • 12
  • 101
  • 143