Finding N contiguous zero bits in an integer to the left of the MSB position of another integer
- by James Morris
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, with the minimum number of zero bits given by width to the left of the position (ie, in the higher bits).
Here is the C code for my solution:
typedef unsigned int t;
unsigned const t_bits = sizeof(t) * CHAR_BIT;
_Bool test_fit_within_left_of_msb( unsigned width,
t val1,
t val2,
unsigned* offset_result)
{
unsigned offbit = 0;
unsigned msb = 0;
t mask;
t b;
while(val1 >>= 1)
++msb;
while(offbit + width < t_bits - msb)
{
mask = (((t)1 << width) - 1) << (t_bits - width - offbit);
b = val2 & mask;
if (!b)
{
*offset_result = offbit;
return true;
}
if (offbit++) /* this conditional bothers me! */
b <<= offbit - 1;
while(b <<= 1)
offbit++;
}
return false;
}
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.
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)
