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

This graphics.stanford.edu/~seander/bithacks.... 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).

This graphics.stanford.edu/~seander/bithacks.... 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.

I've edited the question several thousand times now and hopefully the code comments, the rewording of the question, and the inclusion of a (slightly) better test case will contribute to your better understanding of the problem - which, I'm starting to believe I'll get zero answers on and have wasted several hours trying to clarify something which already works! – James Morris May 8 '10 at 1:23.

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> 1; // clear leading ones from groups } offset = count_trailing_zero_bits( last ); } else { count = lz2; offset = 32 - lz2; } return ( count >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 MultiplyDeBruijnBitPosition32 = { 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.

This code gives very different results to my code - for simplicity I just replaced each call to count_leading_zero_bits with the 2 line MSB finding while loop from mine. Am I right in assuming value relates to var1 in and other relates to var2 from my code? Also, can you state if this finds regions of zeros contained within set bits?

– James Morris May 8 '10 at 18:20 Is your msb loop destructive? In your original posting it shifts the input value. I added what the expected value would be at each iteration of the loop.

– drawnonward May 9 '10 at 2:36 val1 having only a single bit set is an artificiality imposed to make finding regions of zero bits more likely. – James Morris May 9 '10 at 9:23 +1 for effort, and, causing me to think hard enough to come to a solution. Thanks.

– James Morris May 9 '10 at 16:13 I have always liked bit manipulation. What did you come up with as a final solution? – drawnonward May 9 '10 at 16:47.

Here is my new and improved algorithm: int test_fit_within_left_of_msb( unsigned width, unsigned val1, unsigned val2 ) { int offset = 32; int msb = 0; unsigned mask; unsigned b; msb = 32 - __builtin_clz(val1); /* GCC builtin to count Leading Zeros */ while(offset - width > msb) { mask = (((unsigned)1 You could nit pick over subtracting the offset from 32. The important point here in the code, is the algorithm - I realize there are portability concerns and assumptions made about types and there sizes. Looking back up the page to the output where width 8 can be found at position 12 performed in 10 iterations, the new alogirthm does the same in 2 iterations of the loop.

I've used the GCC builtins for convenience here, the MultiplyDeBruijnBitPosition code that drawonward provided ( from: graphics.stanford.edu/~seander/bithacks.... ) can be used to replace __builtin_ctz, while __bultin_clz could be replaced with one of the integer log base 2 codes from the same page. One concern here though, is the data (with sparsely set bits) I've used to test this with makes this algorithm perform better, this will maybe not be so great looking at integers with more densely set bits. (Not correct - by counting the trailing zeros it avoids this bad case).

After implementing my previous answer but to work for the right of the MSB, I saw that aside from a very minor difference, the left and right versions were exactly the same. This lead to the realization there is no real requirement for the algorithm to be working with an MSB from some prior value at all. So although this answer does not meet the specifications of the question, it is the correct answer because the specification was incorrect.

#include /* returns bit position within a 32bit integer, where a region of contiguous zero bits can be found whose count is equal to or greater than width. It returns -1 on failure. */ int binary_width_fit( unsigned width, uint32_t val ) { int offset = 32; uint32_t mask; uint32_t b; while(offset >= width) { mask = (((uint32_t)1.

This is not so great with small widths. Improved version uses GCC builtin to count the leading ones before applying the mask to further reduce the loop's iteration count. – James Morris May 10 '10 at 0:34 I wish you had put that comment in the original question.

– nategoose May 10 '10 at 15:57 @nategoose: do you mean the comment about there being no real requirement for working within the left of some MSB rather than the whole range of bits? If so, I can add it as an edit, and if you come up with a better solution I'll be happy to accept it if it is indeed better... When I asked the question I'd not figured everything out, it seems like it's taken quite a while to get to this stage, where I realize constraining the process to one side of the MSB (etc). – James Morris May 10 '10 at 18:26 The in code comment was what explained what you wanted to me, even though you swapped which end of the word you were working from.

BTW, you could do int offset = 8*sizeof(unsigned long); and make this take advantage of larger native word sizes and be portable, if having more bits is useful. – nategoose May 10 '10 at 21:24.

1 (fast) method is to use precalulated LOOKUP TABLES (LUTs) for each 8bit byte: PosOfFirst1, PosOfLast1, PosOfFirst0, PosOfLast0 -- all arrays of 256 bytes Precalculate the tables using: (soz for poor, pascalish pseudocode) PosOfLast1: FOR EACH ByteVal (0..255): if byteVal>127 return 8 elseif byteVal>63 return 7 ... elseif byteVal>0 return 1 else return 0 PosOfFirst1: c:=0; while cFast For larger sizes (0, 16, 24, 32 +++++) use procs and loops that check each constituent 8bit byte. Memory access to the LUT may be needed but this method is still faster: a) Can be used easily without needing a procedure call. B) scanning a 32 bit number takes 1 shift & comparison to 0 per byte with 1 lookup needed (if a non-zero byte is found) instead of n (0..32) shifts, ands and comparisons... c) if programmed well will halt after finding 1st/last 1 The LUT principle applies to 'population count' + other bit manip.Routines... Cheers, PrivateSi FASTER IS BETTER?!

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.