#ifndef __BITS_COUNTER__
#define __BITS_COUNTER__

#include <iostream>
#include <iomanip>

using namespace std;

/**
 * ビット列の中にあるビットを数えたり、
 * 一番右から何番目にビットが立っているか調べるクラス 
 * 
 */
class BitsCounter{
  
  private:
    template <class T, int Interval>
    static T make_mask(){
      
      /*
       * このようなマスクを作る
       * @see http://www.nminoru.jp/~nminoru/programming/bitcount.html
       * 
       * 01010101010101010101010101010101  1 32
       * 00110011001100110011001100110011  2 32
       * 00001111000011110000111100001111  4 32
       * 00000000111111110000000011111111  8 32
       * 00000000000000001111111111111111 16 32 
       */
      
      T mask(1);
      for(int i(1); i < Interval; i++){
        mask <<= 1;
        mask |= 0x01;
      }
      /*
      // あるいは以下も有効
      mask <<= Interval;
      mask = (mask & (-mask)) - 1;
      */ 
      
      T res(mask);
      for(unsigned int i(1); i < 8 * sizeof(T) / Interval / 2; i++){
        res <<= Interval;
        res <<= Interval;
        res |= mask;
      }
      return res;
    }
    
    template <class T, int Interval>
    struct count_loop{
      static T run(T bits){
        bits = count_loop<T, (Interval >> 1)>::run(bits);
        T mask(make_mask<T, Interval>());
        // 少なくともビットシフト演算と+演算が定義されている必要あり
        return (bits & mask) + ((bits >> Interval) & mask);
      }
    };
    
    template <class T>
    struct count_loop<T, 1>{
      static T run(T bits){
        T mask(make_mask<T, 1>());
        return (bits & mask) + ((bits >> 1) & mask);
      }
    };
  
  public:
    /**
     * ビットが何個立っているか調べる
     * 
     * @param bits ビット列
     */
    template <class T>
    static T count(T bits) {
      return count_loop<T, sizeof(T) * 8 / 2>::run(bits);
    }
    
    /**
     * 右から何番目にはじめてビットが立っているか調べる
     * 
     * @param bits ビット列
     */
    template <class T>
    static T ntz(T bits){
      return count((T)((~bits) & (bits - 1)));
    }
};

#endif /* __BITS_COUNTER__ */