Re: value range propagation for _bitwise_ OR

[Jérôme M. Berger]

Ali Çehreli wrote:
> � wrote:
> 
>> The idea is to build a value that is  between minA and maxA and will
>> set as many bits as possible when or'ed with maxB:
> 
> The assumption that maxB would be the value that produces the maximum
> a|b is not correct. A lower valued b may fill more gaps in the bit
> representation of what is calculated from min_a and max_a.
> 
> Your function failed for me with the following values:
> 
>            min_a 00000000000000000000000011001000 000000c8        200
>            max_a 00000000000000000000001100001111 0000030f        783
>            min_b 00000000000000000000000001000101 00000045         69
>            max_b 00000000000000000000001001100001 00000261        609
>       calculated 00000000000000000000001001100101 00000265        613
> WRONG! empirical 00000000000000000000001111111111 000003ff       1023
>        emp_max_a 00000000000000000000000110011110 0000019e        414
>        emp_max_b 00000000000000000000001001100001 00000261        609
> 
> Please see my test code elsewhere in the same thread: :)
> 
> http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=108851
> 
        The "calculated" value above obviously was not computed with my
function! Since the return value from my function includes maxA and
maxB, at least all bits that are set in either of those should be
set in the output.

        I've run my code with those input and the result is 3ff as
expected... (See attached source file).

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

#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

int highbit (uint32_t n)
{
   assert (n != 0);

   int  result = 0;
   if (n & 0xFFFF0000) {
      result  += 16;
      n      >>= 16;
   }
   if (n & 0xFF00) {
      result  += 8;
      n      >>= 8;
   }
   if (n & 0xF0) {
      result  += 4;
      n      >>= 4;
   }
   if (n & 0xC) {
      result  += 2;
      n      >>= 2;
   }
   if (n & 0x2) {
      result  += 1;
      n      >>= 1;
   }
   return result;
}

inline uint32_t min (uint32_t a, uint32_t b)
{
   return (a<b) ? a : b;
}

uint32_t maxOr (uint32_t    minA, uint32_t minB,
                uint32_t    maxA, uint32_t maxB)
{
   assert (minA <= maxA);
   assert (minB <= maxB);

   if (maxA == 0) return maxB;
   if (maxB == 0) return maxA;

   uint32_t a = maxA ^ minA;
   if (a != 0)
      a = ((1 << highbit (a)) - 1);

   uint32_t b = maxB ^ minB;
   if (b != 0)
      b = ((1 << highbit (b)) - 1);

   uint32_t  t = maxA & maxB;
   if (t != 0)
      t = ((1 << highbit (t)) - 1);

   return min (maxA|maxB|a|b, maxA|maxB|t);
}

int main (int, char**)
{
   uint32_t minA = 200;
   uint32_t maxA = 783;
   uint32_t minB = 69;
   uint32_t maxB = 609;
   printf ("minA=%x\n"
           "maxA=%x\n"
           "minB=%x\n"
           "maxB=%x\n"
           "maxOr=%x\n",
           minA, maxA, minB, maxB,
           maxOr (minA, minB, maxA, maxB));
   return 0;
}

signature.asc
Description: OpenPGP digital signature