Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!npeer02.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!border3.nntp.dca.giganews.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!nntp.earthlink.com!news.earthlink.com.POSTED!not-for-mail
NNTP-Posting-Date: Sat, 20 Oct 2012 14:34:28 -0500
Message-ID: <5082FCC3.28F1@mindspring.com>
Date: Sat, 20 Oct 2012 15:34:27 -0400
From: pete <pfiland@mindspring.com>
Reply-To: pfiland@mindspring.com
Organization: PF
X-Mailer: Mozilla 3.04Gold (WinNT; I)
MIME-Version: 1.0
Newsgroups: comp.programming
Subject: Re: bit trick
References: <9b4b2014-3882-4d9f-bc89-0adcb3ffc882@googlegroups.com> <0.bf807fe1d9a6efd25a6e.20121020014608BST.87txtq0y3z.fsf@bsb.me.uk>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Lines: 76
X-Usenet-Provider: http://www.giganews.com
NNTP-Posting-Host: 4.156.228.155
X-Trace: sv3-wFFR09LISQ7H0tWwXgF1hMba2jqvphgta+MMAqmVMp0iAPJj4jYvVyXFhSRnGSqW4MBFHnZfpdL/yIl!rmM++LOwEZn3e+3sfWMgO3VmfaicH1GbVI1PAfQuuJ3ffsvA+5xQySyc/qgSg6XrumxSq04TULbR!YT6zqH9joy0=
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 2847
X-Received-Bytes: 2988
Xref: csiph.com comp.programming:2372

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