value range propagation for _bitwise_ OR

[Adam D. Ruppe]

On Sat, Apr 10, 2010 at 07:38:07PM -0400, Adam D. Ruppe wrote:
> I *might* have it, but I'm not 100% confident in my test program.

I think my test program is telling me something: a non-zero min_c subtracts from
max_c. If I take my brute-force empirically calculated max_c and compare it to
what my max_c function returns, it doesn't always match if the minimums change.

This might be a bug; it is unintuitive that it would do this, but it actually
makes sense. Consider if min == max, you only have one value to work with.

let max_a = 4, min_a = 0;

max_b = 4

You can get 7 out of it, since 3 < 4, so it is a possible number and: 100 | 011 == 7

But, if min_b == 4, the only possible value for b is 4. And: 100 | 100 == 4.

Increasing min_b does indeed decrease the max you can get.


Nice fact, but I've spent too much time on this already, so I'll call it done with
this:

My max_c included some unnecessary code: my reusable mask obsoletes all of
my special case code! So, we can bring the program down to three lines:

import std.intrinsic;
uint numbits(uint a) { return a == 0 ? a : (bsr(a) + 1); }
uint max_c(uint a, uint b) { return a | ((1 << numbits(a&b)) - 1) | b; }

It passes my test, though since I bugged it up the first time, I might have done
it again.

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