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

Groups > comp.lang.c > #272361 > unrolled thread

Re: portable way to get highest bit set?

Back to article view | Back to comp.lang.c

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  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
      Re: portable way to get highest bit set? Kaz Kylheku <864-117-4973@kylheku.com> - 2023-10-15 16:59 +0000
    Re: portable way to get highest bit set? yeti <yeti@tilde.institute> - 2023-10-15 14:26 +0000

#272361 — Re: portable way to get highest bit set?

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?

-- 
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

[toc] | [next] | [standalone]

#272579

On Sunday, October 15, 2023 at 8:27:00 AM UTC+3, Kaz Kylheku wrote:
> On 2023-10-11, Kaz Kylheku <864-11...@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? 
> 
> -- 
> TXR Programming Language: http://nongnu.org/txr 
> Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal 
> Mastodon: @Kazi...@mstdn.ca 
> NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

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.

[toc] | [prev] | [next] | [standalone]

#272712

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

[toc] | [prev] | [next] | [standalone]

#273045

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.

[toc] | [prev] | [next] | [standalone]

#272722

Kaz Kylheku <864-117-4973@kylheku.com> writes:

> 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 at all.  It's a well-known technique.  But it doesn't
address the central ask for an approach that works no
matter how wide the value type is.

[toc] | [prev] | [next] | [standalone]

#276931

On 2023-10-15, Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> Kaz Kylheku <864-117-4973@kylheku.com> writes:
>
>> 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 at all.  It's a well-known technique.  But it doesn't
> address the central ask for an approach that works no
> matter how wide the value type is.

Oh, if I had to make it work with the unsigned long type, like the other
solutions, I'd probably just do this:

  unsigned long fill_mask_down(unsigned long x)
  {
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;

  #if UINT_MAX == UINT32_MAX
    x |= x >> 16;
  #elif UINT_MAX == UINT64_MAX
    x |= x >> 16;
    x |= x >> 32;
  #elif UINT_MAX != UINT16_MAX
  #error port me!
  #endif

    return x;
  }

  unsigned long isolate_highest_bit(unsigned long x)
  {
     unsigned long m = fill_mask_down(x);
     return m ^ (m >> 1);
  }


-- 
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

[toc] | [prev] | [next] | [standalone]

#275386

Kaz Kylheku <864-117-4973@kylheku.com> writes:

> I guess this went over people's heads?

Nope.
I've used that before, just not in C yet.

-- 
Fake signature.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web