Re: portable way to get highest bit set?

From	Michael S <already5chosen@yahoo.com>
Newsgroups	comp.lang.c, alt.comp.lang.c
Subject	Re: portable way to get highest bit set?
Date	2023-10-15 11:35 +0300
Organization	A noiseless patient Spider
Message-ID	<20231015113545.0000150f@yahoo.com> (permalink)
References	<ug5gvh$1jkar$3@dont-email.me> <20231011143809.748@kylheku.com> <20231014222046.551@kylheku.com>

Cross-posted to 2 groups.

Show all headers | View raw

On Sun, 15 Oct 2023 05:26:44 -0000 (UTC)
Kaz Kylheku <864-117-4973@kylheku.com> wrote:

> On 2023-10-11, Kaz Kylheku <864-117-4973@kylheku.com> 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);
}

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Re: portable way to get highest bit set? Kaz Kylheku <864-117-4973@kylheku.com> - 2023-10-15 05:26 +0000
  Re: portable way to get highest bit set? Michael S <already5chosen@yahoo.com> - 2023-10-15 00:28 -0700
  Re: portable way to get highest bit set? Michael S <already5chosen@yahoo.com> - 2023-10-15 11:35 +0300
    Re: portable way to get highest bit set? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-10-15 02:52 -0700
  Re: portable way to get highest bit set? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-10-15 01:44 -0700

csiph-web