View mode: basic / threaded / horizontal-split · Log in · Help
April 10, 2010
value range propagation for logical OR
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
April 10, 2010
Re: value range propagation for logical OR
On Sat, 10 Apr 2010 12:01:45 -0500, Andrei Alexandrescu 
<SeeWebsiteForEmail@erdani.org> 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

It seems like it would use the lowest minimum and the highest maximum of 
the two... that's what I personally would find most natural, given the 
semantics of bitwise OR, but maybe I'm just way off base.
April 10, 2010
Re: value range propagation for logical OR
On 04/10/2010 12:22 PM, Justin Spahr-Summers wrote:
> On Sat, 10 Apr 2010 12:01:45 -0500, Andrei Alexandrescu
> <SeeWebsiteForEmail@erdani.org>  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
>
> It seems like it would use the lowest minimum and the highest maximum of
> the two... that's what I personally would find most natural, given the
> semantics of bitwise OR, but maybe I'm just way off base.

I thought the same, but consider:

a = 4;
b = 3;

Then the maximum value is 7, larger than both.


Andrei
April 10, 2010
Re: value range propagation for logical OR
On Sat, Apr 10, 2010 at 12:01:45PM -0500, Andrei Alexandrescu wrote:
> 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.

min_c seems easy enough:
min_c = max(min_a, min_b);

When you or two values together, the result must be >= both of them, and this
does the trick there.

max_c is a bit harder. The obvious solution of:

max_c = max(max_a, max_b);

Fails because of 0b1100 | 0b0011... looking at this example, let's try:

max_c = max_a + max_b;

It covers that case, but is too big for 0b1111 | 0b1111.

This might work:

int numbits(number) { return the number of bits required to hold that number; }

if ( numbits(max_a + max_b) > max(numbits(max_a), numbits(max_b)) )
   max_c = 2 ^^ (max(numbits(max_a), numbits(max_b))) - 1;
else
   max_c = max_a + max_b;


The biggest we can possibly get is the sum of the two numbers. But, if it carries
over to more bits than either option, we truncate it - OR never gives more bits
than the two arguments. So we assume the max is the worst case of all ones or'd
with all ones.

I think this would work, but might not be the best we can possibly do. It is the
best I can think of though.

-- 
Adam D. Ruppe
http://arsdnet.net
April 10, 2010
Re: value range propagation for _bitwise_ OR
(By the way I meant _bitwise_ in the title.)

On 04/10/2010 12:38 PM, Adam D. Ruppe wrote:
> On Sat, Apr 10, 2010 at 12:01:45PM -0500, Andrei Alexandrescu wrote:
>> 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.
>
> min_c seems easy enough:
> min_c = max(min_a, min_b);
>
> When you or two values together, the result must be>= both of them, and this
> does the trick there.

Yah, that works for unsigned types. For signed types, it's tricky (as 
tricky as max).

> max_c is a bit harder. The obvious solution of:
>
> max_c = max(max_a, max_b);
>
> Fails because of 0b1100 | 0b0011... looking at this example, let's try:
>
> max_c = max_a + max_b;
>
> It covers that case, but is too big for 0b1111 | 0b1111.

Yah, sum is a bound for max, but not the exact max. This is because 
bitwise OR is like a sum without transport.

> This might work:
>
> int numbits(number) { return the number of bits required to hold that number; }
>
> if ( numbits(max_a + max_b)>  max(numbits(max_a), numbits(max_b)) )
>      max_c = 2 ^^ (max(numbits(max_a), numbits(max_b))) - 1;
> else
>      max_c = max_a + max_b;
>
>
> The biggest we can possibly get is the sum of the two numbers. But, if it carries
> over to more bits than either option, we truncate it - OR never gives more bits
> than the two arguments. So we assume the max is the worst case of all ones or'd
> with all ones.
>
> I think this would work, but might not be the best we can possibly do. It is the
> best I can think of though.

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.


Andrei
April 10, 2010
Re: value range propagation for _bitwise_ OR
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.


Andrei
April 10, 2010
Re: value range propagation for logical OR
Andrei Alexandrescu:
> 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.

This is Interval arithmetic. If you are able to find a book about it... (or a library for some programming language that implements it).

Bye,
bearophile
April 10, 2010
Re: value range propagation for _bitwise_ OR
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
April 10, 2010
Re: value range propagation for _bitwise_ OR
On 4/10/2010 11:52, Andrei Alexandrescu wrote:
> 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;
> }

This looks wrong.  Your function, if I understand it correctly, flips
all the bits in 'maxb' (excluding the leading zeros).  If 'maxb' is
exactly 1 less than a power of 2, then 'candidate' will be 0.  Now
consider a in [0, 16], b in [0, 15].  Your function will produce 16, but
the real maximum is 31.

For maximum accuracy, you have to consider the minima as well as the
maxima when calculating the new maximum.  With 'a' in [16, 16] and 'b'
in [16, 16], the new range can only be [16, 16].  With 'a' in [0, 16]
and 'b' in [0, 16], the correct new range is [0, 31].


-- 
Rainer Deyke - rainerd@eldwood.com
April 10, 2010
Re: value range propagation for _bitwise_ OR
Adam D. Ruppe:

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

Time ago I have even suggested to disallow bitwise ops when one or both operands are signed...

Bye,
bearophile
« First   ‹ Prev
1 2 3 4 5
Top | Discussion index | About this forum | D home