题目条件

image-20200329221250027

嗯。。。条件全被控制了

两种解法,反正我是没想出来,第一种也是Java的bitcount函数的实现

两两归一

image-20200329221719255

https://blog.csdn.net/Scl_Diligent/article/details/101716713

emm,图源某位大佬,从左向右看,具体举个🌰,假设为8位

1 1 0 1 1 0 1 0 S1
1 0 1 1 S1’=(S1>>1) & 0b01010101(0x55)
1 0 0 1 0 1 0 1 S2=S1-S1’
0 1 0 1 S2’=S2&0b00110011(0x33)
1 0 0 1 S2’'=(S2>>2)&0b00110011(0x33)
0 0 1 1 0 0 1 0 S3=S2’+S2’’
0 0 1 1 S3’=S3>>4
0 0 0 0 0 1 0 1 S4=(S3+S3’)&0b00001111(0x0f)

这已经得到结果了,对于第三行,假设从左到右为b0, b1, b2, …,而第一行是a0, a1, a2 …那么我们有2*a0+a1 - a0 = b0b1,这波很巧妙把每两个合在一起了,此时开始等于有4组数据,那么继续,之后S3计算变为加法,这波就很妙,因为最高是2,所以如果两组都是2加起来大不了就是0100,也不会爆,至于S4先加和还是先位与都是一样的,最高就是1000,同样前面四位就无所谓了,之后思路类似

题解:

1
2
3
4
5
6
int bitcount(int n)
{
n = n -((n >> 1) & ( 0x55555555));
n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
return (((n + (n >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

image-20200329231049059

这个乘法很灵性啊,但是不给分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int bitCount(int x){
int ans;
int help1=85,help2=51,help3=15,help4=255,help5=255;
help1=(help1<<24)+(help1<<16)+(help1<<8)+help1;//6
help2=(help2<<24)+(help2<<16)+(help2<<8)+help2;//6
help3=(help3<<24)+(help3<<16)+(help3<<8)+help3;//6
help4=(help4<<16)+help4;//2
ans=x+((~(((x>>1)&help1)))+1);//5
ans=((ans>>2)&help2)+(ans&help2);//4
ans=((ans>>4)+ans)&help3;//3
ans=((ans>>8)+ans)&help4;//3
ans=((ans>>16)+ans)&help5;//3
return ans;
}

正常做法

逐四扫描

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
int bitCount(int x)
{
int ans = 0;
int fence = (0x11 << 24) | (0x11 << 16) | (0x11 << 8) | (0x11);
int tmp = x & fence;
x = x >> 1;
tmp = tmp + (x & fence);
x = x >> 1;
tmp = tmp + (x & fence);
x = x >> 1;
tmp = tmp + (x & fence);
// get count of per 4 bits
// do and operation per 4 bits, add the result to ans
ans = tmp & 0x0f;
tmp = tmp >> 4;
ans = ans + (tmp & 0x0f);
tmp = tmp >> 4;
ans = ans + (tmp & 0x0f);
tmp = tmp >> 4;
ans = ans + (tmp & 0x0f);
tmp = tmp >> 4;
ans = ans + (tmp & 0x0f);
tmp = tmp >> 4;
ans = ans + (tmp & 0x0f);
tmp = tmp >> 4;
ans = ans + (tmp & 0x0f);
tmp = tmp >> 4;
ans = ans + (tmp & 0x0f);

return ans;
}

这个是挺简单的想法,不解释应该也能懂