Bit-Arrays and Constant Time Device Number Access

This article comes from a class in embedded systems that I am currently taking.

Warning some basic knowledge of bit operations and programing is required.

1. Problem Statement

Consider the problem of device addressing. This can be done using what is called a flag variable. This is a bit-array (a binary number in essence). This process is as follows:

Device signals that it is ready
- Sets flag in bit-array
- (Optionally) triggers an interrupt
Control device responds to signal
- Through some system of polling and/or interrupt handlers
Base case is restored
- Control device resets device flag in bit-array
- Cleans up unneeded extraneous objects and/or locks

Thus the problem seems to be as follows. Given a binary number \\(latex (b\_{15}, b\_{14}, ..., b\_0)\_2\\), corresponding to the devices numbered 0-15 respectively, how do I know which bits are set, which devices need service. Of notice is that we are not necessarily given that only one bit is set (This is of importance later).

One might try to address this problem naively as follows.

1.1. Algorithm #1

var i = 0 // counter for bit position
var temp = flags
while temp != 0
  if temp & 1 == 1 // is bit 0 set
    var device_num = i
    temp = temp >> 1 //divided by 2

This algorithm takes at worst case O(n) where n is the number of bits in the bit-array. We could not possibly do better than this though, right?

2. The Better Solution

So I will included two references at this point. One is to an awesome page from Stanford and another a good blog post on basic bit shifting techniques.

Stanford: https://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn

Peter Krumins: http://www.catonmat.net/blog/low-level-bit-hacks-you-absolutely-must-know/

The basics of the new algorithm are as follows

2.1. Algorithm #2*

var temp = flags
while temp != 0
  if "temp's has a rightmost bit set"
    "get this bit" //ex. 0010 => 0010, 0101 => 0001 ...
    "find log_2(bit)"
    temp = temp & ~"bit" // resets only bit flag

This would be great if it were not for the problem of finding the log base 2 of a number. That would be inefficient. This would be my thought process but thanks to math this can be done in constant time (check Stanford page).

Integrating the solutions to the quoted portions using bit operations yields the following solution.

2.2. Algorithm #2

var temp = flags
while temp != 0
  // if not needed since temp != 0 implies that a bit is set
  // Log lookup table = Stanford, temp & (-temp) finds rightmost bit = Krumins
  var device_number = LOG_TABLE[((temp&(-temp) * 0x077CB531U) >> 27]
  temp = temp & ~(1 << device_number)

The reason this works is that finding the rightmost bit makes the bit-array a power of two. Then using the log table as described in the Stanford page can be done in constant time. Thus we now have a constant time algorithm for this procedure. Albeit, we do now have extra space due to the log table. But, that is computing, a game of trade-offs.

PS: The reason for the temp variable follows from the reason for noting that more than one device may be set at once. As food for thought, show that this does solve a potential starvation problem.