Thread: power_of_two function

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;
}