Fun with bits 1
What does the following ARM code do to the value in register r0?
Suppose that we are using 8-bit arithmetic and that r0 initially contains the binary
value 11011100. Subtracting 1 gives 11011011 and ANDing with 11011100 gives 1101000.
What’s happened? The 1 in the least-significant bit position has been inverted to
give 0. The effect of this code is to take a word and force the least-significant
bit that is a 1 to to be cleared to; for example 010111000 would become 010110000.
If we’d used a brute force method, we might have done something like:
Count = 1
Shift x one place right
count = count + 1
Until carry out = 1 or count = 32
Shift x one place left
count = count - 1
Until count = 0
Why does the algorithm work?
We are evaluating X(X - 1)
Consider X as the bit pattern xxxx100…0. This is equivalent to xxxx000…0 + 0000100…0.
If we subtract 1 from this we get: xxxx000…0 + 0000011…1 = xxxx011…0.
If we now perform a logical AND between xxxx100…0 and xxxx011…1 we get xxxx000…0,
which is the original value with the least-significant 1 cleared.