跳转至

二进制 1 的个数

方法一

不断地减去 lowbit

int bitcnt(int x)
{
    int ans = 0;
    while (x) { ans ++; x -= lowbit(x); }
    return ans;
}

方法二

int b1 = 0b01010101010101010101010101010101;
int b2 = 0b00110011001100110011001100110011;
int b4 = 0b00001111000011110000111100001111;
int b8 = 0b00000000111111110000000011111111;
int b16 = 0b00000000000000001111111111111111;

int bitcnt(int x)
{
    x = (b1 & x) + (((b1 << 1) & x) >> 1);
    x = (b2 & x) + (((b2 << 2) & x) >> 2);
    x = (b4 & x) + (((b4 << 4) & x) >> 4);
    x = (b8 & x) + (((b8 << 8) & x) >> 8);
    x = (b16 & x) + (((b16 << 16) & x) >> 16);
    return x;
}
AcWing 801. 二进制中1的个数

给定一个长度为 \(n\) 的数列，请你求出数列中每个数的二进制表示中 \(1\) 的个数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>

using namespace std;
int debuggersum = 0;

// 即使是不成熟的尝试，

int lowbit(int x)
{
    return (~x + 1) & x;
}

int b1 = 0b01010101010101010101010101010101;
int b2 = 0b00110011001100110011001100110011;
int b4 = 0b00001111000011110000111100001111;
int b8 = 0b00000000111111110000000011111111;
int b16 = 0b00000000000000001111111111111111;

int bitcnt(int x)
{
    x = (b1 & x) + (((b1 << 1) & x) >> 1);
    x = (b2 & x) + (((b2 << 2) & x) >> 2);
    x = (b4 & x) + (((b4 << 4) & x) >> 4);
    x = (b8 & x) + (((b8 << 8) & x) >> 8);
    x = (b16 & x) + (((b16 << 16) & x) >> 16);
    return x;
}

// int bitcnt(int x)
// {
//     int ans = 0;
//     while (x) { ans ++; x -= lowbit(x); }
//     return ans;
// }

int n, t;

void solve(void)
{
    scanf ("%d", &n);
    while (n --)
    {
        int t; scanf ("%d", &t);
        printf ("%d ", bitcnt(t));
    }
}

// 也胜于胎死腹中的策略。

int main(void)
{
    ifstream fi; ofstream fo;
    fi.open("./lrq.in"); fo.open("./lrq.out");
    if (fi.is_open() && fo.is_open())
    {
        fo << "start running ..." << endl; fo.close(); fi.close();
        for (long long i = 1; i <= 4e8 + 2e7; i++);
        FILE *fin = freopen("./lrq.in", "r", stdin);
        FILE *fout = freopen("./lrq.out", "w", stdout);
        solve(); fclose(fin); fclose(fout);
    }
    else solve();

    return 0;
}