A Significant Bit of Fun – Part 2

By now I’m guessing you caught on to the pun. And since the title is just a pun, I frankly don’t care if you did not have any fun reading the first post. Perhaps I should refrain from using puns that imply your enjoyment reading my blog. Implications aside, its time for you to have some more fun.

In part 1 of this series, a way was devised to calculate the index of the most significant bit (msb) for a given bit string when interpreted as an unsigned integer. Here was the sample data we looked at last time:

• 0 0 0 0 0 0 0 0  = 0, msbi = undefined
• 0 0 0 0 0 0 0 1  = 1, msbi = 0
• 0 0 0 0 0 0 1 0  = 2, msbi = 1
• 0 0 0 0 0 0 1 1  = 3, msbi = 1
• 0 0 0 0 0 1 0 0  = 4, msbi = 2
• 0 0 0 0 0 1 0 1  = 5, msbi = 2
• 0 0 0 0 0 1 1 0  = 6, msbi = 2
• 0 0 0 0 0 1 1 1  = 7, msbi = 2
• 0 0 0 0 1 0 0 0  = 8, msbi = 3

Using 0-based indexes starting from the right, we can see the msb in blue and the msbi in this lovely olive color. Part 1 concluded with a formula to calculate msbi values:

• msbi(n) = ⌊log₂(n)⌋

I suppose the next item to address is the usefulness of what we’ve done. After that, we’ll address the usefulness of what we’re doing right now. If I can postpone practicality enough times in a row, we will use induction to prove that my blog posts are not very useful.

Given a bit string, a, how would we generate another bit string, b, such that:

1. a · b = a    (AND)
2. a + b = b   (OR)
3. msbi(a) = msbi(b)

An interesting property about these rules is that they yield a value which is binary repunit up to and including the msbi. I’m not sure there is a special name for a value with these properties, but please let me know if one exists. Until then, I will be referring to this value as msbq. Let’s look at some examples. Each bullet point shows a bit string above its corresponding msbq:

• 0 0 0 0 0 1 0 0
  0 0 0 0 0 1 1 1
• 0 0 0 0 0 1 0 1
  0 0 0 0 0 1 1 1
• 0 0 0 0 0 1 1 0
  0 0 0 0 0 1 1 1
• 0 0 0 0 0 1 1 1
  0 0 0 0 0 1 1 1
• 0 0 0 0 1 0 0 0
  0 0 0 0 1 1 1 1

As previously stated, the msbq is a binary repunit up to and including the msbi of our source bit string. At least that statement makes sense now that we see sample data. But how do we calculate this value? There is one obvious solution and one not-so-obvious solution that I would like to address. Let’s talk about the obvious solution first.

We know how to calculate the msbi, and we also know that this value is the 0-based index of the most significant bit. After reading that sentence a few times, it sounds like that buys us a two things. First, a loop invariant. Second, a base for a counter. Let’s see if we can use the msbi to construct a loop to shift a single bit left and bitwise-OR the result with an accumulator:

x = 11
count = msbi(x)
result = 0
while (count >= 0)

result = result | (1 << count)
count = count - 1

With result acting as an accumulator, we shift a single bit (the value 1) left a successive number of times and bitwise-OR the result with our accumulator. That’s nice and all, but I think we can do better. Let’s look at the non-obvious (relatively speaking) solution.

As it turns out, we can exploit a property of the binary number system to calculate the msbq without a loop and it starts by interpreting the msbi as an integer. Meaning, what is the integer value of the bit string where the only “on” bit is the one at the msbi? Here are some examples:

• 0 0 0 0 0 0 0 1, msbi = 0, msbv = 1
• 0 0 0 0 0 0 1 0, msbi = 1, msbv = 2
• 0 0 0 0 0 1 0 0, msbi = 2, msbv = 4
• 0 0 0 0 1 0 0 0, msbi = 3, msbv = 8

We will call this value msbv and we can calculate it one of two ways. We could shift 1 to the left msbi number of times:

msbv = 1 << msbi(x)

Or we could use powers of two:

msbv = 2^msbi(x)

So how does the msbv bridge the gap between the msbi and the msbq? It does so by exploiting the property I eluded to earlier. As it turns out, a power of 2 subtracted by 1 yields the summation of all lesser powers of two! Let’s see an example:

• 0 0 0 0 0 0 0 1, msbv = 1
• 0 0 0 0 0 0 1 0, msbv = 2
• 0 0 0 0 0 1 0 0, msbv = 4
• 0 0 0 0 1 0 0 0, msbv = 8; 8 – 1 = 7 = 4 + 2 + 1

Or more formally:

	i < n
2n = 1 +	Σ    2i
	i = 0

A little math goes a long way in this case. This looks a little easier on the eyes that our iterative solution above and it’s much easier to test and prove.

The only thing left is to show how to calculate the msbq given the msbv. As you might have already guessed, a simple bitwise-OR with our source value works out nicely:

msbq = x | msbv(x) – 1

And that’s it! Instead of boring you with some more examples, Here is some C# code for you to play with on your own time:

Func<int, int> msbi = x =>
    {
        return (int)Math.Log(x, 2);
    };
Func<int, int> msbv = x =>
    {
        return 1 << msbi(x);
        //return 2 ^ msbi(x);
    };
Func<int, int> msbq = x =>
{
    return x | msbv(x) - 1;
};

Where do we go from here? I suppose you’ll have to wait until part 3 to see if this comes together. I cannot promise that it will, but I will reserve the right to imply your enjoyment with puns.