#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)));
    }
};

int main(){
  
  cout << "sizeof => " 
      << "int:" << sizeof(int) << ", " 
      << "short:" << sizeof(short) << ", "
      << "char:" << sizeof(char) << endl;
  for(int i(0); i < 0x100; i++){
    cout << i << " => " 
        << BitsCounter::ntz(i) << ", " 
        << (int)BitsCounter::ntz((short)i) << ", "
        << (int)BitsCounter::ntz((char)i) << endl;
  }
  
  return 0;
}

sizeof => int:4, short:2, char:1
0 => 32, 16, 8
1 => 0, 0, 0
2 => 1, 1, 1
3 => 0, 0, 0
4 => 2, 2, 2
5 => 0, 0, 0
6 => 1, 1, 1
7 => 0, 0, 0
8 => 3, 3, 3
9 => 0, 0, 0
10 => 1, 1, 1
11 => 0, 0, 0
12 => 2, 2, 2
13 => 0, 0, 0
14 => 1, 1, 1
15 => 0, 0, 0
16 => 4, 4, 4
17 => 0, 0, 0
18 => 1, 1, 1
19 => 0, 0, 0
20 => 2, 2, 2
21 => 0, 0, 0
22 => 1, 1, 1
23 => 0, 0, 0
24 => 3, 3, 3
25 => 0, 0, 0
26 => 1, 1, 1
27 => 0, 0, 0
28 => 2, 2, 2
29 => 0, 0, 0
30 => 1, 1, 1
31 => 0, 0, 0
32 => 5, 5, 5
33 => 0, 0, 0
34 => 1, 1, 1
35 => 0, 0, 0
36 => 2, 2, 2
37 => 0, 0, 0
38 => 1, 1, 1
39 => 0, 0, 0
40 => 3, 3, 3
41 => 0, 0, 0
42 => 1, 1, 1
43 => 0, 0, 0
44 => 2, 2, 2
45 => 0, 0, 0
46 => 1, 1, 1
47 => 0, 0, 0
48 => 4, 4, 4
49 => 0, 0, 0
50 => 1, 1, 1
51 => 0, 0, 0
52 => 2, 2, 2
53 => 0, 0, 0
54 => 1, 1, 1
55 => 0, 0, 0
56 => 3, 3, 3
57 => 0, 0, 0
58 => 1, 1, 1
59 => 0, 0, 0
60 => 2, 2, 2
61 => 0, 0, 0
62 => 1, 1, 1
63 => 0, 0, 0
64 => 6, 6, 6
65 => 0, 0, 0
66 => 1, 1, 1
67 => 0, 0, 0
68 => 2, 2, 2
69 => 0, 0, 0
70 => 1, 1, 1
71 => 0, 0, 0
72 => 3, 3, 3
73 => 0, 0, 0
74 => 1, 1, 1
75 => 0, 0, 0
76 => 2, 2, 2
77 => 0, 0, 0
78 => 1, 1, 1
79 => 0, 0, 0
80 => 4, 4, 4
81 => 0, 0, 0
82 => 1, 1, 1
83 => 0, 0, 0
84 => 2, 2, 2
85 => 0, 0, 0
86 => 1, 1, 1
87 => 0, 0, 0
88 => 3, 3, 3
89 => 0, 0, 0
90 => 1, 1, 1
91 => 0, 0, 0
92 => 2, 2, 2
93 => 0, 0, 0
94 => 1, 1, 1
95 => 0, 0, 0
96 => 5, 5, 5
97 => 0, 0, 0
98 => 1, 1, 1
99 => 0, 0, 0
100 => 2, 2, 2
101 => 0, 0, 0
102 => 1, 1, 1
103 => 0, 0, 0
104 => 3, 3, 3
105 => 0, 0, 0
106 => 1, 1, 1
107 => 0, 0, 0
108 => 2, 2, 2
109 => 0, 0, 0
110 => 1, 1, 1
111 => 0, 0, 0
112 => 4, 4, 4
113 => 0, 0, 0
114 => 1, 1, 1
115 => 0, 0, 0
116 => 2, 2, 2
117 => 0, 0, 0
118 => 1, 1, 1
119 => 0, 0, 0
120 => 3, 3, 3
121 => 0, 0, 0
122 => 1, 1, 1
123 => 0, 0, 0
124 => 2, 2, 2
125 => 0, 0, 0
126 => 1, 1, 1
127 => 0, 0, 0
128 => 7, 7, 7
129 => 0, 0, 0
130 => 1, 1, 1
131 => 0, 0, 0
132 => 2, 2, 2
133 => 0, 0, 0
134 => 1, 1, 1
135 => 0, 0, 0
136 => 3, 3, 3
137 => 0, 0, 0
138 => 1, 1, 1
139 => 0, 0, 0
140 => 2, 2, 2
141 => 0, 0, 0
142 => 1, 1, 1
143 => 0, 0, 0
144 => 4, 4, 4
145 => 0, 0, 0
146 => 1, 1, 1
147 => 0, 0, 0
148 => 2, 2, 2
149 => 0, 0, 0
150 => 1, 1, 1
151 => 0, 0, 0
152 => 3, 3, 3
153 => 0, 0, 0
154 => 1, 1, 1
155 => 0, 0, 0
156 => 2, 2, 2
157 => 0, 0, 0
158 => 1, 1, 1
159 => 0, 0, 0
160 => 5, 5, 5
161 => 0, 0, 0
162 => 1, 1, 1
163 => 0, 0, 0
164 => 2, 2, 2
165 => 0, 0, 0
166 => 1, 1, 1
167 => 0, 0, 0
168 => 3, 3, 3
169 => 0, 0, 0
170 => 1, 1, 1
171 => 0, 0, 0
172 => 2, 2, 2
173 => 0, 0, 0
174 => 1, 1, 1
175 => 0, 0, 0
176 => 4, 4, 4
177 => 0, 0, 0
178 => 1, 1, 1
179 => 0, 0, 0
180 => 2, 2, 2
181 => 0, 0, 0
182 => 1, 1, 1
183 => 0, 0, 0
184 => 3, 3, 3
185 => 0, 0, 0
186 => 1, 1, 1
187 => 0, 0, 0
188 => 2, 2, 2
189 => 0, 0, 0
190 => 1, 1, 1
191 => 0, 0, 0
192 => 6, 6, 6
193 => 0, 0, 0
194 => 1, 1, 1
195 => 0, 0, 0
196 => 2, 2, 2
197 => 0, 0, 0
198 => 1, 1, 1
199 => 0, 0, 0
200 => 3, 3, 3
201 => 0, 0, 0
202 => 1, 1, 1
203 => 0, 0, 0
204 => 2, 2, 2
205 => 0, 0, 0
206 => 1, 1, 1
207 => 0, 0, 0
208 => 4, 4, 4
209 => 0, 0, 0
210 => 1, 1, 1
211 => 0, 0, 0
212 => 2, 2, 2
213 => 0, 0, 0
214 => 1, 1, 1
215 => 0, 0, 0
216 => 3, 3, 3
217 => 0, 0, 0
218 => 1, 1, 1
219 => 0, 0, 0
220 => 2, 2, 2
221 => 0, 0, 0
222 => 1, 1, 1
223 => 0, 0, 0
224 => 5, 5, 5
225 => 0, 0, 0
226 => 1, 1, 1
227 => 0, 0, 0
228 => 2, 2, 2
229 => 0, 0, 0
230 => 1, 1, 1
231 => 0, 0, 0
232 => 3, 3, 3
233 => 0, 0, 0
234 => 1, 1, 1
235 => 0, 0, 0
236 => 2, 2, 2
237 => 0, 0, 0
238 => 1, 1, 1
239 => 0, 0, 0
240 => 4, 4, 4
241 => 0, 0, 0
242 => 1, 1, 1
243 => 0, 0, 0
244 => 2, 2, 2
245 => 0, 0, 0
246 => 1, 1, 1
247 => 0, 0, 0
248 => 3, 3, 3
249 => 0, 0, 0
250 => 1, 1, 1
251 => 0, 0, 0
252 => 2, 2, 2
253 => 0, 0, 0
254 => 1, 1, 1
255 => 0, 0, 0