CODEWITHSUNDEEP
cperformancemathoptimization
bph
bph

Reputation: 11268

Efficient computation of a power of 2

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?

Upvotes: 6

Views: 2436

Answers (6)

Alex Shesterov
Alex Shesterov

Reputation: 27535

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

Upvotes: 2

Charles Bretana
Charles Bretana

Reputation: 146541

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

Upvotes: 2

user2180519
user2180519

Reputation:

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.

Upvotes: 1

Randy Howard
Randy Howard

Reputation: 2156

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

Upvotes: 9

Zach
Zach

Reputation: 7940

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.

Upvotes: 1

user1944441
user1944441

Reputation: 

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.

Upvotes: 2

Related Questions