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

int uint32_log2_hardware(uint32_t value) {
	return 31 - __builtin_clz(value);
}

int uint64_log2_hardware(uint64_t value) {
	return 63 - __builtin_clzll(value);
}

int uint32_log2_table(uint32_t value) {
	static const int 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,
	};
	value |= value >> 1;
	value |= value >> 2;
	value |= value >> 4;
	value |= value >> 8;
	value |= value >> 16;
	return table[(value * 0x7C4ACDD) >> 27];
}

int uint64_log2_table(uint64_t value) {
	static const int table[64] = {
		 0, 58,  1, 59, 47, 53,  2, 60, 39, 48, 27, 54, 33, 42,  3, 61,
		51, 37, 40, 49, 18, 28, 20, 55, 30, 34, 11, 43, 14, 22,  4, 62,
		57, 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21, 56,
		45, 25, 31, 35, 16,  9, 12, 44, 24, 15,  8, 23,  7,  6,  5, 63,
	};
	value |= value >> 1;
	value |= value >> 2;
	value |= value >> 4;
	value |= value >> 8;
	value |= value >> 16;
	value |= value >> 32;
	return table[(value * 0x3F6EAF2CD271461) >> 58];
}

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

int uint64_log2_float(uint64_t n) {
	double d = n | 1;
	int e = (*(uint64_t *)&d >> 52 & 0x7FF) - 1023;
	return e - ((n - (1ULL << e)) >> 63);
}

int main(void) {
	for (uint64_t i = 0, j = 1; i < 64; i += 1, j <<= 1) {
		if (uint64_log2_float(j) != i) {
			printf("log2(%lu) != %lu\n", j, i);
		}
		if (i > 0) {
			if (uint64_log2_float(j - 1) != (i - 1)) {
				printf("log2(%lu) != %lu\n", j - 1, i - 1);
			}
			if (uint64_log2_float(j + 1) != i) {
				printf("log2(%lu) != %lu\n", j + 1, i);
			}
		}
	}
	return 0;
}