Align Number to Multiple

Aligning an integer, say n, to its closest muplitple of m is easy by using round(n / m) * m (arithmetic division) or (n + m - 1) / m * m (Euclidean division).

However, if m is a power of 2, i.e., m = 2^k, using bitwise operations can help a lot.

aligned_n = (n + (m - 1)) & ~(m - 1);

Explanation

This should be viewed from a binary perspective.

For example, say m = 8 and demonstrate it in 8-bit binary.

variable	number	binary
m	8	0000 1000
m - 1	7	0000 0111
~(m - 1)	/	1111 1000

By applying bitwise AND &, the lower bits of the number are cleaned to 0, leaving the result becoming the multiple of m.

If not adding m - 1, the result will be the closest multiple smaller than n, and adding it makes sure the result is bigger than the original number n.

Remark

(n + m/2) & ~(m-1) is an alternative, and adding a number ranging from m/2 to m - 1 is technically all fine.

This method could be helpful in memory page alignment, where standard library is not available and we can sacrifice a little bit of readability of the code. For example, PGROUNDUP and PGROUNDDOWN in xv6, which stand for page round up and page round down, are implemented in this way.

References

1. c - What is bit masking? - Stack Overflow
2. Bit Twiddling Hacks - Round up to the next highest power of 2
3. c - What do PGROUNDUP and PGROUNDDOWN in xv6 mean? - Stack Overflow
4. mit-pdos/xv6-riscv: Xv6 for RISC-V
5. Bitwise operation - Wikipedia