Finding N contiguous zero bits in an integer to the left of the MSB position of another integer

Question

The problem is: given an integer val1 find the position of the highest bit set (Most Significant Bit) then, given a second integer val2 find a contiguous region of unset bits to the left of the position yielded from the first integer. width specifies the minimum number of unset bits that must be found in contiguity (ie width zeros without ones within them).

Here is the C code for my solution:

#include <limits.h> /* for CHAR_BIT - number of bits in a char */

typedef unsigned int t;
unsigned const t_bits = sizeof(t) * CHAR_BIT;

_Bool test_fit_within_left_of_msb(  unsigned width,
                                    t val1, /* integer to find MSB of */
                                    t val2, /* integer to find width zero bits in */
                                    unsigned* offset_result)
{
    unsigned offbit = 0; /* 0 starts at high bit */
    unsigned msb = 0;
    t mask;
    t b;

    while(val1 >>= 1) /* find MSB! */
        ++msb;

    while(offbit + width < t_bits - msb)
    {
        /* mask width bits starting at offbit */
        mask = (((t)1 << width) - 1) << (t_bits - width - offbit);
        b = val2 & mask;

        if (!b) /* result! no bits set, we can use this */
        {
            *offset_result = offbit;
            return true;
        }

        if (offbit++) /* this conditional bothers me! */
            b <<= offbit - 1;

        while(b <<= 1)
            offbit++; /* increment offbit past all bits set */
    }
    return false; /* no region of width zero bits found, bummer. */
}

Aside from faster ways of finding the MSB of the first integer, the commented test for a zero offbit seems a bit extraneous, but necessary to skip the highest bit of type t if it is set. Unconditionally left shifting b by offbit - 1 bits will result in an infinite loop and the mask never gets past the 1 in the high bit of val2 (otherwise, if the high bit is zero no problem).

I have also implemented similar algorithms but working to the right of the MSB of the first number, so they don't require this seemingly extra condition.

How can I get rid of this extra condition, or even, are there far more optimal solutions?

Edit: Some background not strictly required. The offset result is a count of bits from the high bit, not from the low bit as maybe expected. This will be part of a wider algorithm which scans a 2D array for a 2D area of zero bits. Here, for testing, the algorithm has been simplified. val1 represents the first integer which does not have all bits set found in a row of the 2D array. From this the 2D version would scan down which is what val2 represents.

Here's some output showing success and failure:

t_bits:32
     t_high: 10000000000000000000000000000000 ( 2147483648 )
---------

-----------------------------------
*** fit within left of msb test ***
-----------------------------------
      val1:  00000000000000000000000010000000 ( 128 )
      val2:  01000001000100000000100100001001 ( 1091569929 )
msb:   7
offbit:0 + width: 8 = 8
      mask:  11111111000000000000000000000000 ( 4278190080 )
      b:     01000001000000000000000000000000 ( 1090519040 )
offbit:8 + width: 8 = 16
      mask:  00000000111111110000000000000000 ( 16711680 )
      b:     00000000000100000000000000000000 ( 1048576 )
offbit:12 + width: 8 = 20
      mask:  00000000000011111111000000000000 ( 1044480 )
      b:     00000000000000000000000000000000 ( 0 )
offbit:12
iters:10


***** found room for width:8 at offset: 12 *****

-----------------------------------
*** fit within left of msb test ***
-----------------------------------
      val1:  00000000000000000000000001000000 ( 64 )
      val2:  00010000000000001000010001000001 ( 268469313 )
msb:   6
offbit:0 + width: 13 = 13
      mask:  11111111111110000000000000000000 ( 4294443008 )
      b:     00010000000000000000000000000000 ( 268435456 )
offbit:4 + width: 13 = 17
      mask:  00001111111111111000000000000000 ( 268402688 )
      b:     00000000000000001000000000000000 ( 32768 )
 ***** mask: 00001111111111111000000000000000 ( 268402688 )
offbit:17
iters:15


***** no room found for width:13 *****

(iters is the count of iterations of the inner while loop, b is result val2 & mask)

Answer 1

This http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious has several ways to calcuate the unsigned integer log base 2 of an unsigned integer (which is also the position of the highest bit set).

I think that this is part of what you want. I suspect that if I really knew what you want I could suggest a better way of calculating it or something that served the same purpose.

Answer 2

count_leading_zero_bits is often a single instruction that the compiler will provide an inline function for. otherwise put it in a loop.

count_trailing_zero_bits can use count_leading_zero_bits(x&-x) or a debruijn lookup if the former is a loop.

for simplicity I assume 32 bit values.

int offset_of_zero_bits_over_msb_of_other_value( unsigned width , unsigned value , unsigned other ) {
  int count = 0;
  int offset = -1;
  int last = 1;
  int lz = count_leading_zero_bits( other );
  other |= ((1<<(32-lz2))-1); // set all bits below msb
  if ( value & ~other ) {
    value |= other; // set all bits below msb of other
    value = ~value; // invert so zeros are ones
    while ( value && count < width ) {
      count += 1; // the widest run of zeros
      last = value; // for counting trailing zeros
      value &= value >> 1; // clear leading ones from groups
    }
    offset = count_trailing_zero_bits( last );
  } else {
    count = lz2;
    offset = 32 - lz2;
  }
  return ( count < width ) ? -1 : offset;
}

The idea behind the code is this:

  val1:  00000000000000000000000010000000 ( 128 )
  val2:  01000001000100000000100100001001 ( 1091569929 )
  lz1:   24
  lz2:   1
  val2:  01000001000100000000100011111111 // |= ((1<<(32-lz1))-1);
  val2:  10111110111011111111011100000000 // = ~val2
  val2:  00011110011001111111001100000000 // &= val2>>1 , count = 1
  val2:  00001110001000111111000100000000 // &= val2>>1 , count = 2
  val2:  00000110000000011111000000000000 // &= val2>>1 , count = 3
  val2:  00000010000000001111000000000000 // &= val2>>1 , count = 4
  val2:  00000000000000000111000000000000 // &= val2>>1 , count = 5
  val2:  00000000000000000011000000000000 // &= val2>>1 , count = 6
  val2:  00000000000000000001000000000000 // &= val2>>1 , count = 7
  val2:  00000000000000000000000000000000 // &= val2>>1 , count = 8

So at each step, all ranges of zeros, now ones, are shrunken from the right. When the value is zero, the number of steps taken is the width of the widest run. At any point, counting the number of trailing zeros will give the offset to the nearest range of at least count zeros.

If at any point count exceeds width, you can stop iterating. The maximum number of iteration is thus width, not the word size. You could make this O(log n) of width, because you can double the shift amount at each iteration as long as you do not exceed width.

Here is a DeBruijn lookup for counting trailing zero bits for 32 bit values.

static const int MultiplyDeBruijnBitPosition[32] = {
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];

I noticed that in both your examples, val1 had only a single bit set. If that is the case, you can use the DeBruijn trick to find the MSB.