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

Groups > comp.programming > #2367 > unrolled thread

bit trick

Back to article view | Back to comp.programming

Contents

  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

#2367 — bit trick

I found this function lying around some code:

    /**
     * Find the smallest power of two >= the input value.
     * (Doesn't work for negative numbers.)
     */
    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?

[toc] | [next] | [standalone]

#2369

"bob" <bob@coolfone.comze.com> wrote in message 
news:9b4b2014-3882-4d9f-bc89-0adcb3ffc882@googlegroups.com...
>I found this function lying around some code:
>
>    /**
>     * Find the smallest power of two >= the input value.
>     * (Doesn't work for negative numbers.)
>     */
>    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?

It works something like this:

private int roundUpPower2(int x) {
   x -= 1;

   for(int i = 1 ; i  < 17;  i <<= 1)
       x |= x >> i;

   return  x + 1;
   }

--

numerist at aquaporin4 dot com

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

#2376

On Friday, October 19, 2012 5:35:03 PM UTC-5, Charles Richmond wrote:
> "bob" <bob@coolfone.comze.com> wrote in message 
> 
> news:9b4b2014-3882-4d9f-bc89-0adcb3ffc882@googlegroups.com...
> 
> >I found this function lying around some code:
> 
> >
> 
> >    /**
> 
> >     * Find the smallest power of two >= the input value.
> 
> >     * (Doesn't work for negative numbers.)
> 
> >     */
> 
> >    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?
> 
> 
> 
> It works something like this:
> 
> 
> 
> private int roundUpPower2(int x) {
> 
>    x -= 1;
> 
> 
> 
>    for(int i = 1 ; i  < 17;  i <<= 1)
> 
>        x |= x >> i;
> 
> 
> 
>    return  x + 1;
> 
>    }
> 
> 
> 
> --
> 
> 
> 
> numerist at aquaporin4 dot com

I see.  Kind of like:

1. Subtract one
2. Take highest one and "smear" it to the right
3.  Add one

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

#2370

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.

-- 
Ben.

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

#2371

On Oct 20, 11:46 am, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
> bob <b...@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.

I think that 0 < x <= 2147483648 is OK for unsigned integers
(32-bit word, of course)..

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

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

#2373

Robin Vowels <robin.vowels@gmail.com> writes:

> On Oct 20, 11:46 am, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
>> bob <b...@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.
>
> I think that 0 < x <= 2147483648 is OK for unsigned integers
> (32-bit word, of course)..

Yes, if the function were re-written to use unsigned ints, but I was
commenting on what was posted.  I'm not sure what language it is (C#
would be my guess) but unless the language is a little odd, it seems to
take a signed int and returns another.

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

-- 
Ben.

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

#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

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

#2387

bob <bob@coolfone.comze.com> wrote:
> I found this function lying around some code:
> 
>     /**
>      * Find the smallest power of two >= the input value.
>      * (Doesn't work for negative numbers.)
>      */
>     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?

Add printing x in binary after each line.

-- 
__Pascal J. Bourguignon__

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

#2388

On 20-Oct-12 0:05 AM, bob wrote:
> I found this function lying around some code:
>
>      /**
>       * Find the smallest power of two >= the input value.
>       * (Doesn't work for negative numbers.)
>       */
>      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?

Every successive OR line ensures the original has at least *that* bit 
set. At the end all bits lower than the very first bit are also set.

[Jw]

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web