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

Groups > comp.lang.c > #237875

Re: portable way to get highest bit set?

Show all headers | View raw

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?

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