文章目录
  1. 1. 题目
  2. 2. 遍历法
  3. 3. 快速查找法
  4. 4. 查表法

题目

求一个二进制数字中1出现的个数

这道题目面试非常常见,但是工作中也很实用,以32位int整形为例,下面列举一下一些经典的做法(主要是做记录用^_^)

遍历法

这个是最简单的方法,向右移位,判断最低位是否为1进行计数即可!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* 普通遍历法
* @param n
* @return
*/

public static int traverseCount(int n)
{

int count = 0;
while(n>0)
{
n = n>>1;
count++;
}

return count;
}

该方法最直观,不过复杂度是O(N)

快速查找法

为啥说快速呢,因为这里的复杂度是和1个个数有关,有多少1就循环多少次,该方法的设计也非常巧妙

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* 快速计数法
* @param n
* @return
*/

public static int quickCount(int n)
{

int count = 0;
while(n>0)
{
n &= (n-1);
count ++;
}

return count;
}

大致可以这么理解

假设当前的n=7
n          n-1
0111    0110
0110    0101
0100    0000

复杂度是O(K),其中K为二进制数中1个数,非常实用

查表法

一般整形的位数是固定的,假如我们知道每种情况下的1的个数,其实直接查表即可,但是如果是32位的整形枚举这个表的可能性不是很大,但是巧妙的方法是可以将其分割成4个8位的数字,而8位的数字就只有256种情况了,可以直接方法预设的表中

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
/**
* 查表法
* @param n
* @return
*/

public static int searchTableCount(int n)
{

int[] table =
{
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];
}

该方法的复杂度是O(N/8),占的空间也不是特别多,也是比较实用的一种

还有一些神奇的方法可以看http://www.cnblogs.com/graphics/archive/2010/06/21/1752421.html,写得非常赞


本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可,我的博客欢迎复制共享,但在同时,希望保留我的署名权kubiCode,并且,不得用于商业用途。如您有任何疑问或者授权方面的协商,请给我留言

文章目录
  1. 1. 题目
  2. 2. 遍历法
  3. 3. 快速查找法
  4. 4. 查表法