You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Currently, the bit_ceil function is implemented as:
unsignedintbit_ceil(unsignedint n) {
unsignedint x = 1;
while (x < (unsignedint)(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:
unsignedintbit_ceil(unsignedint n) {
if (n == 0) return1;
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.
The text was updated successfully, but these errors were encountered:
Currently, the
bit_ceil
function is implemented as: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:
This implementation:
It would be great to update the function to this version for better performance.
The text was updated successfully, but these errors were encountered: