Geek Answers Handbook

Efficient power calculation 2

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

I am currently using:

 #define log2(x) log(x)/log(2) #define round(x) (int)(x+0.5) k = round(pow(2,(ceil(log2(n)))));

this is a critical performance feature

Is there a more computationally efficient way to calculate k ?

+6
source share
6 answers
 int calculate_least_covering_power_of_two(int x) { int k = 1; while( k < x ) k = k << 1; return k; }
+2
source 
 /* returns greatest power of 2 less than or equal to x, branch-free */ /* Source: Hacker 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 is interesting to study and see how it works. I think that the only way 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 tool and profile it and see what is most effective for your purpose.

Industry-independent, this one is likely to be good enough for some others, but you should check 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; }
+9
source 
 lim = 123; n = 1; while( ( n = n << 1 ) <= lim );

Multiply your number by 2 until it becomes more than lim.

The left shift of one multiplies the value by 2.

+2
source

Yes, you can calculate this by simply taking the number in question and using bit shifts to determine power 2.
The right offset takes all the bits in the number and moves them to the right, discarding the rightmost (least significant) digit. This is equivalent to doing an integer division by 2. Left shift of the value moves all the bits to the left, discarding bits that are shifted from the left end, and adds zeros to the right end, effectively multiplying the value by 2. Therefore, if you count how many times you need to shift to the right before the number reaches zero, you calculated the integer part of the logarithm of base 2. Then use it to create the result by shifting the value 1 so many times.

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

EDIT: Alternatively, and a little easier: you do not need to calculate the counter

  int CalculateK(int val) { int res = 1; while(res <= val) res <<= 1; return res ; }
+2
source 
 k = 1 << (int)(ceil(log2(n)));

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

Although, if you can somehow avoid ceil (log2 (n)), you will see a much greater increase in performance.

+1
source

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 that you need to add:

 x = x | (x >> 32);

For 64-bit numbers.

+1
source

More articles:


All Articles