2進数で考える.

2倍するということは左に1ビットシフトすることであり, その後1を加えるということは末尾のビットを立てることである. これを繰り返すと, 例としては以下のようになる.

\[\begin{align} t_1 &= 0000001 \\ t_2 &= 0000010 \\ t_3 &= 0000100 \\ t_4 &= 0001001 \\ t_5 &= 0010011 \\ t_6 &= 0100110 \\ t_7 &= 1001100 \end{align}\]

これらをすべて足したものが \(s\) なので,

\[s = 1111111 + 1111 + 111\]

となる. 逆に言えば, \(s\) が上のように表せればその数は作れるということになる.

これは, \(1111111 + 1 = 10000000\) なので, \(s\) に \(k\) を足した数の立っているビット数は \(k\) 個になることを使えば確認できる.