Tuesday, April 08, 2008

Bit Operations: round a number to a next multiple of a power of 2

This is easier than the last bit operation post. By the way, I would like to thank "LOLmachine" for the comments - improvements in the last bit operation post....

Anyway...Multiples of a power of 2 share the property that have at least a fixed number of digits zero in the least significant position. So, all multiples of 2 have the 1 first bits zeroed, all multiples of 4 have the 2 digits zeroed, etc.

In order to round a number (x) to the next multiple of "a", where "a" is a power of 2 all you need to do is to compute this:

round(x) = (x + (a-1)) & ~(a-1)

SO, if a is 8, the above formula looks like this:

round(x) = (x + 7) & ~7;

round(14) = (14 + 7) & (~7) = 16
round(16) = (16 + 7) & (~7) = 16
round(17) = (17 + 7) & (~7) = 24