B2140 二进制分类 题解

· · 题解

题目分析

这道题要求我们把 1 \sim n 的所有数分类，那我们只需要统计这个数的二进制有多少个 1 和 0 就行了。有一种办法就是把这个数的二进制的每一位都提取出来。

代码中用到的一些进制处理：

将 x （二进制形式）右移 n 位：

x>>n

将 x 和 y 按位与：

x&y

（按位且的规则：将 x 和 y 的二进制按位比较，若一位都是 1 ，则返回 1 ，否则，返回 0 ）

那么，有了以上的铺垫，我们就能很轻松的提取了。我们这需要每次把数和 1 进行按位且操作，这样就能提取出这个数的最后一位，然后在把这个数右移一位就行了。

代码

#include <iostream>
using namespace std;
int A, B, cnt0, cnt1;
int main() {
    int n, t, temp;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cnt0 = 0, cnt1 = 0;
        t = i;
        while (t) {
            temp = t & 1;
            t = t >> 1;
            if (temp) cnt1++;
            else cnt0++;
        }
        cnt1 > cnt0 ? A++ : B++;
    }
    cout << A << ' ' << B;
}