The basics of bit manipulation

Talking with fellow developers, I realized that many feel confused when it comes down to bit manipulation. It is indeed something not used on a day-to-day basis, but nevertheless the Android framework relies on it heavily in for memory optimizations: when a boolean can do, a bit can do too. Examples are View and Window flags. This post sets out to demystify the basics of bit manipulation: afterwards it will feel no more difficult than using arrays.

First, before manipulating bits, we need containers for them: let’s use plain Java ints for simplicity. For each int we have 32 positions to store bits. We will call 0 the least significant bit position and 31 the most significant one. Thinking bits as boolean elements in a container boils down bit problems to array problems: we only need to find out how to read and write such elements. We will write two methods, get() and set(), that given an int-container read and write respectively one of its elements.

The first line of get() divides n by 2^i (assuming n >= 0). If you think n in binary, this lops off the i least significant digits, filling in i zeros on the right. Example:

The second line of get() is equivalent to shifted % 2 (assuming n >= 0). Think again shifted in binary: all digits of shifted will be ‘and’-ed with a 0 except the least significant bit which will be ‘and’-ed with a 1. This means everything will be zero except the least significant bit that will its value: we effectively conserved only the information about the parity of shifted. Now let’s see the set() method.

We start splitting the general set() in two private methods, clear() and set(). The english espressions set and clear flag are standard jargon for setting a bit to 1 and clearing a bit to 0, and are used in Android too. First, consider the method clear(): we create a mask of the type 00..010..0 with a left shift, then we flip it to 11..101..1 by a bitwise negation. When we ‘and’ n with this mask we get a number which is the same as n, except having a 0 in the same place of the 0 in the mask: we cleared only one bit.

Now it is the turn of (private) set(): first, differently from arrays, ints are primitives, so we cannot hold a reference from outside and see the write: we need to create a new int, with the wanted bit set, and return it. Otherwise, the logic is similar to get(), except this time the mask looks like 00..010..0 and we ‘or’ it with n.