专栏首页赵俊的Java专栏LeetCode 191 Number of 1 Bits

LeetCode 191 Number of 1 Bits

位1的个数

题意

编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 1 的个数.

示例 1:

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

示例 2:

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

示例 3:

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

解法一

这里用到了位运算, 如数字 5, 二进制位为 101, 那么使用 & 运算, 和 1 进行与运算, 如:

  101
& 001
-----
  001

因为 1 只有最后一位为 1, 其他为都是 0, 所以他与任何数进行 & 运算后, 都只会保留这个数的最后一位, 如果运算结果还是 1, 说明这个树的最后一位是 1, 反之为 0.

那就很好解决了, 将 num & 1 后判断为 1, 则计数增加 1, 然后将右移一位 num >>= 1, 以此类推, 直到移位 32 次.

public class Solution {
    public int hammingWeight(int n) {
        int bits = 0;
        int mask = 1;
        for (int i = 0; i < 32; i++) {
            if ((n & mask) != 0) {
                bits++;
            }
            n >>= 1;
        }
        return bits;
    }
}

时间复杂度 O(1), 空间复杂度 O(1).

解法二

这个解法有些取巧, 在二进制表示中,数字 n 中最低位的 1 总是对应 n - 1 中的 0. 因此, 将 nn - 1 与运算总是能把 n 中最低位的 1 变成 0, 并保持其他位不变.

如对于数字 10, 和 10 - 1 进行 & 运算:

  1010
& 1001
------
  1000

接着对于二进制值 1000, 与 999 进行 & 运算:

  1000
&  999
------
  0000

由于每次都把最低位的 1 变为 0 了, 直到为 0, 那么这种个编程变了几次就说明有多少个 1.

public class Solution {
    public int hammingWeight(int n) {
        int sum = 0;
        while (n != 0) {
            sum++;
            n &= (n - 1);
        }
        return sum;
    }
}

时间复杂度 O(1), 空间复杂度 O(1). 但此算法效率相对比算法一效率高.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 黄蓉填充九宫格

    经过分析此题要点是边界处理,即向右上移动时,超出九宫格时的处理过程,右上冲突时向下移动不需要考虑边界问题,均未超出边界。

    一份执着✘
  • Java 动态代理初探

    对于使用过 Spring 的朋友, 应该都使用过 AOP, 那么今天我们来对 AOP 的原理: 动态代理 来一探究竟.

    一份执着✘
  • 落单的数

    一份执着✘
  • 关于位运算几道经典题目

    版权声明:本文为博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。

    张凝可
  • 13:大整数的因子

    13:大整数的因子 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 已知正整数k满足2<=k<=9,现给出长度最大为30位...

    attack
  • hdu1049

    @坤的
  • 从Bitmap中获取YUV数据的两种方式

    从Bitmap中我们能获取到的是RGB颜色分量,当需要获取YUV数据的时候,则需要先提取R,G,B分量的值,然后将RGB转化为YUV(根据具体的YUV的排列格式...

    雪月清
  • Codeforces Round #513 D. Social Circles(思维)

    题目链接:http://codeforces.com/contest/1060/problem/D

    Ch_Zaqdt
  • Zoj 3865 Superbot

    若羽
  • 【JVM】Int类型在栈中是否会被缓存?

    在写面试题系列文章中,多次涉及到JVM的内存分布情况,以及方法执行的过程中局部变量的存储变化情况。比如,在此前已经讲解过字符串常量池的初始化及使用情况。

    程序新视界

扫码关注云+社区

领取腾讯云代金券