LeetCode[191] Number of 1 Bits

Scliang 发布于2019-08-14 15:00 / 3346人阅读

摘要：依次移位复杂度思路依次移动位数进行计算。代码利用性质复杂度，思路代码

LeetCode[191] Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of ’1" bits it has (also known as the Hamming weight).
For example, the 32-bit integer ’11" has binary representation 00000000000000000000000000001011, so the function should return 3.

依次移位

复杂度
O(N), O(1), N = number of bits in the interger

思路
依次移动位数进行计算。
The unsigned right shift operator ">>>" shifts a zero into the leftmost position, while the leftmost position after ">>" depends on sign extension.
So when the first bit is 1, if use >>, 1 will always be there, then the loop will never end.

代码

public int hammingWeight(int n) {
    int cnt = 0;
    while(n != 0) {
        if((n & 1) == 1) {
            cnt ++;
        }
        // must use unsigned operation
        n = n >>> 1;
    }
    return cnt;
}

利用性质 n & (n - 1)

复杂度
O(N), O(1)， N = number of 1 bits in the number

思路
consider n & (n - 1) always eliminates the least significant 1.

代码

public int hammingWeight(int n) {
    int cnt = 0;
    // loop times = number of 1"s in the n
    while(n != 0) {
        n = n & (n - 1);
        cnt ++;
    }
    return cnt;
}

云服务器 GPU云服务器 Bits jquery191 cdn-191磁力 LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65226.html

[LeetCode] 191. Number of 1 Bits

Problem Number of 1 BitsWrite a function that takes an unsigned integer and returns the number of ’1 bits it has (also known as the Hamming weight). Example For example, the 32-bit integer 11 has bina...

gitmilk 2019-08-16 12:31 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月汇总（55 题攻略）

摘要：微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目录不...

warmcheng 2019-08-26 10:09 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0
[Leetcode] Number of 1 Bits 一的位数

摘要：重复此步骤直到原数归零。注意右移运算符是算术右移，如果符号位是的话最高位将补，符号位是的话最高位补。当原数不为时，将原数与上原数减一的值赋给原数。因为每次减一再相与实际上是将最左边的给消去了，所以消去几次就有几个。 Number of 1 Bits Write a function that takes an unsigned integer and returns the numbe...

msup 2019-08-14 12:21 评论0 收藏0