value range propagation for _bitwise_ OR

[Adam D. Ruppe]

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


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