问题:
Write a function that takes an unsigned integer and returns the number of ’1‘ bits it has (also known as the Hamming weight).
For example, the 32-bit integer ’11‘ has binary representation 00000000000000000000000000001011, so the function should return 3.
对于这个问题，我们首先想到是将十进制数转换成二进制的过程，通过除2取余来得到二进制的每一位来判断。然后，最容易想到的方法肯定不是最好的算法，我们可以考虑有没有比这个方法更好的算法。我们自然想到，通过移位操作要比出发操作的效率高很多。
位操作算法：首先将整数n与0x01做位与运算(&),然后将n右移移位，直到将所有位数全部移完。这种方法虽然比上一种好，但执行次数是整数的位数，那有没有一种执行次数是1的个数呢？答案是肯定的。
我们通过消除最后边的1来操作(n&=(n-1))，很多博客都介绍了这种方法，而我则侧重介绍该方法的原理：可以设想一下，假如n只有一个1的情况，做减1操作会对进行借位或者直接减掉，那么做n&(n-1)的结果则为零，因为n-1后，相对于n原来1的位置发生了改变。那么n有多个1的情况，在第一个1的左边是不会变得的,每次只会影响右边第一个1，情况和之前一样，这个，操作数就为1的个数。
代码如下，自己写了测试程序（这个小习惯可能会在你面试时写代码的时候发挥奇效呢）。
import java.util.Random; public class NumberOf1Bit { /** * 转换成2进制数，去比较每一位的值来判断是否为1 * @param n 输入的一个32位整数 * @return count 记录1的个数 */ public int hammingWeight1(int n){ int count=0; while(n!=0){ if(n%2!=0) count++; n/=2; } return count; } /** * 使用移位操作，效率要高于除法运算 * @param n * @return */ public int hammingWeight2(int n){ int count=0; while(n!=0){ if((n&0x01)!=0) count++; n>>=1; } return count; } /** * 前两个的运算次数都是每个整数的全部位，下面的方法则只需计算次数由1的个数决定 * @param n * @return */ public int hammingWeight3(int n){ int count=0; while(n!=0){ if(n!=0) count++; n&=(n-1); } return count; } public void test(){ Random r = new Random(); for(int i=0;i<10;i++){ int n=r.nextInt(50); System.out.println(n+"------"+Integer.toBinaryString(n)); System.out.println(hammingWeight1(n)+" "+hammingWeight2(n)+" "+hammingWeight3(n)); System.out.println("**********"); } } public static void main(String[] args) { // TODO Auto-generated method stub new NumberOf1Bit().test(); } }
原文：http://www.cnblogs.com/triplewood/p/5118618.html
