On Sat, 10 Apr 2010 22:53:42 -0400, Andrei Alexandrescu
<seewebsiteforem...@erdani.org> wrote:
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)
Couldn't help it, this seems like such a fun problem, I had to solve it :)
uint maxor(uint mina, uint maxa, uint minb, uint maxb)
{
uint bt = 1 << 31;
uint result = 0;
while(bt)
{
if((bt & maxa) && (bt & mina))
{
result |= bt;
if((bt & minb) ^ (bt & maxb))
{
return result | (bt-1);// always can choose all 1s for
rest of b
}
}
else if((bt & maxb) && (bt & minb))
{
result |= bt;
if((bt & mina) ^ (bt & maxa))
{
return result | (bt-1);// always can choose all 1s for
rest of a
}
}
else if(bt & (maxa | maxb))
{
result |= bt;
if(bt & (maxa & maxb))
{
// both maxa and maxb have bt set, and both mina and minb
have
// bt unset. This means we can choose this bit to be set
on
// either, and it is possible to have all 1s set for the
other
// for the rest of the bits.
return result | (bt - 1);
}
else if(bt & maxa)
{
// now that we are using this bit from maxa, we need to
raise
// mina so it becomes the smallest value with bt set.
However,
// we don't really care about bits above bt, so setting
// it to 0 is fine.
mina = 0;
}
else
{
minb = 0;
}
}
// else, neither maxa or maxb have bt set, continue to next bit.
bt >>= 1;
}
return result;
}
This only solves unsigned (tested all ranges against a brute force
solution up to max values of 64, given the nature of binary, I don't think
there can be any weird cases that wouldn't have problems at lower ranges.
Note that in my solution, maxa and maxb are inclusive.
Signed is probably trickier, suppose one is always negative and one is
always positive! I'm satisfied solving the unsigned for now, maybe
someone else can modify this solution to work with signed integers also :)
-Steve
