#include <stdio.h>
#include <stdint.h>
#include <assert.h>

unsigned int npot2(unsigned int size)
{
	if (size == 0) return 0;
	unsigned int npot = 1;

	while ((size >>= 1) > 0) {
		npot <<= 1;
	}
	return npot;
}

unsigned int ceil_pot(unsigned int size)
{

	unsigned v = size;

	v--;
	v |= v >> 1;
	v |= v >> 2;
	v |= v >> 4;
	v |= v >> 8;
	v |= v >> 16;
	v++;

	return v;
}

uint32_t floor_pot(uint32_t n)
{
	uint32_t v = n;

	static const int MultiplyDeBruijnBitPosition[32] =
	{
		0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
		8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
	};

	if (v == 0)
		return 0;

	v |= v >> 1; // first round down to one less than a power of 2
	v |= v >> 2;
	v |= v >> 4;
	v |= v >> 8;
	v |= v >> 16;

	return (uint32_t)1 << (MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27]);
}

int main(void)
{
	int i;

	for (i = 0; i < 65536; i++) {
		if (floor_pot(i) != npot2(i))
			printf("n == %d != %d\n", i, floor_pot(i));
	}

	return 0;
}