题目：
49% 通过 计算在一个 32 位的整数的二进制表式中有多少个 1.
样例
给定 32 (100000)，返回 1
给定 5 (101)，返回 2
给定 1023 (111111111)，返回 9
解题：
Java程序：
public class Solution {
/**
* @param num: an integer
* @return: an integer, the number of ones in num
*/
public int countOnes(int num) {
// write your code here
return countOnes1(num); //总耗时: 1201 ms
// return countOnes2(num); //总耗时: 1185 ms
// return countOnes3(num); // 总耗时: 1215 ms
}
public int countOnes1(int num){
int count = 0;
while(num!=0){
if(num%2==1)
count++;
num=num/2;
}
return count;
}
public int countOnes2(int num){
int count = 0;
while(num!=0){
count +=num&0x01;
num = num>>1;
}
return count;
}
public int countOnes3(int num){
int count = 0;
while(num!=0){
num = num & (num-1);
count++;
}
return count;
}
};
上面程序中有三种方法，都来自编程之美
第一种：
原数除以2后，数字将减少一个0
若余数是1则，减少一个1，记录1的个数
若余数是0则，减少一个0，记录0的个数
第二种：
利用位运算
0&1 =0
1&1 =1
这个32位数与0000 0001 与运算的值是1，记录1的个数
即：count += num & 0x01
num右移一位
num=num>>1
第三种：
int count = 0;
while(num!=0){
num = num & (num-1);
count++;
}
return count;
好机智的方法，时间复杂度是O(M)，M是num中1的个数
Python程序：
class Solution:
# @param num: an integer
# @return: an integer, the number of ones in num
def countOnes(self, num):
# write your code here
# return self.countOnes1(num) # 387 ms
# return self.countOnes2(num) # 418 ms
return self.countOnes3(num) # 398 ms def countOnes1(self,num):
count = 0
while num!=0:
if num%2==1:
count+=1
num/=2
return count def countOnes2(self,num):
count = 0
while num!=0:
count += num&0x01
num = num>>1
return count def countOnes3(self,num):
count = 0
while num!=0:
num = num & (num-1)
count+=1
return count