Re: portable way to get highest bit set?

On Sun, 15 Oct 2023 05:26:44 -0000 (UTC)
Kaz Kylheku <[email protected]> wrote:

> On 2023-10-11, Kaz Kylheku <[email protected]> wrote:
> > 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);
> >   }
> >  
> 
> I guess this went over people's heads?
> 

Not over my head.
My O(log(N)) variant is inspired by your solution.
It is essentially the same like yours, with only difference that I
tried to meet requirement of Tim Rentsch to code it in a manner
independent of number of bits in x.
Sorry for not giving you the credit.

When coded as below, it become more clear that idea is the same like
yours:

T
highest_bit_set( T u ){
  for (int rshift = 1; ((u+1) & u) != 0; rshift += rshift)
    u |= (u >> rshift);
  return u ^ (u>>1);
}