2進数を配列で扱った際、0からSまでのインクリメントにかかる計算量

コストを前のビットとの差異とする(ビットを前の数から何か所変更する必要があるか)

数                コスト

000000    0

000001    1

000010    2

000011    1

000100    3

000101    1

000110    2

000111    1

001000    4

001001    1

001010    2

みたいになって、0からSまででの合計を知りたい

桁毎に、コストを考えると、各桁で数をインクリメントした際に増えるコストの期待値は0桁目で1, 1桁目で1/2, 2桁目で1/4という風になる

よって全体で(1+1/2+1/4+1/8+1/16+.... )*S = 2S 回ぐらい(近似)かかると分かった

N進数で考えると 等比数列の和が出てきて S / (1 - 1/N) 回

すみません途中で嫌になって説明が無くなりました

今回の記事を書いた経緯は0~13071(2^17-1)までインクリメントする際にかかるコストをプログラムに計算させたら丁度2倍の26142になり感心したからなのですが、説明が難しく虚無になり頓挫しました