Jump to page: 1 29  
Page
Thread overview
value range propagation for logical OR
Apr 10, 2010
Adam D. Ruppe
Re: value range propagation for _bitwise_ OR
Apr 10, 2010
Adam D. Ruppe
Apr 10, 2010
bearophile
Apr 10, 2010
Adam D. Ruppe
Apr 10, 2010
bearophile
Apr 10, 2010
Adam D. Ruppe
Apr 10, 2010
Adam D. Ruppe
Apr 10, 2010
bearophile
Apr 11, 2010
bearophile
Apr 10, 2010
Adam D. Ruppe
Apr 10, 2010
Adam D. Ruppe
Apr 11, 2010
Adam D. Ruppe
Apr 11, 2010
Adam D. Ruppe
Apr 11, 2010
Ali Çehreli
Re: value range propagation for _bitwise_ OR
Apr 10, 2010
Rainer Deyke
Apr 10, 2010
Don
Apr 11, 2010
PBa
Apr 10, 2010
Adam D. Ruppe
Apr 10, 2010
Jérôme M. Berger
Apr 11, 2010
Jérôme M. Berger
Apr 11, 2010
Jérôme M. Berger
Apr 11, 2010
Ali Çehreli
Apr 11, 2010
Jérôme M. Berger
Apr 11, 2010
Ali Çehreli
Apr 12, 2010
Jérôme M. Berger
Apr 12, 2010
Ali Çehreli
Apr 11, 2010
Jérôme M. Berger
Apr 12, 2010
Adam D. Ruppe
Apr 12, 2010
Jérôme M. Berger
Apr 20, 2010
Don
Apr 12, 2010
Jérôme M. Berger
Apr 12, 2010
Jérôme M. Berger
Apr 13, 2010
Jérôme M. Berger
Apr 13, 2010
Jérôme M. Berger
Apr 13, 2010
Fawzi Mohamed
Apr 13, 2010
bearophile
Apr 13, 2010
Fawzi Mohamed
Apr 13, 2010
Don
Apr 13, 2010
Fawzi Mohamed
Apr 13, 2010
Jérôme M. Berger
Apr 12, 2010
Jérôme M. Berger
Apr 12, 2010
Jérôme M. Berger
Apr 12, 2010
Ali Çehreli
Apr 13, 2010
Jérôme M. Berger
Apr 13, 2010
Don
Apr 13, 2010
Adam Ruppe
Apr 13, 2010
bearophile
Apr 13, 2010
Adam D. Ruppe
Apr 13, 2010
Clemens
Apr 13, 2010
Adam D. Ruppe
Apr 13, 2010
Don
Apr 13, 2010
Don
Apr 13, 2010
Jérôme M. Berger
Dec 04, 2010
Ellery Newcomer
Dec 04, 2010
Ellery Newcomer
Apr 10, 2010
bearophile
Apr 10, 2010
BCS
Apr 10, 2010
BCS
Apr 10, 2010
BCS
April 10, 2010
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
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
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
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
(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
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
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
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
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
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 6 7 8 9