#include #include #include #include using namespace std; int64_t pcnt(int64_t x) { return __builtin_popcountll(x); } const int64_t trunc = 20, lt = 1 << trunc; int main() { int64_t n; cin >> n; auto nxt = vector>(trunc + 1, vector(3 * trunc)), step = vector>(trunc + 1, vector(3 * trunc)); // (offset, num) for (int64_t i = 0; i <= trunc; i++) { for (int64_t j = !i; j < 3 * trunc; j++) { int64_t j_ans = j, c = 0; for (; j_ans < lt; c++, j_ans += pcnt(j_ans) + i) ; nxt[i][j] = j_ans; step[i][j] = c; } } int64_t ans = 1, i; for (i = 1; nxt[pcnt(i >> trunc)][i & (lt - 1)] + lt * (i >> trunc) <= n; i = nxt[pcnt(i >> trunc)][i & (lt - 1)] + lt * ((i >> trunc))) { ans += step[pcnt(i >> trunc)][i & (lt - 1)]; } for (; i < n; i += pcnt(i)) { ans++; } if (i == n) cout << ans << endl; else cout << -1 << endl; return 0; }