#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/math-fundamentals/number-bases/count-bits-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/math-fundamentals/number-bases/count-bits-implementation

Repovive

Count Bits - Implementation - Number Bases | Math Fundamentals | Repovive

Repovive.

Count Bits - Implementation

Pseudocode solution

0 min

Here is the complete solution using the Brian Kernighan trick:


function hammingWeight(n)
    count := 0
    while n > 0
        n := n & (n - 1)    // Flip rightmost 1 bit to 0
        count := count + 1
    return count

For $n = 11$ n=11 (binary $1011$ 1011), the loop runs 3 times: $1011 \& 1010 = 1010$ 1011&1010=1010, $1010 \& 1001 = 1000$ 1010&1001=1000, $1000 \& 0111 = 0000$ 1000&0111=0000. The count is 3. Time complexity: $O(k)$ O(k) where $k$ k is the number of 1 bits. Space: $O(1)$ O(1).