0 ms C solution!


  • 20
    T
    int hammingWeight(uint32_t n) {
        int count = n ? 1 : 0;
        while(n &= (n-1)) count++;
        return count;
    }
    

    Edit: Updated code to make it more readable. Still 0 ms.


  • 0
    G

    i couldnot understand the logic could you please explain me briefly.


  • 0
    A

    Some issues with formatting my comment see my reply below :)


  • 11
    A

    This is a reply to gvikram:

    Todd was going for minimal line usage which creates some confusion.
    the exact same implementation in a little more human readable format is:

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

    when n=0 the while loop exits.
    much like how n++ = n+1
    n&=1 is the same as n=n&(n-1)
    n&=(n-1)
    As to how it works:

    say n is 5
    count = 0
    5 = 101
    n-1 is 4
    4 = 100
    101 & 100 = 100 
    count = 1;
    n=100
    3=  11
    100 & 11 = 0
    count = 2
    

    exit loop. Success! Every iteration of this loop removes a 1 from the binary value of your number. It;'s very clever

    Another example:

    n=7
    count = 0;
    7=111
    6=110
    111&110=110
    count = 1;
    n   =110
    n-1=101
    110&101 = 100
    count =2
    n =100
    n-1=11
    100&11=0
    count =3
    Success!
    

    Very clever :)


  • 0
    X

    Thanks for your brilliant solution and patient illustrations.


Log in to reply
 

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