What does this bit-manipulating function do?

Question

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

It works pretty fast. – Sergio Tulentsev Dec 26 ‘11 at 15:46 — Sergio Tulentsev, Dec 26 ‘11 at 15:46
i know it works well, but i want to know which algorithm it use. – guoxx Dec 26 ‘11 at 15:51 — guoxx, Dec 26 ‘11 at 15:51

leonbloy · Answer 1 · 2011-12-26 16:54:40Z

The OR and SHIFT statements fills with ones all bits of x to the right of most significant bit (up to 32 bits). Together with the pre-decrement and post-increment statements, this computes (as the function name suggets) the next power-of-two number, equal or greater than the given number (if x is greater than 0 and less than 2^32)

The pre-decrement ensures inputs of zero and powers of two are mapped onto themselves. – njuffa Dec 26 ‘11 at 17:41 — njuffa, Dec 26 ‘11 at 17:41

L?u V?nh Phúc · Answer 2 · 2013-08-01 08:08:44Z

This function rounds x up to the next highest power of 2. It‘s exactly the code in here

unsigned int v; // compute the next highest power of 2 of 32-bit v

v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;

What does this bit-manipulating function do?

2 Answers