Efficient computation of a power of 2

Question

I have a requirement to compute k as the smallest power of 2 which is >= an integer value, n (n is always > 0)

currently I am using:

#define log2(x) log(x)/log(2)
#define round(x) (int)(x+0.5)

k = round(pow(2,(ceil(log2(n)))));

this is in a performance critical function

Is there a more computationally efficient way of calculating k?

If you are using GCC, you can use `1 << CHAR_BIT * sizeof x - __builtin_clz(x)`, provided `x` has type `unsigned int` or, on normal systems, `int`. There is also `__builtin_clzl` for `unsigned long`. Some non-GCC compilers also support this extension. This will be faster than any of the other answers so far on processors that have a “find first bit set” instruction. — Eric Postpischil, Mar 20 '13 at 14:12
note edit from '> an integer value' to '>= an integer value' — bph, Mar 20 '13 at 14:34
There is a “rollback” button in the editing interface. Answers which were changed solely to address the greater-than versus greater-than-or-equal-to issue can be rolled back with this. Answers which had other changes will need manual editing. — Eric Postpischil, Mar 20 '13 at 14:39
Unrelated to an answer, but worth mentioning to anyone who comes upon this and doesn't know better: it's wise to ditch the +0.5 and (int) cast, and instead use the floor() or ceiling() functions in calculations like this. Of course, logarithms are still slow. — DarenW, Mar 28 '13 at 07:32
Possible duplicate of [Rounding up to next power of 2](https://stackoverflow.com/questions/466204/rounding-up-to-next-power-of-2) — phuclv, Nov 02 '17 at 12:34

Randy Howard · Answer 1 · 2013-03-20T14:22:52.753

9

/* returns greatest power of 2 less than or equal to x, branch-free */
/* Source: Hacker's Delight, First Edition. */
int
flp2(int x)
{
    x = x | (x>>1);
    x = x | (x>>2);
    x = x | (x>>4);
    x = x | (x>>8);
    x = x | (x>>16);
    return x - (x>>1);
}

It's entertaining to study it and see how it works. I think the only way for you to know for sure which of the solutions you see will be optimal for your situation is to use all of them in a text fixture and profile it and see which is most efficient for your purpose.

Being branch-free, this one is likely to be quite good performance-wise relative to some others, but you should test it directly to be sure.

If you want the least power of two greater than or equal to X, you can use a slightly different solution:

unsigned
clp2(unsigned 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;
}

edited Mar 20 '13 at 14:22

answered Mar 20 '13 at 14:04

Randy Howard

2,165
16
26

This is nice, since the 'left most' 1 is the answer the goal is to 0 all other bits, this does it nicely. You will need an extra line for 64 bit numbers. – Mar 20 '13 at 14:16
Ah yes, you wanted something else, let me post it. – Mar 20 '13 at 14:19
If you use the `x |= x >>1; ...` form, you can get rid of the parentheses, since the assignment operators have very low precedence. – wildplasser Mar 20 '13 at 14:21
@EricPostpischil -- thank you, I've edited to include a similar routine that finds a power greater than or equal to X, which I think matches the original question better. – Randy Howard Mar 20 '13 at 14:23
@EricPostpischil This answer returns the greatest power of 2 less than or equal to `x`. To change that to the least power of 2 greater than `x`, simply left shift the result by 1. – Sam Harwell Mar 20 '13 at 14:23
@RandyHoward Note that the question asks for greater, not greater than or equal. – Sam Harwell Mar 20 '13 at 14:25
@EricPostpischil The greatest power of 2 less than or equal to 33 is 32. If you left shift that by 1, you get 64, not 128. – Sam Harwell Mar 20 '13 at 14:27
@28OZ28: You are correct, shifting the result of the original code by 1 bit works. – Eric Postpischil Mar 20 '13 at 14:31
1

Yes. Moving the end result up or down by one power of 2, (depending on the actual intent) is pretty straightforward. Hopefully Hiett will be able to use the information for the specific needs of his program. – Randy Howard Mar 20 '13 at 14:33
am i right in thinking these 'hacker delight' solutions are not so portable then, i.e. 32 bit and 64 bit architectures? – bph Mar 20 '13 at 14:50
i guess a check on sizeof(unsigned int) would be required? – bph Mar 20 '13 at 14:55
Don't let the term "hacker" fool you. These are quite useful. They are certainly more portable than compiler specific solutions, or CPU-specific instruction solutions, for example. These bit shifting solutions have to know how large an int or unsigned int is on a given platform for them to work correctly. That's true of anything like this though. You can determine the size of various data types at compile time though, and make adjustments (or use an alternate implementation) for other architectures if you need extreme ranges. – Randy Howard Mar 20 '13 at 14:58
@RandyHoward is an int still 32 bits on a 64 bit machine? additional line would only be needed for a long (64 bits)? wouldn;t the type checking for the input parameter prevent any problems - e.g. if its an int it should be 32 bits? – bph Mar 20 '13 at 21:07
1

@Hiett since right shifting 0 is still 0 you can add the extra line if you need to cater for both 32-bit and 64-bit. the result for 32 bit will still be correct and only waste a few instructions – Rune FS Apr 04 '13 at 15:50

score 2 · Answer 2 · 2013-03-20T14:17:18.640

2

lim = 123;
n = 1;
while( ( n = n << 1 ) <= lim );

Multiply your number by 2 until it's bigger than lim.

Left shift of one multiplies value by 2.

edited Mar 20 '13 at 14:17

answered Mar 20 '13 at 14:04

@EricPostpischil Tnx for noticing, fixed... ( doesn't work for lim = zero but that can be solved using if() ) – Mar 20 '13 at 14:19

Charles Bretana · Answer 3 · 2013-03-20T15:08:52.810

Yes, You can calculate this by simply taking the number in question, and using bit-shifts to determine the power of 2.
Right-shifting takes all the bits in the number and moves them to the right, dropping the far right (least significant) digit. It is equivalent to performing an integer division by 2. Left-shifting a value moves all the bits to the left, dropping the bits that shift off the left end, and adding zeroes to the right end, effectively multiplying the value by 2. So if you count how many times you need to right shift before the number reaches zero, you have calculated the integer portion of the base 2 logarithm. Then use it to create your result by left-shifting the value 1 that many times.

  int CalculateK(int val)
  {
      int cnt = 0;
      while(val > 0)
      {
           cnt++;
           val = val >> 1;
      }
      return 1 << cnt;
  }

EDIT: Alternatively, and a bit simpler: you don't have to calculate the count

  int CalculateK(int val)
  {
      int res = 1;
      while(res <= val) res <<= 1;
      return res ;
  }

Alex Shesterov · Accepted Answer · 2013-03-20T15:14:07.297

2

int calculate_least_covering_power_of_two(int x)
{
  int k = 1;
  while( k < x ) k = k << 1;
  return k;
}

edited Mar 20 '13 at 15:14

answered Mar 20 '13 at 14:17

Alex Shesterov

26,085
12
82
103

1

benchmark this with the branch-free version, I suspect you'll find this isn't the most efficient way to do it. But, it will work. – Randy Howard Mar 20 '13 at 16:27
@RandyHoward i've done that and theres no discernible difference (for my application) so I think I'll stick with this answer as its simpler – bph Mar 20 '13 at 17:40
@Randy: this naive method is very easy to understand and must not be ported to 64- (128-, ...)bit machines. It is also helpful to understand it first, then move on to the branch-free version. **The branch-free version will _surely_ be more efficient for uniformly distributed 32-bit-integers.**, but may be a bit slower for small integers. Also, I've given a "+1" to your post, and it was a nice surprise that my post was accepted ) – Alex Shesterov Mar 20 '13 at 17:42
@alex-shesterov could you explain the problem with porting your function to a 64-bit machine? – bph Mar 20 '13 at 18:32
@Hiett: the function from _this_ answer works for 16, 32, 64, whatever-bit systems without any changes; its complexity (number of iterations) is equal to the number of system-bits (i.e. 16, 32, 64 or whatever) _in worst case_ - i.e. it is linear in the number of bits. The function from RandyHoward's answer needs to be ported to 64-bit-platforms by adding `x |= x>>32`, and its complexity is logarithmic _in worst as well as in best case_. My _estimate_ is that the function by RandyHoward is 15% faster than this one in average on 32-bit systems. – Alex Shesterov Mar 20 '13 at 20:41
@alex-shesterov thanks for clarification - typically my values for x are small, < 50. I think perhaps that is why i see little difference in performance between the 2 functions. Having worked through a few clp2 examples on paper though i can see it is quite elegant – bph Mar 20 '13 at 20:48

Zach · Answer 5 · 2013-03-20T14:20:13.730

1

k = 1 << (int)(ceil(log2(n)));

You can take advantage of the fact that binary digits represent powers of two (1 is 1, 10 is 2, 100 is 4, etc). Shifting 1 left by the exponent of 2 gives you the same value, but it's much faster.

Although if you can somehow avoid the ceil(log2(n)) you will see a much larger performance increase.

edited Mar 20 '13 at 14:20

answered Mar 20 '13 at 14:02

Zach

7,730
3
21
26

This code does not compile because `ceil` has type `double` and cannot be used with `<<`. When a cast to `int` is inserted and `n` is 32, this code produces 32, but the desired result is 64. – Eric Postpischil Mar 20 '13 at 14:18
I added a cast to int to the example. I'm not sure why the desired result for n=32 would be 64... maybe I did not understand the original question. – Zach Mar 20 '13 at 14:20
1

@EricPostpischil, it appears to be asking for the smallest power of 2 greater than or equal to n. 32 is equal to 32. But maybe I am still misunderstanding. Either way, Randy Howard's answer is better. – Zach Mar 20 '13 at 14:24

score 1 · Answer 6 · 2013-03-20T14:28:44.990

1

Source: hackersdelight.org

/* altered to: power of 2 which is greater than an integer value */

unsigned clp2(unsigned x) {
   x = x | (x >> 1);
   x = x | (x >> 2);
   x = x | (x >> 4);
   x = x | (x >> 8);
   x = x | (x >>16);
   return x + 1;
}

Keep in mind you will need to add:

x = x | (x >> 32);

For 64bit numbers.

edited Mar 20 '13 at 14:28

answered Mar 20 '13 at 14:21

Efficient computation of a power of 2

6 Answers6