On 04/10/2010 09:51 PM, Steven Schveighoffer wrote:
Andrei Alexandrescu Wrote:
On 04/10/2010 12:01 PM, Andrei Alexandrescu wrote:
Consider:
byte c = a | b;
Say you already know min_a, max_a, min_b, and max_b. How do you
compute min_c and max_c? I thought of it for a bit and it seems
quite tricky.
Thanks,
Andrei
I think this would work:
uint maxOR(uint maxa, uint maxb) { if (maxa< maxb) return
maxOR(maxb, maxa); uint candidate = 0; foreach (i, bit;
byBitDescending(maxa)) { if (bit) continue; auto t = candidate |
(1<< (31 - i)); if (t<= maxb) candidate = t; } return maxa |
candidate; }
The idea is to find the candidate that would fill as many zeros in
maxa as possible.
But this is inefficient. I'm wondering whether a simple bitwise
manipulation expression could do the trick.
Don't you need to take into account the minimum of b also? That is,
the candidate needs to be greater than minb. Because filling in more
holes doesn't necessarily mean biggest number, I don't think it
works.
Ha! Good point. I'd forgotten the initial requirement and considered
both values to start at 0. They don't! Adam? :o)
Andrei
