value range propagation for _bitwise_ OR

[Nathan Tuggy]

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 at 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;
> }
> =========