N = gets.to_i def dfs(n, memo) return 0 if n <= 0 return memo[n] if memo[n] if n.even? memo[n] = dfs(n / 2, memo) + n / 2 else memo[n] = 2 * dfs((n - 1) / 2, memo) end end memo = Hash.new puts dfs(N, memo)