value range propagation for _bitwise_ OR

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

Andrei Alexandrescu wrote:
> On 04/10/2010 01:55 PM, Rainer Deyke wrote:
>> 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).
> 
> It tries to set all bits in which maxa is zero starting and keeps them
> set if the resulting number is less than maxb.
> 
	In other words: maxa | ((1 << highbit (maxb))-1) where:

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

		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/20100410/ae9d6457/attachment.pgp>