题目链接：https://codeforces.com/contest/1362/problem/C
计算从 $0$ 到 $n$ 有多少相邻的数二进制下同一位不同，考虑前导 $0$ 。（$1≤n≤10^{18}$）
逐位考虑。因为值是连续的，所以从右至左第 $i$ 位的 $01$ 周期为 $2^i$ 。计算出完整的 $01$ 周期个数 $t$，每个完整的周期内有一对 $01$ 相邻，相邻的完整周期间共有 $t - 1$ 对 $01$ 相邻，然后考虑多余的周期长度，如果之前有完整的 $01$ 周期且有多余的周期，答案 $+1$，如果多余周期长度大于完整周期的一半，答案 $+1$ 。
移位较多应使用 1LL 。
#include <bits/stdc++.h> using ll = long long; using namespace std; void solve() { ll n; cin >> n; ++n; ll ans = 0; for (int i = 1; i < 64; i++) { ll len = (1LL << i); ll t = n / len; ans += t + max(0LL, t - 1) + (t and n % len > 0) + (n % len > len / 2); if (len >= n) break; } cout << ans << "\n"; } int main() { int t; cin >> t; while (t--) solve(); }
Codeforces Round #647 (Div. 2) C. Johnny and Another Rating Drop（数学）
原文：https://www.cnblogs.com/Kanoon/p/13052840.html