Find least significant bit set in 0(1)

lsb.cc

#include <cstdint>

namespace mybits{

constexpr uint8_t log2(uint64_t n){
	constexpr uint8_t tab64[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
	};

	n |= n >> 1;
	n |= n >> 2;
	n |= n >> 4;
	n |= n >> 8;
	n |= n >> 16;
	n |= n >> 32;

	auto const pos = (n  * 0x03F6EAF2CD271461) >> 58;

	return tab64[pos];
}


constexpr uint8_t log2(uint32_t n){
	constexpr uint8_t tab32[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;

	auto const pos = (n * 0x07C4ACDD ) >> 27;

	return tab32[pos];
}

#if 0
	uint8_t log2_not_optimal(uint64_t value){
		constexpr uint8_t tab64x[64] = {
			63,  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
		};

		value |= value >> 1;
		value |= value >> 2;
		value |= value >> 4;
		value |= value >> 8;
		value |= value >> 16;
		value |= value >> 32;

		auto const pos = uint64_t( (value - (value >> 1)) * 0x07EDD5E59A4E28C2 ) >> 58;

		return tab64[pos];
	}
#endif

constexpr uint64_t lsb(uint64_t const x){
	return x & ( ~x + 1 );
}

} // namespace mybits

#include <iostream>
#include <iomanip>


template<typename T>
void p(T const x){
	using namespace mybits;

	std::cout
		<< std::setw(20)	<< x
		<< ' '
		<< std::setw(20)	<< lsb(x)
		<< ' '
		<< std::setw(20)	<< uint16_t{ log2(lsb(x)) }
		<< '\n'
	;
}

int main(){
	for(uint32_t i = 0; i <= 0x100; ++i)
		p(i);

	p<uint64_t>(0x8000000000000000);
	p<uint32_t>(0x80000000);
}