beingsde
Sign In
Back to all DSA patterns
Bit Manipulation•Pattern: Bit Manipulation•Medium

Number of 1 bits (Hamming weight)

Problem Intuition & Objective

Count set bits in an integer efficiently.

Time ComplexityO(k) — k = number of set bits
Optimal
Space ComplexityO(1)
Memory Bounds
Optimal Algorithmic Approach

Brian Kernighan: n = n & (n-1) loop, counting iterations.

Core Invariants & Edge Cases

  • n & (n-1) clears the lowest set bit each iteration
  • Repeat until n = 0; count iterations
  • Brian Kernighan's Algorithm: O(number of set bits)
Previous ProblemSum of two integers without + or - operatorsNext Problem Search in rotated sorted array

System Design & Architecture Roadmap

Coding interviews are only 50% of the bar. Master High-Level Design, distributed systems, and Object-Oriented LLD.

60+ HLD QuestionsSharding, caching, and real-time distributed systems.27 LLD BlueprintsObject-oriented design patterns with class diagrams.SDE Quick ReferenceLatency numbers and database selection matrix.