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

$ 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.

Math Fundamentals18 sections · 842 units13h total

Open in Course

Count Bits - Implementation

Pseudocode solution

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$ (binary $1011$ ), the loop runs 3 times: $1011 \& 1010 = 1010$ , $1010 \& 1001 = 1000$ , $1000 \& 0111 = 0000$ . The count is 3. Time complexity: $O(k)$ where $k$ is the number of 1 bits. Space: $O(1)$ .