Brian Kernighan’s Algorithm: Count set bits in a number

Subtract one from n to flip bits after the rightmost set bit (including the rightmost set bit itself) and use n & (n-1) expression to clear the rightmost set bit of n until n becomes zero. The number of times we clear the rightmost set bit of n will be the set bit count.

Brian Kernighan’s algorithm summary card

Table of Contents

· Set and Unset Bit
· Bitwise AND Operator(&)
· Bitwise Right-Shift Operator(>>)
· Brute Force
  ∘ Graphical Explanation
  ∘ Code Implementation
    ∘ Complexity
    ∘ Golang
    ∘ Python
· Brian Kernighan's algorithm
  ∘ Graphical Explanation
  ∘ Code Implementation
    ∘ Complexity
    ∘ Golang
    ∘ Python

Set and Unset Bit

• set bit: a binary number is represented by 1
• unset bit: a binary number is represented by 0

22 in binary

Bitwise AND Operator(&)

Return 1 if both of bits are 1. Otherwise, return 0.

bitwise AND operator

Bitwise Right-Shift Operator(>>)

Shift a number to the right by 1 that is the same as dividing it by 2. The rightmost bit is deleted.

bitwise right-shift operator

Brute Force

191. Number of 1 Bits

Traverse through all bits in a number and count set bits if n & 1 == 1.

Graphical Explanation

brute force process

Code Implementation

Complexity

Time: O(log(n))
Space: O(1)
n: the total number of bits in a number

Golang

Python

Brian Kernighan’s algorithm

191. Number of 1 Bits

The idea is to subtract n by 1 to invert all the bits after the rightmost set bit of n (including the rightmost set bit). Then use n & (n-1) expression to clear the rightmost set bit. The number of times we clear the rightmost set bit until the number becomes zero will be the set bit count.

Graphical Explanation

Brian Kernighan’s algorithm process

Code Implementation

Complexity

Time: O(log(n))
Space: O(1)
n: the total number of set bits in a number

Golang

Python

You can access the source code here.

LeetCode Problem

• 191. Number of 1 Bits