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

#define LENGTH(X) (sizeof((X))/sizeof(*(X)))

int log2_tabled_32bit(uint32_t n)
{
	static const int log2_32bit_table[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,
	};
	n |= n >> 1;
	n |= n >> 2;
	n |= n >> 4;
	n |= n >> 8;
	n |= n >> 16;
	return log2_32bit_table[(uint32_t)(n * 0x07C4ACDD) >> 27];
}

int log2_floated_32bit(uint32_t n)
{
	double ff = (double)(n | 1);
	return ((*(1 + (uint32_t*)&ff)) >> 20) - 1023;
}

int log2_branched_32bit(uint32_t n)
{
	int i = -(n == 0);
	#define S(k) if (n >= (UINT32_C(1) << k)) { i += k; n >>= k; }
	S(16);
	S(8);
	S(4);
	S(2);
	S(1);
	#undef S
	return i;
}

int main(void) {
	int (*log2_32bit[])(uint32_t) = {
		log2_tabled_32bit,
		log2_floated_32bit,
		log2_branched_32bit,
	};
	for (int i = 0; i < LENGTH(log2_32bit); ++i) {
		int (*func)(uint32_t) = log2_32bit[i];
		for (uint32_t j = 1, k = 0; k < 32; j <<= 1, k += 1) {
			int output = func(j);
			if (output != k) {
				printf("precise error: func=%d, input=%u, output=%d\n", i, j, output);
			}

			if (j > 5) {
				output = func(j - 1);
				if (output != (k - 1)) {
					printf("approximate error: func=%d, input=%u, output=%d\n", i, j - 1, output);
				}
			}
		}
	}
	return 0;
}