In order to align a data structure at the nearest wordalignment to a given starting address, we’d must find the smallest multiple of N (a power of 2) which is greater than or equal to integer X. Is there a way we can make this fast, i.e. not use division or modulo?
First Thoughts
First of all
1


Otherwise, we have two cases
First Case
N: 00100
X: 01100

=> 01100
This example indicates the following:
1


Second Case
N: 00100
X: 01101

=> 10000
Which can be accomplished by
1


So we have the firsttake program of
1 2 3 

Engineering Wisdom
The above solution is in fact correct (takes a quick bow).
When I looked up a better answer on StackOverflow, I found a program that does not use conditionals, and is therefore much faster
1


However, it was not obvious to me that this program works! Let’s peer inside and see how similar it is to my solution.
First we’re going to compute something, and then we’re going to “and” it with
~(N1)
. Well, “and”ing anything against ~(N1)
is going to round it down
to a multiple of N. So that part is taken care of.
Now we need to get the right multiple of N. if X < N
, then then adding X to
N and rounding down to a multiple N is just going to give us N. That’s the
first line of my answer, taken care of.
So if X > N
, we either do or don’t have bits in place values below N. This is
what my last two lines are taking care of. However, we can deal with this by
noting that after we add X to N, if there are bits in place values below N,
when we subtract 1, it will not change any bits that will survive the “and”
stage. But if there are no bits in place values below N, then subtracting one
will decrement our answer wrt bits N and higher.
Hmm, not the best explanation of all time. But that’s what’s going on in there.