# power_of_two function

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 09-21-2010
Aisthesis
power_of_two function
What's the best way to write a function with the following prototype:

unsigned power_of_two(const unsigned &max);

where the function should return the largest power of 2 that is < max.

You can of course do it the old-fashioned way:
Code:

```unsigned power_of_two(const unsigned &max) {   unsigned result = 1;   while (result < max) {     result *= 2;   }   result /= 2;   return result; }```
Or you can do this:
Code:

```unsigned power_of_two(const unsigned &max) {               unsigned result = max;         --result;         result |= result >> 1;         result |= result >> 2;         result |= result >> 4;         result |= result >> 8;         result |= result >> 16;        // now all bits are set up to the most significant bit in _size         ++result;                // result is now the nearest power of 2 greater than or equal to _size         result = result >> 1; // result < _size         return result;```
Or, in the same spirit as the second, and presumably slightly slower but more straightforward:

Code:

```unsigned power_of_two(const unsigned &max) {   unsigned result = 1;   while (result < max) {     result = result << 1;   }   result = result >> 1;   return result; }```
• 09-21-2010
Elysia
I would simply use log2 to get the power of 2 to get max. Then take the integer and raise 2 to that power.
Otherwise, I'd prefer the first.
• 09-22-2010
iMalc
My first step would be to drop the const reference and just pass by value.
Next I would not name the parameter 'max'.

Then, much like your second code snippet, I would lose the extra variable and just write it like this:
Code:

```unsigned int power_of_two(unsigned int val) {     --val;     val |= val >> 16;     val |= val >>  8;     val |= val >>  4;     val |= val >>  2;     val |= val >>  1;     return val ^ (val >> 1); }```
Or if I wasn't already familiar with this technique, I would look something up from this site.

I also question whether you are after a power of two strictly less than the input, or whether you actually want a power of two that is less than or equal. E.g. For most purposes I would expect that passing in 16 would return 16. In which case you can lose the --val; part. This would also allow it to return a sensible value when passed in zero. Otherwise I'd feel it necessary to throw an exception or just assert, when the input parameter is zero.

Note also that all of the methods you posted fail when given input greater than or equal to 2^31, the first and third one going into an infinite loop, with the second one simply giving the wrong answer. As a minimum I would expect an author of such code to document this limitation.
This issue is fixed with the code I just posted, as it also would be with Elysia's suggestion.
• 09-22-2010
kmdv
One silly note - this code is non portable.
I would probably use the first (but modified) version.

Quote:

Or, in the same spirit as the second, and presumably slightly slower but more straightforward:
Code:

```unsigned power_of_two(const unsigned &max) {   unsigned result = 1;   while (result < max) {     result = result << 1;   }   result = result >> 1;   return result; }```

This is the same as the first, isn't it?
• 09-22-2010
Aisthesis
it is the same result as the first for sure, but i like it better.

as to dropping const and &: if you drop the "const" will it work if you pass it a constant? if so, then i agree with you that it's ridiculous to add the extra baggage when one is copying it anyway.

then on the input > 2^31: you're right, but an easy fix is to make it:
Code:

`while (result && result < max) { ... }`
i'll have to think a little about your technique for modifying 2).
• 09-22-2010
dwks
Quote:

Originally Posted by Aisthesis
as to dropping const and &: if you drop the "const" will it work if you pass it a constant? if so, then i agree with you that it's ridiculous to add the extra baggage when one is copying it anyway.

Yes, it will work. A function like this
Code:

`void func(unsigned x);`
can be passed an unsigned int or a const unsigned int, because a copy of the number will be made. It's quite customary to pass small data structures and especially primitives by value unless there's a reason to do something else.

(For more complicated data structures, it might be expensive to copy the object, or the object might not even have a copy constructor, in which case you start seeing constant references being used.)
• 09-22-2010
EVOEx
Quote:

Originally Posted by dwks
Yes, it will work. A function like this
Code:

`void func(unsigned x);`
can be passed an unsigned int or a const unsigned int, because a copy of the number will be made. It's quite customary to pass small data structures and especially primitives by value unless there's a reason to do something else.

(For more complicated data structures, it might be expensive to copy the object, or the object might not even have a copy constructor, in which case you start seeing constant references being used.)

I actually consider it fairly good practice to pass things as const reference, with the exception of built-in types... It won't ever hurt...
• 09-22-2010
dwks
Sure. With the exception of built-in types. :) Although . . . I sometimes pass small things like Points by value, but not much else.

And it can hurt, if you try to generalize the practice outside of parameters. ;)
Code:

`const Object &getAnObject() { return Object(); }  // oops`
• 09-22-2010
iMalc
Quote:

Originally Posted by Aisthesis
it is the same result as the first for sure, but i like it better.

as to dropping const and &: if you drop the "const" will it work if you pass it a constant? if so, then i agree with you that it's ridiculous to add the extra baggage when one is copying it anyway.

I think this has been answered now.

Quote:

Originally Posted by Aisthesis
then on the input > 2^31: you're right, but an easy fix is to make it:
Code:

`while (result && result < max) { ... }`
).

That would do it. I was thinking of putting a specific check for the input being >= 2^31 at the start of the function so as to not impact the performance of the loop.
Quote:

Originally Posted by Aisthesis
i'll have to think a little about your technique for modifying 2).

How it works:
After all the |= lines, val is made up of some number of consecutive zeros bits starting from the high end, followed by some number of ones.
E.g. 31 =
0x00, 0x00, 0x00, 00011111
Right shifted, this gives us:
0x00, 0x00, 0x00, 00001111
XOR them and you get:
0x00, 0x00, 0x00, 00010000
Using subtraction would work just as well, but in such cases I always use the logically simpler operation, such that when the technique is generalised to bigint class type etc, it is faster.
• 09-22-2010
Aisthesis
i'm not terribly worried about the strictly less than or less than in this case.

my only problem with version 2) or your improvement is that you're locked into a 32-bit representation of int, which it should be, but it's kind of nice to have it apply more generally just in case.

i hope the falling takes care of all the pitfalls discussed and still does things pretty fast:

Code:

```unsigned power_of_two(unsigned const &max) {  // since we don't need a copy   result = 1;   while (result && result < max) {     result <<= 1;   }   // only remaining problem is that result could be 0 if max has its most significant bit set   --result;   result >>= 1;   ++result; }```
for numbers ~< 2^12 this should even be faster than the 16, 8, 4, ... method (since the loop stops quickly, although slower for bit integers. i also feel more comfortable with it doesn't depend on integers being 32 bits long.

should work every time, too, i think--or does this one still break down in some cases?
• 09-22-2010
brewbuck
Why not just shift the value left until a 1 bit appears in the MSB?

Code:

```unsigned int power_of_two(unsigned int max) {     const unsigned int mask = ~(~0U>>1);     unsigned int result = mask;     assert(max != 0);     while(!(max & mask))     {         result >>= 1;         max <<= 1;     }     return result; }```
No assumptions made about how many bits in an unsigned int, no weird corner cases.
• 09-22-2010
Aisthesis
beautiful idea! can't we simplify further like this:

Code:

```unsigned power_of_two(const unsigned &max) {   assert(max != 0);  // also a nice addition   unsigned result = ~(~0U >> 1);   while(!(result & max)) result >>= 1;   return result; }```
• 09-22-2010
brewbuck
Quote:

Originally Posted by Aisthesis
beautiful idea! can't we simplify further like this:

Code:

```unsigned power_of_two(const unsigned &max) {   assert(max != 0);  // also a nice addition   unsigned result = ~(~0U >> 1);   while(!(result & max)) result >>= 1;   return result; }```

Yes, good spotting.
• 09-22-2010
CornedBee
Haven't validated the theory behind this, but it should work:
Code:

```unsigned power_of_two(unsigned i) {   while(i & (i-1))     i &= i-1;   return i; }```
I am pretty sure that (i & (i-1)) always eliminates the least significant set bit of the number. Also, if the compiler is smart, this should compile down to something like:
Code:

```; assume ebx holds i repeat:   mov eax, ebx   dec eax   and ebx, eax   jnz repeat   inc eax   ret```
Of course, if we're at that low level, it's easier to do this:
Code:

`return 1 << (sizeof(unsigned)*CHAR_BIT - 1) - clz(i)`
where clz is the count leading zeros instruction many architectures have. x86 has BSF, bit scan forward. Its performance over time has varied greatly in various CPUs, but as of the Core2, it's fast again, and will easily beat every loop.
• 09-23-2010
iMalc
Quote:

Originally Posted by Aisthesis
my only problem with version 2) or your improvement is that you're locked into a 32-bit representation of int, which it should be, but it's kind of nice to have it apply more generally just in case.

Yes absolutely, that is the caveat.

Quote:

Originally Posted by Aisthesis
for numbers ~< 2^12 this should even be faster than the 16, 8, 4, ... method (since the loop stops quickly, although slower for bit integers. i also feel more comfortable with it doesn't depend on integers being 32 bits long.

It might be less operations, but it has conditional branches. If one those are mispredicted, which is highly likely, then it probably wont end up faster.
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last