191. 位1的个数


191. 位 1 的个数

编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)。

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int bits = 0;
        int mask = 1;
        for (int i = 0; i < 32; i++) &#123;
            if ((n & mask) != 0) &#123;
                bits++;
            &#125;
            mask <<= 1;
        &#125;
        return bits;

//作者:LeetCode
//链接:https://leetcode-cn.com/problems/number-of-1-bits/solution/wei-1de-ge-shu-by-leetcode/
    &#125;
&#125;

复杂度分析

时间复杂度:O(1) 。运行时间依赖于数字 n 的位数。由于这题中 n 是一个 32 位数,所以运行时间是 O(1) 的。
空间复杂度:O(1)。没有使用额外空间。


在二进制表示中,数字 n 中最低位的 1 总是对应 n−1 中的 0 。因此,将
n 和 n−1 与运算总是能把 n 中最低位的 1 变成 0 ,并保持其他位不变。
使用这个小技巧,代码变得非常简单。

Java

public class Solution &#123;
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) &#123;
       // public int hammingWeight(int n) &#123;
        int sum = 0;
        while (n != 0) &#123;
            sum++;
            n &= (n - 1);
        &#125;
        return sum;
    &#125;
&#125;

作者:LeetCode
链接:https://leetcode-cn.com/problems/number-of-1-bits/solution/wei-1de-ge-shu-by-leetcode/

二进制

N N-1 N&(N-1)
11 10 10
10 1 0
1100 1011 1000
1000 111 0
1011 1010 1010
1010 1001 1000
1000 111 0

文章作者:   future
版权声明:   本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 future !
 上一篇
108. 将有序数组转换为二叉搜索树 108. 将有序数组转换为二叉搜索树
108. 将有序数组转换为二叉搜索树难度简单 705给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。**高度平衡  **二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1
2021-03-01 future
下一篇 
1047. 删除字符串中的所有相邻重复项 1047. 删除字符串中的所有相邻重复项
1047. 删除字符串中的所有相邻重复项难度简单 122给出由小写字母组成的字符串 S,重复项删除操作会选择两个相邻且相同的字母,并删除它们。在 S 上反复执行重复项删除操作,直到无法继续删除。在完成所有重复项删除操作后返回最终的字符串。答
2021-03-01 future
  目录