how to prove 'roundup' arithmetic

[joefoxreal]

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?

Thanks
Eirc

 

[Andrew Poelstra]

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?

"Abviously". That's a new one. A and O are at opposite ends of the
keyboard. Since you appear not to speak English as a first language,
remember that the word is "obviously".

This question is beyond the realm of clc. You should check on one
of the algorithm-related groups. Try comp.programmer.

 

[Richard Heathfield]

(e-mail address removed) 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.

 

[Graham J Lee]

"Abviously". That's a new one. A and O are at opposite ends of the
keyboard.

http://www.klippert.com/tcc/blog/pics/Dvorak.jpg

;-)