シフトと加算

装置がある。
装置にはディスプレイがあり，そこには最初 1 と表示されている。
ディスプレイの下には［+1］と［×2］という 2 つのボタンがある。
それぞれ，ディスプレイに表示されている数に 1 を加える，2 倍する，という機能だ。
ディスプレイある数を表示するために，最低何回ボタンを押さなければならないか求めよ。
たとえば，
10 を表示するためには ×2, ×2, +1, ×2 の 4 回
40 を表示するためには ×2, ×2, +1, ×2, ×2, ×2 の6 回
60 を表示するためには ×2, +1, ×2, +1, ×2, +1, ×2, ×2 の 8 回
65 を表示するためには ×2, ×2, ×2, ×2, ×2, ×2, +1 の 7 回

つまり，「全ての整数は，二進表示で，初期値 1 の左シフトと 1 の加算でできるということ。
左から順に 2 桁目以降が 0 なら左シフト 1 回，1 なら，左シフト 1 回と 1 の加算が必要。

func = function(n) {
  a = NULL
  repeat {
    a = c(n %% 2, a)
    if ((n = n %/% 2) == 0) break
  }
  a = a[-1]
  sum(a == 0) + sum(a == 1)*2
}

> func(10)
[1] 4

> func(40)
[1] 6

> func(60)
[1] 8

> func(65)
[1] 7

> func(10000000)
[1] 30