2 進数の 1 の数

10 進数の整数 n に対し，1 から n の整数を 2 進数で表したときの各々の 1 の個数の和を求めよ。

F = function(n) { # 再帰関数
  if (n <= 2) return(n)
  k = floor(log(n, base=2)) # 2 進数で表現したときの桁数 - 1
  ones = numeric(k) # k 桁で表現される 0 ～ 2^k - 1 の整数に含まれる 1 の数
  ones[1] = 1
  if (k > 1) for (i in 2:k) ones[i] = 2*ones[i-1] + 2^(i-1)
  return(Recall(n-2^k) + ones[k] + n-2^k+1) # 2^k ～ n までを再帰呼び出し
}
F0 = function(n) { # n が小さいときにしか使えない，馬鹿正直に計算する関数
  sum(sapply(0:n, function(m) sum(as.integer(intToBits(m)))))
}
F(3)
F(13)
n = 37; cat(F(n), F0(n), "\n")
n = 370; cat(F(n), F0(n), "\n")
n = 3700; cat(F(n), F0(n), "\n")
system.time(print(F(10^3)))
system.time(print(F(10^10)))

実行結果

> F(3)
[1] 4

> F(13)
[1] 25

> n = 37; cat(F(n), F0(n), "\n")
93 93

> n = 370; cat(F(n), F0(n), "\n")
1518 1518

> n = 3700; cat(F(n), F0(n), "\n")
21475 21475

> system.time(print(F(10^3)))
[1] 4938
   ユーザ   システム       経過  
     0.008      0.001      0.020 # 所要時間はゴミみたいなもの

> system.time(print(F(10^10)))
[1] 164293127179
   ユーザ   システム       経過  
         0          0          0 # 所要時間はゴミみたいなもの