二进制权重之和

解题思路

本题区间上界只有10^5，可以逐个整数求二进制中1的个数。对x不断执行x&=x-1，每次恰好清除最低的一位1，操作次数就是该数的权重，再累计区间内全部权重。

例如5的二进制101，第一次变100，第二次变000，故权重为2。

正确性说明

x-1会把最低1变0、右侧0变1；与原x按位与后，仅最低1被清除，其余高位保持。因此循环次数与原有1的数量一一对应。遍历闭区间中每个数一次，累计得到总权重。

易错点

二进制权重不是二进制长度；区间包含L与R两个端点；总和用long long。

复杂度

时间O((R-L+1)log R)，空间O(1)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int L, R;
    cin >> L >> R;
    long long answer = 0;
    for (int value = L; value <= R; value++) {
        int x = value;
        while (x) {
            x &= x - 1;
            answer++;
        }
    }
    cout << answer << "\n";
    return 0;
}