﻿ Fun with bits 1

Fun with bits 1

What does the following ARM code do to the value in register r0?

SUB r1,r0,#1

AND r0,r1,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

Repeat

Shift x one place right

count = count + 1

Until carry out = 1 or count = 32

Repeat

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.