My simple c++ solution in O(the number of ones)


  • 3
    H

    class Solution {
    public:
    int hammingWeight(uint32_t n) {

        int count=0;
        while (n){
            count++;   
            n&=n-1;
            
        }
        return count;
    }
    

    };


  • 4
    Y

    could you briefly explain what does n&n-1 means? I have no idea about that..


  • 0
    H

    (n&n-1) removes the least significant "1".
    for Example, let x =1010, so x-1= 1001 --> 1010 & 1001 = 1000 --> successfully removed the lowest set bit of x.
    This way we are looking for the 1's, not checking if the bit is 1 or 0.


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

    I tried in java, but 2147483648 did not pass. Is there a difference btw java & C++ here? Or my code has a bug? Thank you.


  • 0
    H

    I'm not familiar with java, but I can see you are considering an integer as your input, which has a maximum value of 2147483647 while the original input is uint32_t, which has a maximum value of (2^32)-1. Other than that I see no bugs


  • 0

    I have another solution only need two lines code

    class Solution {
    public:
    int hammingWeight(uint32_t n) {
    bitset<32> number(n);
    return number.count();
    }
    };


  • 0

    Thank you for your explaination!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.