Number of 1 Bits


  • 0

    Click here to see the full article post


  • 0
    S

    The Second Method here should be attributed to Brian Kernighan, since he gave the same.


  • 0
    D

    According to https://graphics.stanford.edu/..., the earliest publication of the 2nd method is due to Peter Wegner (from CACM 3 [1960], p.322). Also discovered independently by Derrick Lehmer and published in 1964.

    The Control Data 6000/7000 series machines (with their 60-bit words and 1s-complement arithmetic) had an instruction to count bits set that they called "population count."


  • 0
    N

    In Python it could be pretty straightforward (still not so efficient) one-liner: bin(n).count('1')


  • 0
    W

    Some in Java here. return Integer.bitCount(n) could work.


  • 0
    W

    'Same'... Sry about that


  • 0
    K

    One of the testcases is 2147483648 which is out of int range. How is this being passed to the function that accepts an "int" parameter?


  • 0

    the number is an unsigned int,right?do{
    if(n%2==1)
    count++;
    n=n/2;
    }while(n!=0);

    this kind of method is wrong? when running the code ,one of the testcases is 2147483648,why?


  • 0
    L

    C++ code as below:

    class Solution {
    public:
    int hammingWeight(uint32_t n) {
    int cou = 0;
    while(n) {
    if (n & 1) ++cou;
    n >>= 1;
    }
    return cou;
    }
    };

    The run time is logn, and the space cost only 1.


  • 0

    For case 315,

    input: None
    output: 0
    expected output: 1

    what is None in JS/Java? I try both lang without undefined and null, but the same error exists


  • 0
    S

    My solution:

    return Integer.bitCount(n ^ 0);

    was accepted


  • 0
    S

    A simple
    return Integer.bitCount(n);
    was also accepted as WTYJack said.


  • 0
    This post is deleted!

  • 0
    N

    How is this constant time complexity? Wouldn't it be O(n)?


  • 0
    G

    There is an even easier bitwise trick which is constant time:
    int hammingWeight(uint32_t n)
    {
    n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
    n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f);
    n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff);
    n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff);
    return (n);
    }


  • 0
    E

    my Python solution:
    x = 0
    for i in list(bin(n))[2:]:
    x += i
    return x


  • 0
    N

    class Solution {
    public:
    int hammingWeight(uint32_t n) {
    int i=0;
    while (n)
    {
    n &= (n-1);
    i++;
    }
    return i;
    }
    };


  • 0
    C

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


  • 0
    E

    Approach #2 dramatically reduces the readability while does no good to space and runtime complexity.


  • 0
    G

    @Eroica I agree about the readability, but the improvement on runtime could be noticed if this function would be applied to lots of integers with only a few bits set. It`s a specific case, but maybe worth mentioning in an interview.


Log in to reply
 

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