题目地址:https://leetcode.com/problems/number-of-1-bits/open in new window

Total Accepted: 88721 Total Submissions: 236174 Difficulty: Easy

题目描述

Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).

Example 1:

Input: 11
Output: 3
Explanation: Integer 11 has binary representation 00000000000000000000000000001011 

Example 2:

Input: 128
Output: 1
Explanation: Integer 128 has binary representation 00000000000000000000000010000000

题目大意

统计一个数字的二进制中有多少个1.

解题方法

右移32次

其实就是不断地右移。判断最后一位总共出现了多少次1.

刚开始没有AC的原因是java是没有无符号整数的,也就是说int的最高位是1的话会认为是负数,所以普通右移并且判断n==0会超时,判断n>0的话直接不运行。

还好java提供了不保持符号位的>>>。

>>是符号位保持不变的右移。

用左移的方法好像不用考虑这么多。

本来是想用n%2==1来判断是否最后一位是1的,效率太差,用n&1的方式可以加快最后一位计算时的速率。

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

1 2 3 4 5 6 7 8 9 10 11

AC:2ms

计算末尾的1的个数

LeetCode给出的另一种巧妙解法。

当n&(n-1)!=0时说明n中至少包含一个1.

通过不停的n=n&(n-1)的方法可以将最后的一个1消掉。

 

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

1 2 3 4 5 6 7 8

python代码如下:

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        res = 0
        while n:
            res += 1
            n &= n - 1
        return res

1 2 3 4 5 6 7 8 9 10 11

转成二进制统计1的个数

代码如下。

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        return bin(n).count("1")

1 2 3 4 5 6 7

使用mask

和原本的数字移动的方式没有太大区别,只不过用了个变量来看每位是不是1.

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        mask = 1 << 32
        res = 0
        while mask:
            if n & mask:
                res += 1
            mask >>= 1
        return res

1 2 3 4 5 6 7 8 9 10 11 12 13

DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有

本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发