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

Groups > comp.lang.c > #273045

Re: portable way to get highest bit set?

Show key headers only | View raw

Michael S <already5chosen@yahoo.com> writes:

> 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.

Two short comments on the above.  One, the requirement to make
the algorithm size independent came from the OP, not me;  I just
expressed that in a way that is apparent in the C code.  Two, I
had assumed that most people would already be familiar with the
expanding-shift-and-oring technique;  it was one of several I
had already coded before the humorous post with my "favorite"
version.

> 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);
> }

I expect to have comments on this and your earlier posted
version soon.

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

Thread

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

csiph-web