証明なしで実験で回答するの、人によって好き嫌いありそう。
https://yukicoder.me/problems/no/589
問題
整数Nが与えられる。となるiのうちが偶数となるのはいくつか。
解法
実験してみると、が奇数となるのは2のpopcount(N)乗であることがわかる。
よって(N+1)からそれを引けばよい。
この特徴については、いくつかのサイトで言及があるね。
A048967 - OEIS
https://www.math.hmc.edu/funfacts/ffiles/30001.4-5.shtml
Art of Problem Solving
ll N; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; x=__builtin_popcountll(N); cout<<(N+1)-(1LL<<x)<<endl; }
まとめ
最初は頑張って求めようかと思ってたよ。