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.

Simple counter case:

a's range is 4 to 5
b's range is 4 to 4

The max value of a | b is 5.

However, I think your function will return 15.

Also, you may to use the max of the smaller number.  For example:

a's range is 3 to 5
b's range is 4 to 4
The max number here is 7, but only when a is 3 and b is 4.  With your method, you automatically assume the number with the highest max value should be at its max value.

I think this is going to need a recursive solution, but I haven't yet wrapped my brain around how it needs to work.  I think you should start by assuming for a given range, mina to maxa, you know that the top 1-bits from ~(mina ^ maxa) will always be in the result, same with b.  If you eliminate those bits, the problem gets narrower.  I feel like a good solution first eliminates those, then decides how to set the next bit, and recurses.  I'm sure there's some sort of method to decide how to set the bit in order to avoid brute force, but I haven't thought about it enough.

-Steve

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

On Sat, 10 Apr 2010 22:53:42 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@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

On Sat, Apr 10, 2010 at 09:53:42PM -0500, Andrei Alexandrescu wrote:
> Ha! Good point. I'd forgotten the initial requirement and considered both values to start at 0. They don't! Adam? :o)

Yeah, my big brute-force tester program ran loops for min_a and min_b too. And it tripped an assert.

core.exception.AssertError@or.d(60): [10, 10]. expected: 3, got 2 (min == 2)

I hacked it by only asserting if the mins are zero too... but I did mention it a couple of times in my spam as the day has gone on.

I'm going to lecture a bit in this post. It is mostly for my benefit - maybe if I write up the patterns and thoughts explicitly, something new will come to mind.


My current solution uses a pattern I noticed:

0100
1000

There, the best you get is 1100.

But,

0100
1100

Lets you get to 1111. The reason is that duplicated one in there means you can trade a 100 for a 011, and still OR in the 100 thanks to the duplicate.

So, I take the two numbers and OR them together, but then, if there is a bit duplicated, I trade one of them for all the following ones, and or that in too.

That leads to the one liner solution: return a | ((1 << numbits(a&b)) - 1) | b;

We OR the two values, then use AND to find duplicated bits. We take the biggest one and trade it out (a power of two minus one gives us all those ones).

If there are no duplicated bits, a&b == 0, and 1 << 1 == 1, and 1 - 1 = 0, so it means no change, the correct solution!



Now, here's the problem: what if all those ones are unavailable due to the minimum value? The example I've been using is (4, 4). It would be nice to trade one of those 4's for a 3, but if the min value for each is also 4, this is impossible. The formula above would give 7, but this limitation means you can't get bigger than 4.

A minimum of one is fine still - it is the same as zero due to how OR works. The problem is a minimum of two or more. This cuts off ones from the right.

Oh, but not necessarily! You get a one on the end for ALL odd numbers, so unless the min == max && !(max&1), you get the one on the end.

So, the bigger the gap, the smaller our mask. Since the interval is inclusive, the most significant set bits on each max can never be masked out.


We'll use that as the starting point and write up a loop solution. We start at the right - the ones place - and or it in if the bit is available.

It looks like the another AND filter applied to the AND that's there, but
instead of using numbits(a&b), we should use numbits(something_min).

Which one are we carrying those ones from? Either, really. So as long as either one works, we should be ok.

Let's try it.

Nope :( The max is now too small.

Gah, I need to get to bed. Here's what I have:

=========
uint max_c(uint max_a, uint max_b, uint min_a, uint min_b) {
	uint tmp = max_a | max_b;

	uint true_min = min(min_a, min_b);
	if(min_a <= 1 || min_b <= 1)
		tmp |= ((1 << numbits(max_a&max_b)) - 1);
	else {
		// THIS PORTION IS WRONG
		tmp |= ((1 << numbits(max_a&max_b)) - 1);
		uint mask = min(msb(max_a), msb(max_b)) - 1;

		for(uint v = 1; v < mask; v <<= 1) {
			if(true_min - v && !(true_min & v))
				mask &= ~v;
		}

		tmp &= ~mask;
	}
	return tmp;
}
=========


-- 
Adam D. Ruppe
http://arsdnet.net

I normally lurk here, because I don't have any projects that use D and thus I haven't really learned it. But I just wanted to say that this problem, and the three threads of solutions, constitute one of the most fascinating discussions I've seen on the newsgroups in quite a while -- probably because I can almost solve the basic problem myself (though doubtless very sub-optimally).

Anyway, the strangeness of this particular problem is really very entrancing. I could sit and think about it all day -- except that it makes my brain hurt ;-).

On 2010-04-10 21:45, Adam D. Ruppe wrote:
> On Sat, Apr 10, 2010 at 09:53:42PM -0500, Andrei Alexandrescu wrote:
>> Ha! Good point. I'd forgotten the initial requirement and considered
>> both values to start at 0. They don't! Adam? :o)
>
> Yeah, my big brute-force tester program ran loops for min_a and min_b too.
> And it tripped an assert.
>
> core.exception.AssertError@or.d(60): [10, 10]. expected: 3, got 2 (min == 2)
>
> I hacked it by only asserting if the mins are zero too... but I did mention
> it a couple of times in my spam as the day has gone on.
>
> I'm going to lecture a bit in this post. It is mostly for my benefit - maybe
> if I write up the patterns and thoughts explicitly, something new will come
> to mind.
>
>
> My current solution uses a pattern I noticed:
>
> 0100
> 1000
>
> There, the best you get is 1100.
>
> But,
>
> 0100
> 1100
>
> Lets you get to 1111. The reason is that duplicated one in there means you
> can trade a 100 for a 011, and still OR in the 100 thanks to the duplicate.
>
> So, I take the two numbers and OR them together, but then, if there is
> a bit duplicated, I trade one of them for all the following ones, and
> or that in too.
>
> That leads to the one liner solution: return a | ((1<<  numbits(a&b)) - 1) | b;
>
> We OR the two values, then use AND to find duplicated bits. We take the
> biggest one and trade it out (a power of two minus one gives us all those
> ones).
>
> If there are no duplicated bits, a&b == 0, and 1<<  1 == 1, and 1 - 1 = 0,
> so it means no change, the correct solution!
>
>
>
> Now, here's the problem: what if all those ones are unavailable due to the
> minimum value? The example I've been using is (4, 4). It would be nice to
> trade one of those 4's for a 3, but if the min value for each is also 4,
> this is impossible. The formula above would give 7, but this limitation
> means you can't get bigger than 4.
>
> A minimum of one is fine still - it is the same as zero due to how OR works.
> The problem is a minimum of two or more. This cuts off ones from the right.
>
> Oh, but not necessarily! You get a one on the end for ALL odd numbers, so
> unless the min == max&&  !(max&1), you get the one on the end.
>
> So, the bigger the gap, the smaller our mask. Since the interval is inclusive,
> the most significant set bits on each max can never be masked out.
>
>
> We'll use that as the starting point and write up a loop solution. We start
> at the right - the ones place - and or it in if the bit is available.
>
> It looks like the another AND filter applied to the AND that's there, but
> instead of using numbits(a&b), we should use numbits(something_min).
>
> Which one are we carrying those ones from? Either, really. So as long as
> either one works, we should be ok.
>
> Let's try it.
>
> Nope :( The max is now too small.
>
> Gah, I need to get to bed. Here's what I have:
>
> =========
> uint max_c(uint max_a, uint max_b, uint min_a, uint min_b) {
> 	uint tmp = max_a | max_b;
>
> 	uint true_min = min(min_a, min_b);
> 	if(min_a<= 1 || min_b<= 1)
> 		tmp |= ((1<<  numbits(max_a&max_b)) - 1);
> 	else {
> 		// THIS PORTION IS WRONG
> 		tmp |= ((1<<  numbits(max_a&max_b)) - 1);
> 		uint mask = min(msb(max_a), msb(max_b)) - 1;
>
> 		for(uint v = 1; v<  mask; v<<= 1) {
> 			if(true_min - v&&  !(true_min&  v))
> 				mask&= ~v;
> 		}
>
> 		tmp&= ~mask;
> 	}
> 	return tmp;
> }
> =========

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));


-- 
Rainer Deyke - rainerd@eldwood.com

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

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 - rainerd@eldwood.com

Rainer Deyke wrote:

> 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.

But no value in the range may have all those bits set. As a result, a|b may have less bits set than fill_bits returns.

> In other words:
>
> min_v | (min_v + 1) | (min_v + 2) | ... | (max_v - 1) | max_v

That's the problem: Only one of those values is used in a|b at a time.

Here is the test code that I've been using when I tried to solve this problem:

import std.random;
import std.stdio;

void report(string label, uint value)
{
    writefln("%25s %032b %08x %10s", label, value, value, value);
}

// ...

unittest
{
    foreach (i; 0 .. 1000) {

        uint max_a = uniform(0, 1024);
        uint min_a = uniform(0, max_a + 1);

        uint max_b = uniform(0, 1024);
        uint min_b = uniform(0, max_b + 1);

        uint calculated_max_c = max_c_Deyke_2(min_a, max_a, min_b, max_b);

        report("min_a", min_a);
        report("max_a", max_a);
        report("min_b", min_b);
        report("max_b", max_b);
        report("calculated", calculated_max_c);

        uint emp_max_a;
        uint emp_max_b;
        uint empirical_max_c;
        foreach (a; min_a .. max_a + 1) {
            foreach(b; min_b .. max_b + 1) {
                if ((a | b) > empirical_max_c) {
                    emp_max_a = a;
                    emp_max_b = b;
                    empirical_max_c = a | b;
                }
            }
        }

        if (empirical_max_c != calculated_max_c) {
            report("WRONG! empirical", empirical_max_c);
            report("emp_max_a", emp_max_a);
            report("emp_max_b", emp_max_b);
            break;
        }
    }
}

Yes, it's incomplete, but does catch problems. :) So far, Steven Schveighoffer's maxor() is the only one that passes the tests. (There may be other solutions that I've missed.)

Ali

Ali Çehreli wrote:
> Yes, it's incomplete, but does catch problems. :) So far, Steven
> Schveighoffer's maxor() is the only one that passes the tests. (There
> may be other solutions that I've missed.)
> 
	I suggest you triple-check your implementations of everyone's
algorithms since the counter-example you found for my algorithm is
wrong (i.e my code gives the correct result).

		Jerome
-- 
mailto:jeberger@free.fr
http://jeberger.free.fr
Jabber: jeberger@jabber.fr