On 4/11/2010 11:16, Ali Çehreli wrote: > Rainer Deyke wrote: >> How about this? >> >> uint fill_bits(uint min_v, uint max_v) { >> uint mask = 0; >> for (int i = 0; i < 32; ++i) { >> if ((min_v | (1 << i)) <= max_v) mask |= (1 << i); >> } >> return mask; >> } >> >> max_c = min( >> max_a | fill_bits(min_b, max_b), >> max_b | fill_bits(min_a, max_a)); >> >> > > That proposal looks at the two pairs of a and b separately. For example, > works with min_a and max_a, and decides a bit pattern. > > What if the allowable bit pattern for the b pair has 0 bits that would > be filled with an value of a that was missed by fill_bits for a? Imagine > a value of a, that has little number of 1 bits, but one of those bits > happen to be the one that fills the hole in b...
The intention of fill_bits is to create a number that contains all of the bits of all of the numbers from min_v to max_v. In other words: min_v | (min_v + 1) | (min_v + 2) | ... | (max_v - 1) | max_v It does this by considering each bit separately. For each bit 'i', is there a number 'n' with that bit set such that 'min_v <= n <= max_v'? 'min_v | (1 << i)' is my attempt at calculating the smallest number with bit 'i' set that satisfies 'min_v | (1 << i)'. This is incorrect. Correct would be '(min_v & (1 << i)) ? min_v : ((min_v >> i) << i) | (1 << i)'. My other mistake is this bit: max_c = min( max_a | fill_bits(min_b, max_b), max_b | fill_bits(min_a, max_a)); This is my attempt to get a tighter fit than 'fill_bits(min_a, max_a) | fill_bits(min_b, max_b)'. It doesn't work correctly, as you have pointed out. Here is my revised attempt, with those errors corrected: uint fill_bits(uint min_v, uint max_v) { uint mask = min_v; for (int i = 0; i < 32; ++i) { if ((min_v & (1 << i)) == 0) { if ((((min_v >> i) << i) | (1 << i)) <= max_v) { mask |= (1 << i); } } } return mask; } max_c = fill_bits(min_a, max_a) | fill_bits(min_b, max_b); -- Rainer Deyke - rain...@eldwood.com