Is Any Bit Set Within a Range?

Introduction

In the last set of notes, we wrote a C function that would determine whether bit i was set or not. Can we generalize this function? In particular, can we implement the following prototype?

bool isBitSetInRange( char ch, int low, int high ) ;

This function returns true if any bit within b_high...b_low had a value of 1. We assume that low <= high. Note that all bits could be 1, or some bits could be 1, or exactly 1 bit in the range could be 1, and they would all return true. You return false only when all the bits in that range are 0.

In order to implement this function, we need to modify the mask. In particular, suppose low = 3 and high = 5, then we would expect the mask to look like:

b₇	b₆	b₅	b₄	b₃	b₂	b₁	b₀
0	0	1	1	1	0	0	0

How to Create a Mask with a Range

So we want to write code that creates a mask that looks like the one in the previous section. How can we do this? There are at several ways to do this.

Method 1 Write a for-loop that checks if bit i is set, from the previous section.

   for ( int i = low ; i <= high ; i++ )
     if ( isBitISet( ch, i )
       return true ;
   // If it didn't return true in the for-loop, then return false
   return false ;

The nice thing about this code is that it reuses the previous code. As a computer science major, the first solution ought to be one that uses an old solution.

However, the main drawback is using a loop. If the bitstring had been much longer (say, 32 or 64 bits), using a loop is more inefficient than not using one.

Method 2 This is somewhat complicated, so we'll need to break it down into steps.

First, we need to create a mask with the appropriate number of 1's. Suppose we want k 1's. Initially, we'll create a mask with n - k 0's, followed by k 1's. This is easier (for now) than creating the actual mask we need.
The question is how to compute k given low and high. This is a classic off-by-one situation. Your first instinct might be high - low. But this would be incorrect. If the index high == low, then high - low == 0.
That's not what you want. When high == low, you want to test for a single bit, i.e. b_high (which is the same as b_low since high == low). Thus, you want the formula to equal 1, when high == low.
So, the formula should be high - low + 1.
Here's the code to do this.
```
   unsigned char mask = ~0 ;   // creates all 1's, using bitwise negation of 0
   int numOnes = (high - low) + 1 ; 
   int numBits = sizeof( unsigned char ) * 8 ;

   // creates (numBits - numOnes) 0's followed by numOnes 1's
   mask >>= ( numBits - numOnes ) ; 
```
Then, we need to shift left to place the 1's in the correct spot. The question is how much to shift left. The answer is abit tricky. Here's how to figure the answer. Think about the least significant bit. It's at position b₀. It currently has a value of 1. Where should this bit end up? Since it's the rightmost bit, it should be the rightmost 1 when we shift left. And where's the rightmost 1? It's at b_low. So we need to shift left by low bits. The remaining 1's shift left with it, and the leftmost 1 should land at b_high because we computed the number of 1's ahead of time.
```
   mask <<= low ;
```

So, the entire code to create the mask looks like:

   unsigned char mask = ~0 ;   // creates all 1's, using bitwise negation of 0
   int numOnes = (high - low) + 1 ; 
   int numBits = sizeof( unsigned char ) * 8 ;

   // creates (numBits - numOnes) 0's followed by numOnes 1's
   mask >>= ( numBits - numOnes ) ; 
   mask <<= low ; // shift left group of 1's to correct location

Notice that no loops were used.

The one possible problem we have is the mask being shifted to the right. If we had used a signed char, instead of an unsigned char, we might have had the sign bit shifted in from the left. That would not create the desired mask (instead, it would leave us with all 1's).

So, here's a solution that avoids this problem.

   unsigned char mask = ~0 ;   // creates all 1's, using bitwise negation of 0
   int numOnes = (high - low) + 1 ; 

   // creates (numBits - numOnes) 1's followed by numOnes 0's
   mask <<= numOnes ; 

   // creates (numBits - numOnes) 0's followed by numOnes 1's
   mask = ~mask ;
   mask <<= low ; // shift left the group of 1's to correct location

By left shifting, we guarantee that 0's are shifted in from the right, regardless of whether the type is signed or unsigned. However, we need the additional step of negating the mask to get the pattern we want. This solution avoids using right shifts, thus should be more portable.

Method 3 The previous solution is moderately complicated to think about, though once you get used to the idea, it isn't all that bad.

A third way to produce the mask is to not only use bitshift operators, but also to use subtraction.

Consider the following two masks.

	b₇	b₆	b₅	b₄	b₃	b₂	b₁	b₀
maskHigh	0	0	1	1	1	1	1	1
maskLow	0	0	0	0	0	1	1	1
maskHigh - maskLow	0	0	1	1	1	0	0	0

So, if we could create a mask with high 1's and a mask with low 1's (as shown above), then subtract, we'd get the desired mask.

How can we get a mask with k 1's? To answer this, answer the following question. Suppose you have 1000 in base 10. This is 1, followed by 3 zeroes. If you subtract 1 from 1000, what do you get? You get 999. Suppose you have 100000. This is 1 followed by 5 zeroes. If you subtract 1 from that, you get 99999.

If you have 1, followed by k zeroes and you subtract 1 from it, then what do you get? You get k 9's.

Now, if this were binary, and you have 1 followed by k zeroes, and you subtract 1, what would you get? You'd get k 1's.

So here's the question. How do get 1, followed by k 0's? You bitshift 1 to the left by k!

  unsigned int mask = 1 << k ;
  mask -= 1 ; // Produces k 1's

So, here's how you get maskHigh and maskLow.

  unsigned char maskHigh = ( 1 << ( high + 1 ) ) - 1 ;
  unsigned char maskLow = ( 1 << low ) - 1 ;
  unsigned char mask = maskHigh - maskLow ;

There is a slight awkwardness when computing maskHigh. We want the leftmost 1 to appear at b_high. This means when we create the 1, followed by k zeroes, the "1" has to be shifted to bit position b_{high + 1}. On the other hand, no such problems occur with maskLow. The string of 1's we want appear in the correct location by shifting 1 to b_low.

If you're observant, you'll notice that when we compute mask, we're performing a computation that's of the form (x - 1) - (y - 1). Notice the 1's cancel, and you get (x - y).

So, we can get the mask without subtracting 1, as in:

  unsigned char mask = ( 1 << ( high + 1 ) ) - ( 1 << low ) ;

Which method is perferable? Method 2 is a little complicated, but is completely restricted to bitwise and bitshift operators. The advantage of that is that it works on signed and unsigned quantities.

Method 3 is simpler to understand, but uses subtraction. This turns out to work whether the type is signed or unsigned.

Putting it All Together

Once you create the mask, the code is really simple to check the range.

bool isBitSetInRange( char ch, int low, int high ) 
{
   unsigned char mask = .... ;
   // code to create mask

   return ch & mask ;
}

It's the same as before. This time, however, ch & mask may produce a result that has more than single bit with a value of 1, whereas the mask that checked for bit i being one could only produce a result that has, at most, one bit with a value of 1.

However, it doesn't matter how many bits are 1. As long as at least one bit is 1, then the result is non-zero, and thus, the return value is true.

Summary

We wish to generalize the problem of determining whether a single bit is set to determining whether any one of a range of bits are set. To write such a function, we generalize the mask to be some number of 0's, followed by some number of 1's, followed by some number of 0's, where there bits that are 1 fall within the desired range.

Web Accessibility