By

文章目录
  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    0011

复杂度是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. 查表法