「题解」统计二进制中 1 出现的个数

二进制统计

给定一个无符号整数 nn ,求 nn 的二进制表示中 11 的个数

n=101(2)ans=2n = 101_{(2)} \Longrightarrow \text{ans} = 2

n=1001010111(2)ans=6n = 1001010111_{(2)} \Longrightarrow \text{ans} = 6

咋做啊 kk

暴力

直接 O(log2n)O(\log_2 n) 暴力

对于每一位统计一下

1
2
3
4
5
6
7
int bitcount (unsigned int n) {
unsigned int cnt;

for (cnt = 0; n; n >>= 1) cnt += n & 1;

return cnt;
}

我们还可以每次清除最低位的 11,时间复杂度 O(1O(1 出现的次数 ))

1
2
3
4
5
6
7
8
9
10
int bitcount (unsigned int n) {
unsigned int cnt = 0;

while (n) {
n &= (n - 1);
cnt++;
}

return cnt;
}

lowbit

可以借用 lowbit 来进行计算

1
2
3
4
5
6
7
8
9
10
inline int lowbit(int x) { return x & (-x); }

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

查表法

可以建表暴力查表

比如对于 1011101000111110(2)1011101000111110_{(2)} 这个 1616 位无符号二进制数,我们可以将其分成 1011 1010 0011 11101011\ 1010\ 0011\ 1110 每一段四位,四位数算就可以了

这样四位数就好做了,打一个大小为 242^4 表,就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
unsigned int table[16] = {
0, 1, 1, 2,
1, 2, 2, 3,
1, 2, 2, 3,
2, 3, 3, 4
} ;

int bitcount (unsigned int n) {
unsigned int cnt = 0;

while (n) {
cnt += table[n & 0xf] ;
n >>= 4;
}

return cnt ;
}

44 位表太小了,我们可以使用八位表

1926081700(10)=01110010 11001101 10101100 10100100(2)1926081700_{(10)} = 0111 0010\ 1100 1101\ 1010 1100 \ 1010 0100_{(2)}

每次取 n & 0xff(n >> 8) & 0xff(n >> 16) & 0xff(n >> 24) & 0xff 就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
unsigned int table[256] = {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
};
int bitcount (unsigned int n) {
return table[n & 0xff] + table[(n >> 8) & 0xff] + table[(n >> 16) & 0xff] + table[(n >> 24) & 0xff] ;
}

查表法更利于并行执行 /cy,好像 __builtin_popcount 中的也是这样写的(

当然如果有时间也可以搞一个 16bit16\text{bit} 的表,或者更神仙一点 32bit32\text{bit} 的表,速度将会更快 /cy

神仙算法

1
2
3
4
5
6
7
8
int bitcount (unsigned int n) {
n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f);
n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff);
n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff);
return n;
}

为什么这样可以呢QAQ

自己手算一下,大体就是这个步骤:

img

而为什么要用这几个数呢,我们将她们的二进制表示出来

1
2
3
4
5
0x55555555 = 01010101 01010101 01010101 01010101
0x33333333 = 00110011 00110011 00110011 00110011
0x0F0F0F0F = 00001111 00001111 00001111 00001111
0x00FF00FF = 00000000 11111111 00000000 11111111
0x0000FFFF = 00000000 00000000 11111111 11111111

我们可以将这个方法推广到 128128 位 (

1
2
3
4
5
// T 是类型(
v = v - ((v >> 1) & (T) ~ (T) 0 / 3); // temp
v = (v & (T) ~ (T) 0 / 15 * 3) + ((v >> 2) & (T) ~ (T) 0 / 15 * 3); // temp
v = (v + (v >> 4)) & (T) ~ (T)0 / 255 * 15; // temp
c = (T)(v * ((T) ~ (T) 0 / 255)) >> (sizeof(T) - 1) * CHAR_BIT; // count

取模

可以使用基于取模的计算方法

1
2
3
4
int bitcount (unsigned int n) {
unsigned int tmp = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
return ((tmp + (tmp >> 3)) & 030707070707) % 63;
}

注意,033333333333011111111111030707070707 这三个数都是八进制的数(

第一行的作用就是将 nn 的二进制表示写出来,然后每 3bit3\text{bit} 分成一组,求出每一组中 11 的个数,再二进制的 11 个数表示成二进制的形式

具体实现可以自己手算一下 /cy

在第一行的基础上,将 tmp 中相邻的两组中 11 的个数累加,由于累加到过程中有些组被重复加了一次,所以要舍弃这些多加的部分,这就是 & 030707070707 的作用,又由于最终结果可能大于 6363,所以要取模

需要注意的是,经过第一行代码后,从右侧起,每相邻的 3bit3\text{bit} 只有四种可能,即000000, 001001, 010010, 011011,为啥呢?因为每 3bit3\text{bit}11 的个数最多为 33 。所以下面的加法中不存在进位的问题,因为 3+3=63 + 3 = 6,不足 88,不会产生进位

tmp + (tmp >> 3) 这句就是是相邻组相加,注意会产生重复相加的部分

最后为什么还要 %63\%63呢,因为上面相当于每次计算相连的 6bit6\text{bit}11 的个数,最多是 111111=77(8)=63(10)111111 = 77_{(8)} = 63_{(10)},所以最后要对 6363 取模。

位标识

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct _byte  {
unsigned a:1;
unsigned b:1;
unsigned c:1;
unsigned d:1;
unsigned e:1;
unsigned f:1;
unsigned g:1;
unsigned h:1;
};

long get_bit_count (unsigned char b) {
struct _byte *by = (struct _byte*) &b;
return (by->a + by->b + by->c + by->d + by->e + by->f + by->g + by->h);
}

指令法

微软提供的SSE4指令 /cy

Link : _mm_popcnt_u32 _mm_popcnt_u64

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
#include <nmmintrin.h>

int main () {
unsigned int a = 0x2F63A150;
unsigned __int64 b = 0x123456789ABCDEF0;

int res32 = _mm_popcnt_u32(a);
int res64 = _mm_popcnt_u64(b);

printf_s("%d\n", res32);
printf_s("%d\n", res64);

return 0;
}
坚持原创技术分享,您的支持将鼓励我继续创作!