本文共 909 字，大约阅读时间需要 3 分钟。

题目：

给定一个32位整数n，可为0，可为正，也可为负，返回该整数二进制表达中1的个数

解法：

一、最简单的解法

整数n每次进行无符号右移一位，检查最右边的bit是否为1来进行统计，代码如下：

public int count1(int n){    int res=0;    while(n!=0){        res+=n&1;        n>>>=1;    }    return res;}

上面这个方法在最复杂的情况下要经过32次循环

二、下面看一个循环次数只与1的个数有关的解法。

public int count2(int n){    int res=0;    while(n!=0){        n&=(n-1);        res++;    }    return res;}

三、与count2方法复杂度一样的是如下代码中的count3方法：

public int count3(int n){    int res=0;    while(n!=0){        n-=n&(~n+1);        res++;    }    return res;}

每次进行n-=n&(~n+1)操作的时候，是移除最右侧的1的过程，等号右边n&(~n+1)的含义是得到n中最右侧的1，这个操作在位运算的题目中常出现。例如：n=01000100，n&(~n+1)=00000100，n-n&(~n+1)=01000000。

四、一种看起来很“超自然”的解法，平行算法

public int count4(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);}

参考自：《程序员代码面试指南》

转载地址：http://zryai.baihongyu.com/