ac-library icon indicating copy to clipboard operation
ac-library copied to clipboard

Optimize bit_ceil to use constant-time bitwise implementation

Open avighnac opened this issue 8 months ago • 0 comments

Currently, the bit_ceil function is implemented as:

unsigned int bit_ceil(unsigned int n) {
    unsigned int x = 1;
    while (x < (unsigned int)(n)) x *= 2;
    return x;
}

This works correctly, but it uses a loop and can take up to log(n) iterations. It can be rewritten in constant time using standard bit-twiddling techniques, which are generally more efficient and can compile down to ~5 instructions.

Suggested optimized implementation:

unsigned int bit_ceil(unsigned int n) {
    if (n == 0) return 1;
    n--;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return n + 1;
}

This implementation:

  • Avoids the loop entirely
  • Works in constant time for all 32-bit unsigned integers

It would be great to update the function to this version for better performance.

avighnac avatar May 15 '25 00:05 avighnac