Assume a 32-bit unsigned integer (answers generalizable to any size are of course better).
This integer can be assumed to be a power of 2, so only one bit is set.
I want to set all bits in the integer, except those lower than the set bit. So (using 8-bit integers for brevity) 00001000
would become 11111000
.
This could of course be accomplished by finding the one set bit and then iterating through the higher bits, setting them also. Assuming highest_set
return the position of the highest set bit:
uint32_t f(uint32_t x)
{
int n = highest_set(x);
for (int i = 31; i != n; --i) {
x |= 1 << i;
}
return x;
}
The runtime of f
does however depend on the value of x
, and I feel that there is a cleverer way of doing this.
Conceptually, an easy thing to do would be to take x - 1
and then XOR it with 0xffffffff
. Writing it as ~(x - 1)
as harold did in the comments below will handle different sized integers without having to change what you're XORing with.