Monday, November 11, 2013

Calculating the Next Power of Two

If you are on a 32-bit (25) architecture, you need to repeat right_shift-or five times (It turns out that if the val is zero or any value greater than 231, it will return zero). If you are on a 64-bit (26) architecture, you need to repeat right_shift-or six times. [check bit twiddling hacks]
For instance: given an integer 0000 0000 1001 0110 (150) on a 32-bit (25) architecture, the next power of two is  0000 0001 0000 0000 (256). We observe that each time we do right_shift-or, we are doubling the number of consecutive highest 1's:
Original number: 0000 0000 1001 0110
After the first right_shift-or:  0000 0000 1101 1111
...
#include <iostream>
using namespace std;

int next_pow_2(int val){
    --val;
    val |= (val>>1);
    val |= (val>>2);
    val |= (val>>4);
    val |= (val>>8);
    val |= (val>>16);
    ++val;
    return val;
}
int main() {
    // Start typing your code here...
    cout << "Hello world!" << endl;
    for(int i=-10; i<10; i++)
        cout <<i<<"---->"<< next_pow_2(i)<<endl;
    
    return 0;
}

No comments:

Post a Comment