What's the best way to write a function with the following prototype:

unsigned power_of_two(const unsigned &max);

where the function should return the largest power of 2 that is < max.

You can of course do it the old-fashioned way:

Code:

unsigned power_of_two(const unsigned &max) {
unsigned result = 1;
while (result < max) {
result *= 2;
}
result /= 2;
return result;
}

Or you can do this:

Code:

unsigned power_of_two(const unsigned &max) {
unsigned result = max;
--result;
result |= result >> 1;
result |= result >> 2;
result |= result >> 4;
result |= result >> 8;
result |= result >> 16; // now all bits are set up to the most significant bit in _size
++result; // result is now the nearest power of 2 greater than or equal to _size
result = result >> 1; // result < _size
return result;

Or, in the same spirit as the second, and presumably slightly slower but more straightforward:

Code:

unsigned power_of_two(const unsigned &max) {
unsigned result = 1;
while (result < max) {
result = result << 1;
}
result = result >> 1;
return result;
}