jo********@gmail.com said:
Hi,
#define roundup(x,n) (((x)+((n)-1))&(~((n)-1)))
This macro is to set x align with n. But how to prove the arithmetic?
Abviously, I can use the value to check it. What's the else?
Given that n is a power of 2, ~(n - 1) will zero out the low log2(n) bits.
Take n = 16, for example, and feed it 0 for x. You'll end up with 15 & ~15,
which is clearly 0. That's because 15 is 0000...00001111, and ~...00001111
is ...11110000, so the AND-mask wipes out those bottom few bits.
Now take n = 16 and feed it 1 for x. This time, you'll end up with 16 & ~15.
This is:
......00000010000
......11111110000 AND
----------------
......00000010000
which is 16. The leftmost bits of the ~15 expression preserve the leftward
bits in (x + n - 1), and the rightmost bits blow away the low bits. The + n
- 1 part is to ensure that x is never decreased as a result of the
rounding. Adding n would be too much, because it would move a value that is
already aligned; and adding n - 2 would be insufficient, because it would
fail to lift, say, a 1 to the next boundary up. But n - 1 is just right.
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)