count_number_of_bits.cpp

#include <cstddef>
#include <type_traits>
#include <iostream>


/*
constexpr std::uint8_t g_number_of_bits_uint4[] = {
	0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4
};
*/
constexpr std::uint8_t g_number_of_bits_uint8[] = {
	0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};

template < class UNSIGNED >
constexpr std::size_t do_count_number_of_bits( const UNSIGNED n )
{
	static_assert( std::is_unsigned< UNSIGNED >::value, "An unsigned type is required." );
//	return n > 0 ? g_number_of_bits_uint4[ n &  0xF ] + do_count_number_of_bits( n >> 4 ) : 0;
	return n > 0 ? g_number_of_bits_uint8[ n & 0xFF ] + do_count_number_of_bits( n >> 8 ) : 0;
}

template < class T >
constexpr std::size_t count_number_of_bits( const T n )
{
	return do_count_number_of_bits( static_cast< typename std::make_unsigned< T >::type >( n ) );
}


int main()
{
	std::cout << count_number_of_bits( 0xDEADBEEF ) << std::endl;
	return 0;
}


#if 0	// comments
constexpr を使ってコンパイル時評価を可能にしたビット数え上げ関数。unsigned 型の数値は右シフトを繰り返せばいずれ 0 になることを利用して 8 ビットずつ再帰で数えている。
http://melpon.org/wandbox/permlink/Y0Fl4RnB90owjM4l
#endif	// comments