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

Groups > comp.programming > #2372

Re: bit trick

Show all headers | View raw

Ben Bacarisse wrote:
> 
> bob <bob@coolfone.comze.com> writes:
> 
> > I found this function lying around some code:
> >
> >     /**
> >      * Find the smallest power of two >= the input value.
> >      * (Doesn't work for negative numbers.)
> >      */
> 
> The comment is a little off.  It finds the smallest *integer* power of
> two >= x and it doesn't work for zero or any x > 1073741824.
> 
> >     private int roundUpPower2(int x) {
> >         x = x - 1;
> >         x = x | (x >> 1);
> >         x = x | (x >> 2);
> >         x = x | (x >> 4);
> >         x = x | (x >> 8);
> >         x = x | (x >>16);
> >         return x + 1;
> >     }
> >
> > Can someone explain in layman's terms how that thing works?
> 
> First off, do you know what all the parts do?  | is the logical OR
> operator and >> is right shift.  Given that, why not work through what
> happens for a couple if different values for x?  I think that should
> make it clear.  I'd ignore the subtraction of one at the start and the
> addition of one at the end for the moment.

Here's a version which returns (0),
when (x) is greater than (UINT_MAX / 2 + 1),
but which otherwise 
returns the smallest integer power of two >= x.



/* BEGIN new.c */

#include <stdio.h>

#define LIMIT   50

unsigned 
roundUpPower2(unsigned x) 
{
    unsigned last = x + (x == 0);

    if ((x - 1 & x) != 0) {
        do {
            last = x;
            x &= x - 1;
        } while (x != 0);
        last <<= 1;
    }
    return last;
}

int 
main(void)
{
    unsigned x;
    
    for (x = 0; x != LIMIT; ++x) {
        printf("%2u     %u\n", x, roundUpPower2(x));
    }
    return 0;
}

/* END new.c */


-- 
pete

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

Thread

bit trick bob <bob@coolfone.comze.com> - 2012-10-19 15:05 -0700
  Re: bit trick "Charles Richmond" <numerist@aquaporin4.com> - 2012-10-19 17:34 -0500
    Re: bit trick bob <bob@coolfone.comze.com> - 2012-10-22 12:44 -0700
  Re: bit trick Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-10-20 01:46 +0100
    Re: bit trick Robin Vowels <robin.vowels@gmail.com> - 2012-10-20 08:18 -0700
      Re: bit trick Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-10-20 21:08 +0100
    Re: bit trick pete <pfiland@mindspring.com> - 2012-10-20 15:34 -0400
  Re: bit trick Pascal J. Bourguignon <pjb@informatimago.com> - 2012-10-25 13:04 +0000
  Re: bit trick Jongware <jongware@no-spam.plz> - 2012-10-25 16:28 +0200

csiph-web