# 3.具体解法

```#include <stdint.h>

int count1(uint32_t x){
int count=0;
while(x){
if(x&0x1)
++count;
x=(x>>1);
}
return count;
}```

```int count1(uint32_t x){
int count = 0;
while(x){
x = x & (x-1);
count++;
}
return count;
}```

```int count1(int x){
int n=0;
while((x+1)){
n++;
x|=(x+1);
}
return 32-n;
} ```

```int Hamming_weight(uint32_t 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;
}```

```0x5555……这个换成二进制之后就是01 01 01 01 01 01 01 01……
0x3333……这个换成二进制之后就是0011 0011 0011 0011……
0x0f0f………这个换成二进制之后就是00001111 00001111……```

```struct BitStruct{
uint8_t a:1;uint8_t b:1;uint8_t c:1;uint8_t d:1;uint8_t e:1;uint8_t f:1;uint8_t g:1;uint8_t h:1;
uint8_t a1:1;uint8_t b1:1;uint8_t c1:1;uint8_t d1:1;uint8_t e1:1;uint8_t f1:1;uint8_t g1:1;uint8_t h1:1;
uint8_t a2:1;uint8_t b2:1;uint8_t c2:1;uint8_t d2:1;uint8_t e2:1;uint8_t f2:1;uint8_t g2:1;uint8_t h2:1;
uint8_t a3:1;uint8_t b3:1;uint8_t c3:1;uint8_t d3:1;uint8_t e3:1;uint8_t f3:1;uint8_t g3:1;uint8_t h3:1;
};

//get number of 1
int count1(uint32_t x){
BitStruct* stBit=(BitStruct*)&x;
return (stBit->a+stBit->b+stBit->c+stBit->d+stBit->e+stBit->f+stBit->g+stBit->h+
stBit->a1+stBit->b1+stBit->c1+stBit->d1+stBit->e1+stBit->f1+stBit->g1+stBit->h1+
stBit->a2+stBit->b2+stBit->c2+stBit->d2+stBit->e2+stBit->f2+stBit->g2+stBit->h2+
stBit->a3+stBit->b3+stBit->c3+stBit->d3+stBit->e3+stBit->f3+stBit->g3+stBit->h3);
}```

`cout<<_mm_popcnt_u32(0xffffffff)<<endl;`

```int HAKMEM(uint32_t n){
uint32_t tmp;
tmp=n-((n>>1)&033333333333)-((n>>2)&011111111111);
tmp=(tmp+(tmp>>3))&030707070707;
return tmp%63;
}```

```(x mod 63)=(a*64^5)%63+(b*64^4)%63+(c*64^3)%63+(d*64^2)%63+(e*64)%63+f%63

(x mod 63)=a%63+b%63+c%63+d%63+e%63+f%63

(x mod 63)=(a+b+c+d+e+f)%63=a+b+c+d+e+f```

```int bitCountSearchTable(unsigned int n){
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,
};

return table[n &0xff]+table[(n>>8)&0xff]=+table[(n >>16)&0xff]+table[(n >>24)&0xff];
}```

（2）静态表-4bit 原理和8-bit表相同，详见8-bit表的解释

```int BitCount4(unsigned int n){
unsigned int table[16]={
0, 1, 1, 2,
1, 2, 2, 3,
1, 2, 2, 3,
2, 3, 3, 4
} ;

unsigned int count =0 ;
while (n){
count += table[n &0xf] ;
n >>=4 ;
}
return count ;
}```

# 参考文献

0 条评论

## 相关文章

### HUST 1588 辗转数对

1588 - 辗转数对 时间限制：1秒 内存限制：128兆 155 次提交 27 次通过 题目描述假设当前有一个数对(a, b)，我们可以通过一步将这个数对...

3459

56710

1262

### 让你眼花缭乱的匹配函数反查技巧

2956

Flink程序是执行分布式集合转换(例如，filtering, mapping, updating state, joining, grouping, defi...

1.7K7

2947

1112

1083

1827

### 51Nod 1182 完美字符串(字符串处理 贪心 Facebook Hacker Cup选拔)

1182 完美字符串 ?             题目来源：                         Facebook Hacker Cup选拔    ...

2917