Ceiling Power-of-Two

Here’s a method find the next power of 2 (in languages where signed numbers are encoded as two’s complement).

long int pow_2_ceil(long int t) {
    if (t == 0) return 1;
    if (t != (t & -t)) {
        do {
            t -= t & -t;
        } while (t != (t & -t));
        t <<= 1;
    }
    return t;
}

Each loop strips the least-significant 1-bit directly; time is O(m) where m = number of 1-bits.

Leave a Reply