剑指offer--二进制中1的个数
题目描述 输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示
Java代码：
public class Solution {
public int NumberOf1(int n) {
String binary = Integer.toBinaryString(n);
char[] ch = binary.toCharArray();
int cnt = 0;
for ( int i = 0 ; i < ch.length ; i++){
if (ch[i] == '1'){
cnt++;
}
}
return cnt;
}
}C++代码思路 这题有3种思路。第一种：让n与1相与后判断是否为真，若为真，计数器cnt加一并将n右移1位直至n为0。这种思路受限于n是否为正数，若n为负数，那么每次右移最高位补1而非0，那么这会导致死循环。第二种：将第一种思路反过来思考，将flag = 1与n相与，若为真，cnt++，每次将flag左移一位，那么这种解法的时间复杂度与n的2进制数的位数一样，效率不高。第三种：一个数n如果减1，那么将这个2进制数从右向左的第一个“1”变成0，若这个1不是最低位，那么之后的所有位取反，而这个1左边的所有位保持不变。那么n与n-1相与可以使从右向左的第一个1与其之后的位变成0，那么这个2进制数有几个1，只需几次上述操作即可。
C++代码：
class Solution {
public:
int NumberOf1(int n) {
int cnt = 0;
while(n){
cnt++;
n = (n-1)&n;
}
return cnt;
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读