Loading...
墨滴

一平米江湖

2021/04/08  阅读:35  主题:奇点

奇点新主题

题目链接

剑指 Offer 15. 二进制中 1 的个数

题目描述

请实现一个函数,输入一个整数,输出该数二进制表示中 1 的个数。例如,把 9 表示成二进制是 1001,有 2 位是 1。因此,如果输入 9,则该函数输出 2。

示例 1:

输入:00000000000000000000000000001011
输出:3
解释:输入的二进制串 00000000000000000000000000001011 中,共有三位为 '1'

示例 2:

输入:00000000000000000000000010000000
输出:1
解释:输入的二进制串 00000000000000000000000010000000 中,共有一位为 '1'

示例 3:

输入:11111111111111111111111111111101
输出:31
解释:输入的二进制串 11111111111111111111111111111101 中,共有 31 位为 '1'

注意:本题与主站 191 题相同:https://leetcode-cn.com/problems/number-of-1-bits/

解题方案

思路 1

  • 标签:位运算
  • 整体思路:通过与 1 进行与运算,可以判断末位是不是 1,然后将数字进行无符号右移,最终当数字变成 0 时结束判断
  • n 表示数字的位数,时间复杂度: ,空间复杂度:

算法流程 1

  1. 首先注意力扣在代码模板中标注了 n 是一个无符号数,如果 n 可能是负数还需要另行讨论
  2. 初始化计数器 count 为 0
  3. 无符号数 n 与 1 进行与运算,如果 ,说明 n 的末位为 1,则 count 加一,如果 ,说明 n 的末位为 0,则 count 不变
  4. 判断完末位之后,将 进行无符号右移,更新末位
  5. 时,结束判断

代码 1

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        while(n != 0) {
            count += n & 1;
            n = n >>> 1;
        }
        return count;
    }
}

画解 1

offer15-1-1.png
offer15-1-2.png
offer15-1-3.png
offer15-1-4.png
offer15-1-5.png
offer15-1-6.png
offer15-1-7.png
offer15-1-8.png
offer15-1-9.png
offer15-1-10.png
offer15-1-11.png
offer15-1-12.png
offer15-1-13.png
offer15-1-14.png
offer15-1-15.png
offer15-1-16.png

<<< 左右滑动见更多 >>>

思路 2

  • 标签:位运算
  • 整体思路:通过与 的运算直接获取最后一位为 1 的位置,减少时间复杂度
  • n 表示数字中包含 1 的位数,时间复杂度: ,空间复杂度:

算法流程 2

  1. 首先注意力扣在代码模板中标注了 n 是一个无符号数,如果 n 可能是负数还需要另行讨论
  2. 初始化计数器 count 为 0
  3. 的运算可以直接获取到当前数字最后一位为 1 的位置,同时更新 n
  4. 时,结束判断

代码 2

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        while(n != 0) {
            count++;
            n = n & (n - 1);
        }
        return count;
    }
}

画解 2

offer15-2-1.png
offer15-2-2.png
offer15-2-3.png
offer15-2-4.png
offer15-2-5.png
offer15-2-6.png
offer15-2-7.png
offer15-2-8.png

<<< 左右滑动见更多 >>>

花絮

offer15-2.mp4
offer15-2.mp4

一平米江湖

2021/04/08  阅读:35  主题:奇点

作者介绍

一平米江湖