面白いとは思うけど真面目に解く人間いなさそう。

solution

問題文からOEISあるいはサンプルから実験の雰囲気を感じとり、そのようにする。 https://oeis.org/A048967。$O(1)$。

implementation

#!/usr/bin/env python3
n = int(input())
print(n + 1 - 2 ** bin(n).count('1'))