Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #238355

Re: portable way to get highest bit set?

Show all headers | View raw

On Thu, 12 Oct 2023 08:05:40 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

> Michael S <already5chosen@yahoo.com> writes:
> 
> > On Thu, 12 Oct 2023 07:01:47 -0700
> > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> >
> >> Anton Shepelev <anton.txt@g{oogle}mail.com> writes:
> >>
> >>> Tim Rentsch:
> >>>
> >>>> But the approach you are using requires knowing the size
> >>>> of the type involved.  The challenge is to write code that
> >>>> works without having to know the size in advance.
> >>>
> >>> Well, I could use macros, or the largest integer type, or:
> >>
> >> Neither necessary nor sufficient.  The code should work for
> >> the type T being __uint128_t, which is larger than uintmax_t.
> >>
> >>> #include <stddef.h>
> >>> #include <limits.h>
> >>>
> >>> [..examine value character-by-character, including
> >>>    determining if little-endian encoding is used..]
> >>
> >> You're making things more complicated than they need to be.
> >> Looking at character values rather than just values of the type
> >> involved is almost guaranteed to have potential representation
> >> issues.  For example, little endian and big endian are not the
> >> only choices possible for endianness.
> >>
> >> Below is a proposed solution that mostly works.  What problems
> >> does it have, and how can they be fixed?  And can we find
> >> something better?
> >>
> >>     /* The type T has been supplied somewhere upstream.  It */
> >>     /* is an unsigned type, and possibly outside the realm  */
> >>     /* of 'integer types' as defined by the C standard, as  */
> >>     /* for example __uint128_t.                             */
> >>
> >>     T
> >>     highest_bit_set( T u ){
> >>         T r = 1;
> >>         while(  u>>1 > r  )  r <<= 1;
> >>         return  r;
> >>     }
> >
> > That code does not look like working.
> 
> Yes, deliberately so.  I didn't want to give working
> code yet, so other people could work on the problem.
> 
> > That is:
> >
> > T
> > highest_bit_set1( T u ){
> >   T r = 0;
> >   while (u > r) r = r*2+1;
> >   return r ^ (r>>1);
> > }
> 
> As expected, this works.  I like the way it naturally
> accommodates a zero input.
> 
> Can you find a different solution that works in
> logarithmic time rather than linear time?

Naturally, I can. But the code is not as easy to comprehend as I would
like. And I am not sure that for typical distributions with prevalence
of small numbers it is faster than above variant.


T
highest_bit_set2( T u ){
  T v;
  for (int rshift = 0; (v = (u >> rshift) >> 1) != 0; rshift = rshift*2+1)
    u |= v;
  return u ^ (u>>1);
}

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

Thread

Re: portable way to get highest bit set? Anton Shepelev <anton.txt@g{oogle}mail.com> - 2023-10-12 11:11 +0300
  Re: portable way to get highest bit set? Michael S <already5chosen@yahoo.com> - 2023-10-12 02:27 -0700
  Re: portable way to get highest bit set? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-10-12 02:41 -0700
    Re: portable way to get highest bit set? Anton Shepelev <anton.txt@g{oogle}mail.com> - 2023-10-12 14:17 +0300
      Re: portable way to get highest bit set? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-10-12 07:01 -0700
        Re: portable way to get highest bit set? scott@slp53.sl.home (Scott Lurndal) - 2023-10-12 14:18 +0000
          Re: portable way to get highest bit set? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-10-12 07:58 -0700
        Re: portable way to get highest bit set? Michael S <already5chosen@yahoo.com> - 2023-10-12 17:30 +0300
          Re: portable way to get highest bit set? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-10-12 08:05 -0700
            Re: portable way to get highest bit set? Michael S <already5chosen@yahoo.com> - 2023-10-12 19:16 +0300
        Re: portable way to get highest bit set? Anton Shepelev <anton.txt@g{oogle}mail.com> - 2023-10-12 18:31 +0300

csiph-web