value range propagation for _bitwise_ OR

["Jérôme M. Berger"]

Andrei Alexandrescu wrote:
> On 04/16/2010 11:43 PM, Steven Schveighoffer wrote:
>> Andrei Alexandrescu Wrote:
>>
>>> Looks great, thanks Jerome!
>>>
>>> Now, how about that case in which some or all of the ranges
>>> involved include negative values?
>>
>> I solved already signed values in terms of any valid unsigned
>> solution, see here:
>> http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=108869
>>
>>
>>  The maxor with all the unsigned casts is the call to the unsigned
>> maxor.  Ditto for minor.
>>
>> Also, see my one liner for unsigned maxor:
>>
>> http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=108916
>>
>>
>>  All that is left is to find a quick (possibly one liner?) minor for
>> unsigned.  Maybe there's a quicker signed solution, but the
>> complexity is already O(1) * complexity of unsigned.
>>
>> Also, someone pointed out that Jerome's highbit is equivalent to the
>> x86 bsr instruction (std.instrinsic.bsr).
> 
> That looks good. I'm thinking of expressing minOR for unsigned in terms
> of maxOR for one's complement.
> 
> We have min_a <= a <= max_a. This implies ~max_a <= ~a <= ~min_a.
> 
> Wavehanding follows.
> 
> We're looking for the numbers a and b that minimize the number of bits
> in a|b. Those choices for a and b would then maximize the number of bits
> in ~a|~b. So:
> 
> minOR == maxOR(~max_a, ~min_a, ~max_b, ~min_b)
> 
> Works?
> 
	Assuming you meant:

minOR == ~maxOR(~max_a, ~min_a, ~max_b, ~min_b)

	Then that was my first idea too but it is *very* conservative. In
my tests it only gave the best result for 0.1% of the time. So we'll
have to do it the hard way:

==============================8<------------------------------
uint32_t minOr (uint32_t minA, uint32_t minB,
                uint32_t maxA, uint32_t maxB)
{
   assert (minA <= maxA);
   assert (minB <= maxB);

   if (minA == 0) return minB;
   if (minB == 0) return minA;

   uint32_t a = maxA ^ minA;
   if (a != 0) {
      a = ((1 << (highbit (a)+1)) - 1) & ~minA & minB;
      if (a != 0)
         a = (1 << highbit (a)) - 1;
   }
   a = minA & ~a;

   uint32_t b = maxB ^ minB;
   if (b != 0) {
      b = ((1 << (highbit (b)+1)) - 1) & ~minB & minA;
      if (b != 0)
         b = (1 << highbit (b)) - 1;
   }
   b = minB & ~b;

   return min (minA|b, a|minB);
}
------------------------------>8==============================

	The one-liner is left as an exercise to the readers (since it has
the same performance anyway).

		Jerome
-- 
mailto:jeberger at free.fr
http://jeberger.free.fr
Jabber: jeberger at jabber.fr

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: OpenPGP digital signature
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20100417/fac6517e/attachment.pgp>