finding N contiguous zero bits in an integer to the left of the MSB from another
- by James Morris
First we find the MSB of the first integer, and then try to find a region of N contiguous zero bits within the second number which is to the left of the MSB from the first integer.
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?
