[数据结构与算法]牛客刷题---JZ15 二进制中1的个数

JZ15 二进制中1的个数

描述

输入一个整数 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=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;
    }
}