Pages

Showing posts with label Binary. Show all posts
Showing posts with label Binary. Show all posts

Friday, February 19, 2016

The smallest 2n-multiple ≥ B

When dealing with quantities that are powers of 2, the binary (base-2) arithmetic as well as the typical binary representation of integer values can allow interesting alternatives to the usual base-10 arithmetic we are commonly used to.
 
The obvious prerequisites are binary arithmetic and logical operations.
The relevant formula is:
[ B +  ( A - 1 ) ] & [ ~( A - 1 ) ], where A = 2n for some n ≥ 0.
The above formula will compute the smallest multiple of A greater than or equal to B.
B is a positive integer value which, if large enough, could represent a pointer.
In this process it's imperative that A be a (positive) power of 2.

One particular application is adjusting C++ pointers to a certain alignment modulus.
In other words, this technique is very important to C++ memory management.
B would be the value of a pointer to be aligned to an A-multiple boundary.
If an alignment modulus is 4, then A = 4 and thus n = 2.
You know: alignment is vital.

Of course I shall prove the formula with a minimal (but enough) formalism.
But first let's get to know better how it works.

The trivial case is when n = 0 ( A = 1 ), which just yields B, no big deal.
In this case we are just aligning to a single byte boundary as A = 1.
So no adjustment to B is required and hence B itself is fine.

For a 4-bytes (32-bits) boundary alignment we would use n = 2.
That means we are interested in multiples of 4, that is, A = 4 and hence n = 2.

To get the whole idea of the formula, let's just work with n = 3, that is, A = 8.
Let's assume, for the sake of simplicity, a single-byte magnitude for the B value.
In a memory alignment scenario, B would be the value of a multi-byte pointer.
As a power of 2, the binary representation of A is a 1 followed by n zeros.
As a direct consequence ( A - 1 ) is always a sequence of n ones.
Hence ~( A - 1 ) is a bit-mask to clear out the first n least significant bits.

Look:
If n = 3,
then A = 8 = 10002 and ( A - 1 ) = 1112 and ~( A - 1 ) = 111110002.
And so what?