题解 | #二进制中1的个数#
二进制中1的个数
http://www.nowcoder.com/practice/8ee967e43c2c4ec193b040ea7fbb10b8
描述
输入一个整数 n ，输出该数32位二进制表示中1的个数。其中负数用补码表示。
示例1
输入：10
返回值：2
说明：十进制中10的32位二进制表示为0000 0000 0000 0000 0000 0000 0000 1010，其中有两个1。
示例2
输入：-1
返回值：32
说明：负数使用补码表示 ，-1的32位二进制表示为1111 1111 1111 1111 1111 1111 1111 1111，其中32个1
解法一：最后一位和1与运算并右移
public class Solution {
public int NumberOf1(int n) {
int res = 0;
for (int i = 1; i <= 32; i++) {
// 最后一位和1进行 与运算
if ((n & 1 ) == 1) {
res++;
}
// 右移一位
n = n >> 1;
}
return res;
}
}
复杂度分析
- 时间复杂度O(N)
- 空间复杂度O(1)
解法二：n 和 n-1 的与操作，让1变0
- 利用 n 从右往左数第一个1，对应的 n-1 一定是0
- 让 n &（n-1）=0 ，把1 变成0
- 每次n &（n-1）会减少 n中最后一个1，对前面的1没有影响
- 记录 与的次数，即是1的个数
public class Solution {
public int NumberOf1(int n) {
int res = 0;
// 1.直到n=0时停止
while (n != 0) {
// 2.每次把n的二进制最后一个1变成0
n = (n & (n - 1));
res++;
}
return res;
}
}
