libjmmcg  build_2783
A C++ library containing an eclectic mix of useful, advanced components.
jmmcg::dyn::lookup::count_setbits< NumBits > Struct Template Reference

Count the number of set bits in the input number. More...

#include <count_setbits.hpp>

Public Types

typedef unsigned long long element_type
 

Public Member Functions

 BOOST_STATIC_ASSERT ((sizeof(element_type) *8)<=std::numeric_limits< typename cache_t::range_type >::max())
 

Static Public Member Functions

static __attribute__ ((pure)) element_type result(element_type num) noexcept(true)
 
constexpr static float efficiency () noexcept(true)
 

Detailed Description

template<u_int8_t NumBits>
struct jmmcg::dyn::lookup::count_setbits< NumBits >

Count the number of set bits in the input number.

Because the operator>>() is poorly defined this only works for unsigned types. This is because there may be a sign bit or two's complement representation of the negative number. Then shifting might cause the sign bit to be shifted into the number itself, possibly causing an infinite loop.

Complexity: run-time: O(n/s) where n is at most the number of bits used to represent the input type, and s is the number of bits used to represent the size of the cache. Space: O(s)

Definition at line 240 of file count_setbits.hpp.

Member Typedef Documentation

◆ element_type

template<u_int8_t NumBits>
typedef unsigned long long jmmcg::dyn::lookup::count_setbits< NumBits >::element_type

Definition at line 248 of file count_setbits.hpp.

Member Function Documentation

◆ __attribute__()

template<u_int8_t NumBits>
static jmmcg::dyn::lookup::count_setbits< NumBits >::__attribute__ ( (pure)  )
inlinestaticnoexcept

A loop-based implementation, using a cache. Note that this implementation assumes that the % and / operations when using divisors that are powers of 2 is fast either because:

  • The compiler is a good optimising compiler and can covert the % & / to shift operations or,
  • the core has either at least one pipelined execution unit that can perform % and / or two execution units that can each perform either % or /.

Definition at line 257 of file count_setbits.hpp.

◆ BOOST_STATIC_ASSERT()

template<u_int8_t NumBits>
jmmcg::dyn::lookup::count_setbits< NumBits >::BOOST_STATIC_ASSERT ( (sizeof(element_type) *8)<=std::numeric_limits< typename cache_t::range_type >::max()  )

◆ efficiency()

template<u_int8_t NumBits>
constexpr static float jmmcg::dyn::lookup::count_setbits< NumBits >::efficiency ( )
inlinestaticconstexprnoexcept

Definition at line 265 of file count_setbits.hpp.


The documentation for this struct was generated from the following file: