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...
This problem has nothing directly to do with values, it has something to
do with parts of values. The parts of values cannot be decided by
looking at only a pair.
Here are some values that the algorithm fails with ("mask" is printed
before returning from fill_bits) :
binary decimal
-----------------------------------
mask 0000000011 3
mask 0111111111 511
min_a 0000100100 36
max_a 0101100011 355
min_b 0000000001 1
max_b 0000000100 4
calculated 0101100011 355
WRONG! empirical 0101100111 359
emp_max_a 0101100011 355
emp_max_b 0000000100 4
The last two lines are telling: An unsuspected value of b happens to be
the one that produces the maximum value of a|b.
Ali
