Re: portable way to get highest bit set?

On 2023-10-11, candycanearter07 <[email protected]> wrote:
> Hi,
>
> What is the best/most portable way to get the highest bit set?
>
> ie. 011010001
> to  010000000

I just noticed you really want the *mask* of the highest bit set,
not its position.

That's pretty easy to do in a portable way.

First we calculate this fully saturated mask:

      011111111

then, we just right shift that to produce this mask:


      001111111

and XOR them together to get

      010000000

Now how do we get that first mask? Like ethis:

Start with x:

      011010001     x

OR it with x >> 1:

   |  001101000     x >> 1
   ------------
   =  011111001

Take that to be the new x. OR it with x >> 2

      011111001
   |  000111110
   ------------
   =  011111111

And here we are done; but we continue to x >> 4 and x >> 8.

E.g. 32 bit code:

   uint32_t fill_mask_down(uint32_t x)
   {
     x |= x >> 1;    // e.g.   1000...0000 -> 1100...0000
     x |= x >> 2;    // e.g.   1100...0000 -> 1111...0000
     x |= x >> 4;    // e.g.   11110000...  -> 11111111...
     x |= x >> 8;
     x |= x >> 16;

     return x;
   }

Thus:

  uint32_t isolate_highest_bit(uint32_t x)
  {
     uint32_t m = fill_mask_down(x);
     return m ^ (m >> 1);
  }

Note that this has no branches whatsoever. There are data hazards
because we are updating an accumulator in place; that's likely
going to cost some pipeline-level parallelism.

Note that the numbeer of |= steps in fill_mask_down is the log2
of the number of bits. The 64 bit code just ads x |= x >> 32.

-- 
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @[email protected]
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.