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

$ curl repovive.com/roadmaps/fundamental-algorithms/bit-manipulation/counting-set-bits

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

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

$ curl repovive.com/roadmaps/fundamental-algorithms/bit-manipulation/counting-set-bits

Repovive

Counting Set Bits - Bit Manipulation | Fundamental Algorithms | Repovive

Repovive.

Fundamental Algorithms8 sections · 294 units2h total

Open in Course

Counting Set Bits

Count the number of 1s in binary.

Problem: Count the number of $1$ bits in an integer (population count).

Method 1: Loop and check each bit. $O(\log n)$ .

count = 0
while n > 0:
    count = count + (n & 1)
    n = n >> 1
return count

Method 2: Clear lowest set bit repeatedly. $O(k)$ where $k$ is the number of $1$ bits.

count = 0
while n > 0:
    n = n & (n - 1)
    count = count + 1
return count

Method 3: Built-in functions.

C++: __builtin_popcount(n)
Python: bin(n).count('1')
Java: Integer.bitCount(n)

Built-ins use hardware instructions and are fastest.