//题目: 求二进制数中1的个数
public class Main {
public static void main(String[] args) {
System.out.println(getOneCount1(19));
System.out.println(getOneCount2(19));
System.out.println(getOneCount3(19));
}
// 解法1: 使用求余操作 O(log2N)
public static int getOneCount1(int n) {
int result = 0;
while (n != 0) {
if (n % 2 == 1) {
result++;
}
n = n / 2;
}
return result;
}
//解法2: 使用位操作 O(log2N)
public static int getOneCount2(int n){
int result = 0;
while(n!=0){
// if((n&1) == 1){
// result++;
// }
result = result+(n&1);
n = n>>1;
}
return result;
}
//解法3: 使用n与n-1与运算的方式 O(M),M为1的个数
public static int getOneCount3(int n){
int result = 0;
while(n!=0){
n = n&(n-1);
result++;
}
return result;
}
//解法4: 使用分支操作把0-255种情况全都列举出来,然后根据条件直接返回结果 O(1)
//解法5: 把0-255各有多少个1提前存在数组中,根据数字直接返回结果 O(1)
//4,5解法属于以空间换时间
}