K!が2で割れる回数=K-popcount(K)であること

$${K!}$$が2で割れる回数を$${f(K)}$$とすると、$${f(K)=K-\text{popcount}(K)}$$ となることの証明。ARC156のD問題で使って、忘れそうなので備忘メモ。

まず、$${K!}$$が素数$${p}$$で割れる回数$${f(K)}$$は中学受験の頻出問題で、$${K}$$を$${p}$$で割った商、$${K}$$を$${p^2}$$で割った商、…を全てたせばよい。これは、$${1}$$から$${K}$$まで全て並べて、$${p}$$の倍数をチェックし、$${p^2}$$の倍数をチェックし、$${p^3}$$の倍数をチェックし・・・という作業をするとわかる。

例：K=10, p=2
1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10
--------------------------------------
    1       1       1       1        1  <-- 2で割った商=5
            1               1           <-- 4で割った商=2
                            1           <-- 8で割った商=1
--------------------------------------
    1回     2回     1回     3回     1回

これを2進数で考えると、$${K}$$を$${2}$$で割った商というのは、2進数で1回右シフト、$${2^2}$$で割った商は2進数で2回右シフト、・・・なので、0になるまでシフトしながらたしていけば、$${f(K)}$$を算出できる。例えば$${K=10}$$の場合、

10   = 1010

10/2 =  101 = 5
10/4 =   10 = 2
10/8 =    1 = 1
---------------
              8

さて、この表をじっくり眺めると、$${f(K)+K}$$は次のように変形できる。

1010     1111
 101      000
  10  =    11
+  1        0
----     ----

一番上に$${K}$$を追加して並べると、斜めに1が並んでいる。つまり$${K}$$の$${b}$$桁目の1は、右シフトしながら$${b}$$回出現するので、それらをまとめて並べ替えれば、$${11…11(b個) = 2^b-1}$$を、1が出現する回数分だけたせばよいことがわかる。ところで、$${\sum 2^b}$$は、$${K}$$のbitで1が立っているところを渡りながら$${b-1}$$番目のbitを$${b}$$番目にしてたしているだけなので、これは$${2K}$$であり、$${-1}$$は$${K}$$のbitが立っている回数分だけ出現するので、結局この和は$${2K-p(K)}$$となる。（但し、$${K}$$のpopcountを$${p(K)}$$とした。）

1111 = 2^4 - 1 = 10000 - 1
 000 =   0     =  0000
  11 = 2^2 - 1 =   100 - 1
+  0 =   0     =    00
-----------------------------
               = 10100 - p(K)
               =   2*K - p(K)

さて、もともとこの和は$${f(K)+K}$$だったので、$${f(K)+K=2K-p(K)}$$、つまり、$${f(K)=K-p(K)}$$であることがわかった。

なお、$${K}$$を右シフトしながらたす作業と、popcount $${p(K)}$$を求める計算とどちらが速いかは微妙なところなんじゃないか。シフト和はint32なら30回程度だし、popcountは高速アルゴリズムでも5～10回くらいは計算する。但し、popcountがハードウェアで実装されている場合はかなり速いらしい。