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 alt.comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

portable way to get highest bit set? candycanearter07 <no@thanks.net> - 2023-10-11 01:56 -0500
  Re: portable way to get highest bit set? Anton Shepelev <anton.txt@g{oogle}mail.com> - 2023-10-11 10:27 +0300
    Re: portable way to get highest bit set? David Brown <david.brown@hesbynett.no> - 2023-10-11 11:31 +0200
      Re: portable way to get highest bit set? Anton Shepelev <anton.txt@g{oogle}mail.com> - 2023-10-11 12:33 +0300
        Re: portable way to get highest bit set? David Brown <david.brown@hesbynett.no> - 2023-10-11 13:58 +0200
          Re: portable way to get highest bit set? Anton Shepelev <anton.txt@g{oogle}mail.com> - 2023-10-11 15:17 +0300
            Re: portable way to get highest bit set? David Brown <david.brown@hesbynett.no> - 2023-10-11 16:22 +0200
              Re: portable way to get highest bit set? Anton Shepelev <anton.txt@g{oogle}mail.com> - 2023-10-11 18:08 +0300
              Re: portable way to get highest bit set? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-10-11 17:20 +0100
                Re: portable way to get highest bit set? David Brown <david.brown@hesbynett.no> - 2023-10-11 18:28 +0200
    Re: portable way to get highest bit set? candycanearter07 <no@thanks.net> - 2023-10-11 11:19 -0500
      Re: portable way to get highest bit set? David Brown <david.brown@hesbynett.no> - 2023-10-11 18:45 +0200
      Re: portable way to get highest bit set? Ian C <deathstation9000@gmail.com> - 2023-10-11 18:03 +0100
        Re: portable way to get highest bit set? candycanearter07 <no@thanks.net> - 2023-10-11 19:26 -0500
      Re: portable way to get highest bit set? Richard Harnden <richard.nospam@gmail.invalid> - 2023-10-11 19:02 +0100
        Re: portable way to get highest bit set? candycanearter07 <no@thanks.net> - 2023-10-11 19:25 -0500
          Re: portable way to get highest bit set? Bart <bc@freeuk.com> - 2023-10-12 01:35 +0100
            Re: portable way to get highest bit set? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2023-10-11 17:50 -0700
            Re: portable way to get highest bit set? candycanearter07 <no@thanks.net> - 2023-10-11 20:03 -0500
  Re: portable way to get highest bit set? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-10-11 13:56 +0100
  Re: portable way to get highest bit set? Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2023-10-11 14:54 +0000
    Re: portable way to get highest bit set? Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2023-10-12 23:35 +0000
      Re: portable way to get highest bit set? Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2023-10-12 23:47 +0000
  Re: portable way to get highest bit set? Kaz Kylheku <864-117-4973@kylheku.com> - 2023-10-11 17:23 +0000
  Re: portable way to get highest bit set? jak <nospam@please.ty> - 2023-10-11 22:26 +0200
    Re: portable way to get highest bit set? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-10-11 23:58 +0100
      Re: portable way to get highest bit set? jak <nospam@please.ty> - 2023-10-12 09:14 +0200
        Re: portable way to get highest bit set? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-10-12 10:50 +0100
          Re: portable way to get highest bit set? jak <nospam@please.ty> - 2023-10-12 13:35 +0200
            Re: portable way to get highest bit set? Michael S <already5chosen@yahoo.com> - 2023-10-12 15:36 +0300
              Re: portable way to get highest bit set? jak <nospam@please.ty> - 2023-10-12 15:18 +0200
          Re: portable way to get highest bit set? jak <nospam@please.ty> - 2023-10-12 15:09 +0200
            Re: portable way to get highest bit set? jak <nospam@please.ty> - 2023-10-12 23:39 +0200
  Re: portable way to get highest bit set? Blue-Maned_Hawk <bluemanedhawk@invalid.invalid> - 2023-10-11 21:16 +0000
    Re: portable way to get highest bit set? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2023-10-11 14:30 -0700
      Re: portable way to get highest bit set? Blue-Maned_Hawk <bluemanedhawk@invalid.invalid> - 2023-10-12 13:42 +0000
        Re: portable way to get highest bit set? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2023-10-12 14:30 -0700
          Re: portable way to get highest bit set? Anton Shepelev <anton.txt@gmail.moc> - 2023-10-13 00:50 +0300
            Re: portable way to get highest bit set? "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-10-12 16:17 -0700
        Re: portable way to get highest bit set? vallor <vallor@cultnix.org> - 2023-10-13 20:12 +0000
          Re: 🏳️‍🌈portable way to get highest bit set?🏳️‍🌈 🌈💐🌻🌺🌹🌻💐🌷🌺🌈Jen🌈💐🌻🌺🌹🌻💐🌷🌺🌈 Dershmender 💐🌻🌺🌹🌻💐🌷🌺🐶笛🌈💐🌻🌺🌹🌻💐🌷🌺🌈 <root@127.0.0.1> - 2023-10-17 18:28 +0000
  Re: portable way to get highest bit set? Kaz Kylheku <864-117-4973@kylheku.com> - 2023-10-11 21:57 +0000
    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 11:35 +0300
      Re: portable way to get highest bit set? yeti <yeti@tilde.institute> - 2023-10-15 14:26 +0000

csiph-web