立っているビットの数を数え

algorithmの考え方

具体的で小さな数から試してみる

1桁

そのまま返せばいい

2桁

00,01,10,11の4パターンある

それぞれのパターンと立っているビット数との関係

table:chart

bit count

00 00

01 01

10 01

11 10

1桁目と2桁目をそれぞれ1つの値と考えて足せばいい

11なら、01+01=10(2個)となる

1桁目は01,2桁目は10でマスクすればとりだせる

4桁

0111→0011

1101→0011

2桁ずつ足せばいい

0111→01,10→0011

0101と1010でマスクしてそれぞれのブロックの1桁目と2桁目を取り出して足す

そのあと1100と0011でブロックごとに取り出して足す

一般化