Number of 1 Bits

Easybit-manipulation
Category: Bit Manipulation
Companies that ask this question:
AmazonAppleFacebookGoogle
LeetCode →

Approach

Number of 1 Bits

Approach

Use bit manipulation to count set bits.

Algorithm

  1. Initialize count to 0
  2. While n is not zero:
    • Add rightmost bit (n & 1) to count
    • Right shift n by 1 position
  3. Return count

Complexity

  • Time: O(log n) or O(32) for 32-bit integers
  • Space: O(1) - constant space

Key Insights

  • n & 1 extracts rightmost bit
  • Right shift processes each bit position
  • Alternative: n & (n-1) clears rightmost 1 bit (faster)

Solution

java
1public class Solution {
2    public int hammingWeight(int n) {
3        int count = 0;
4        
5        while (n != 0) {
6            count += n & 1;
7            n >>>= 1;
8        }
9        
10        return count;
11    }
12}
Loading visualizer...