[Leetcode] Number of 1 Bits 一的位数

msup 发布于2019-08-14 12:21 / 2258人阅读

摘要：重复此步骤直到原数归零。注意右移运算符是算术右移，如果符号位是的话最高位将补，符号位是的话最高位补。当原数不为时，将原数与上原数减一的值赋给原数。因为每次减一再相与实际上是将最左边的给消去了，所以消去几次就有几个。

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(1) 空间 O(1)

思路

通过与运算符判断最低位/最高位是否是1，然后再右移/左移。重复此步骤直到原数归零。

注意

右移运算符是算术右移，如果符号位是1的话最高位将补1，符号位是0的话最高位补0。在C/C++中可以先将原数转换成无符号整数再处理，而在Java中可以使用无符号右移算术符>>>。当然，左移的解法就没有这个问题了。

代码

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

减一相与法 复杂度

时间 O(1) 空间 O(1)

思路

该方法又叫Brian Kernighan方法。当原数不为0时，将原数与上原数减一的值赋给原数。因为每次减一再相与实际上是将最左边的1给消去了，所以消去几次就有几个1。比如110，减去1得101，相与得100，消去了最左边的1。

代码

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

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

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

LeetCode[191] Number of 1 Bits

摘要：依次移位复杂度思路依次移动位数进行计算。代码利用性质复杂度，思路代码 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). Fo...

Scliang 2019-08-14 15:00 评论0 收藏0
[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 PHP题解--D57 762. Prime Number of Set Bits

摘要：题目链接题目分析对给定范围内的每个整数，返回其二进制形式下，数字出现的次数为质数的次数。思路由于题目固定了范围为，次方为千万。即最多只会出现次。存在则符合题目要求的数字，否则不计入该数字。最终代码若觉得本文章对你有用，欢迎用爱发电资助。 D57 762. Prime Number of Set Bits in Binary Representation 题目链接 762. Prime ...

Cobub 2019-07-01 12:45 评论0 收藏0
leetcode7:汉明距离

摘要：题目汉明距离是两个字符串对应位置的不同字符的个数，这里指二进制的不同位置例子我的解法先将，进行异位或运算再转化成二进制然后把去掉算出长度其他方法先算出不同位数，然后用右移运算符算出能右移几次来获取距离 1题目 The Hamming distance between two integers is the number of positions at which the corresp...

xeblog 2019-08-23 16:46 评论0 收藏0
leetcode190 Reverse Bits

摘要：思路一比特位移动将比特位逆转过来也就是将十进制数转化为二进制数，再从右往左获得每一位上的值，再将这个值添加至结果值中。根据分治思想，逆转个比特位等价于分别将每个比特位进行逆转。题目要求 Reverse bits of a given 32 bits unsigned integer. For example, given input 43261596 (represented in...

赵连江 2019-08-16 10:59 评论0 收藏0