下面程序输出什么_360集团笔试题

杨海涛

分治计算一的个数

发表于 2016-04-13 10:13:28 回复(0)

leobuzhi

计算二进制的一的个数，这个算法叫做平行算法。

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 ;

}

速度不一定最快，但是想法绝对巧妙。说一下其中奥妙，其实很简单，先将n写成二进制形式，然后相邻位相加，重复这个过程，直到只剩下一位。

以217（11011001）为例，有图有真相，下面的图足以说明一切了。217的二进制表示中有5个1

编辑于 2016-01-26 22:53:28 回复(14)

Jeffdon

这里运用了分治法计算二进制数中1的个数

(n & 0x55555555) + ((n >> 1) & 0x55555555) 计算每对相邻的2位中有几个1

(n & 0x33333333) + ((n >> 2) & 0x33333333) 计算每相邻的4位中有几个1

接下来8位，16位，32位，对于32位的机器，5条位运算语句就够了。

发表于 2015-11-02 20:35:09 回复(0)

任家硕

197 = 128 + 64 + 4 + 1

11000101 01100010

01010101 01010101

01000101 01000000

69 + 64 = 133

133 = 128 + 4 + 1

10000101 00100001

00110011 00110011

00000001 00100001

1 + 33 = 34

00100010 00000010

00001111 00001111

00000010 00000010

2 + 2 = 4

00000100 00000000

11111111 11111111

00000100 00000000

4

00000100

11111111

00000100

4

编辑于 2016-11-30 23:57:54 回复(2)

lijiayu2011

int func(unsigned int i)

{

unsigned int temp = i;

temp = (temp & 0x55555555) + ((temp>> 1) & 0x55555555); //temp相邻位相加

temp = (temp & 0x33333333) + ((temp >> 2) & 0x33333333); //temp相邻（以2为单位）相加

temp = (temp & 0x0f0f0f0f) + ((temp>> 4) & 0x0f0f0f0f); //temp相邻（以4为单位）相加

temp = (temp & 0xff00ff) + ((temp>> 8) & 0xff00ff); //temp相邻（以8为单位）相加

temp = (temp & 0xffff) + ((temp>> 16) & 0xffff) ; //temp相邻（以16为单位）相加

return temp;

}

temp相邻位相加：相加原理若相邻的两个数为00则结果为00，相邻的两个数为01或10则结果为01，相邻两个数为11则结果为10，也就是先小范围统计每两位中1的个数，后面的步骤在累计有多少个1.

0x11530828的二进制表示如下：

0001 0001 1001 0011 0000 1000 0010 1000；

0 1 0 1 1 1 0 2 0 0 1 0 0 1 1 0；

1 1 2 2 0 1 1 1；

2 4 1 2

6 3

9

发表于 2017-03-31 08:58:12 回复(2)

郁郁欲雨

一般这种题就乱选了，不想浪费时间也做不出来

发表于 2018-09-03 20:20:02 回复(1)

小呀么小甜椒

0xaaaaaaaa = 10101010101010101010101010101010 (偶数位为1，奇数位为0）

0x55555555 = 1010101010101010101010101010101 (偶数位为0，奇数位为1）

0x33333333 = 110011001100110011001100110011 (1和0每隔两位交替出现)

0xcccccccc = 11001100110011001100110011001100 (0和1每隔两位交替出现)

0x0f0f0f0f = 00001111000011110000111100001111 (1和0每隔四位交替出现)

0xf0f0f0f0 = 11110000111100001111000011110000 (0和1每隔四位交替出现)

平行法计算二进制中1的个数，二进制中利用相邻位相加，直到最后剩下一个数，求出1的个数。

举例：
求255（1111 1111）二进制中1的个数

1 1 1 1 1 1 1 1 2 2  2 2  4  4  8

将255的8个位置进行编号，1号位置到8号位置，首先对12、34、56、78进行相加，得到2、2、2、2，分别存放于12、34、56、78位置，再将12、34、56、78看成一个整体，将12和34、56和78相加，得到4、4存放于1234、5678位置，最后再将1234和5678相加，得到8。算法也是利用了二分的思想，给定一个二进制数，将均分成两部分，分别求左边和右边的1的个数，然后相加，最后得到结果。
参考：

https://blog.csdn.net/u012604810/article/details/80623241
https://blog.csdn.net/hyqsong/article/details/50880526

发表于 2018-09-26 09:58:01 回复(1)

zt_xcyk

C

就是求197的二进制中 1的个数

发表于 2016-02-03 23:26:12 回复(0)

沉鱼

&gt;&gt; 右移（二进制）在C/C++中，0x为十六进制的前缀标识，0位八进制的前缀标识，十进制没有前缀标识。因此，那些奇怪的字符为整数的十六进制表示。有那么多的整数，为何在涉及位操作程序中会出现这些整数呢。因为这些整数的二进制形式很特殊，可以借助Windows系统自带的计算器，快捷计算出该整数的二进制形式 0xaaaaaaaa = 10101010101010101010101010101010 (偶数位为1，奇数位为0） 0x55555555 = 1010101010101010101010101010101 (偶数位为0，奇数位为1） 0x33333333 = 110011001100110011001100110011 (1和0每隔两位交替出现) 0xcccccccc = 11001100110011001100110011001100 (0和1每隔两位交替出现) 0x0f0f0f0f = 00001111000011110000111100001111 (1和0每隔四位交替出现) 0xf0f0f0f0 = 11110000111100001111000011110000 (0和1每隔四位交替出现) 利用上述具有特殊二进制的整数，可以很方便进行位操作，而且该整数的十六进制形式比较好记，也不用写那么多的0，1.

编辑于 2019-10-30 19:56:01 回复(0)