Align Number to Multiple

Last updated on August 13, 2024 am

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 = 2k, using bitwise operations can help a lot.

1
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

Align Number to Multiple
https://lingkang.dev/2023/03/12/align/
Author
Lingkang
Posted on
March 12, 2023
Licensed under