value range propagation for _bitwise_ OR

[Adam D. Ruppe]

On Sat, Apr 10, 2010 at 12:39:22PM -0500, Andrei Alexandrescu wrote:
> Yah, that works for unsigned types. For signed types, it's tricky (as 
> tricky as max).

My feeling is to go ahead and cast to unsigned, then do the calculation. For
me at least, when doing bitwise ops, I assume it is unsigned anyway.

> Even on the branch that doesn't use the sum, that's still just a bound. 
> Consider:
> 
> a = 8;
> b = 4;
> 
> Then max(a|b) is 12, but computed with your method is 15.

Yeah, you're right. Bah. Maybe:

max_a = max(a, b) | (2 ^^ numbits(min(a, b)) - 1);

8 | 7 == 15;

Same deal, still wrong. Maybe we can throw in one more thing:

let f(a, b) = the above;
max_c = min(f(a, b), a | b);


Let me test it... it seems to work. Here's the D program I used to brute-force
the test:

===
import std.intrinsic; // for bsr()

uint max(uint a, uint b) { return (a >= b) ? a : b; }
uint min(uint a, uint b) { return (a >= b) ? b : a; }

uint numbits(uint a) { return a == 0 ? a : bsr(a) + 1; }

unittest {
	assert(numbits(0) == 0);
	assert(numbits(1) == 1);
	assert(numbits(2) == 2);
	assert(numbits(3) == 2);
	assert(numbits(4) == 3);
	assert(numbits(5) == 3);
}

uint f(uint a, uint b) {
	return max(a, b) | (1 << numbits(min(a, b)) - 1);
}

uint max_a(uint a, uint b) {
	return min(f(a, b), a | b);
}

void main() {
	for(uint a = 0; a <= 256; a++)
	for(uint b = 0; b <= 256; b++)
		assert(a|b <= max_a(a, b));
}
=======

I compiled with the unittests, and it closed without tripping any asserts.
Eyeballing the output looks right too.

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