What is the time and space complexity of Number of 1 Bits?

Time complexity: O(k) where k is the number of set bits. Space complexity: O(1).

Number of 1 Bits

Easy

Concept

Code

Loading editor...

Tap Analyze to see visualization

Click Analyze to visualize

See step-by-step execution, variables, and output

Variables

Run code to see variables

Output

Console output will appear here

Press Space to start•← → to step•? all shortcuts

Solution Guide: Number of 1 Bits

Approach

Use Brian Kernighan's algorithm: repeatedly clear the lowest set bit with n & (n - 1) and increment a counter. The loop runs exactly as many times as there are 1-bits.

Complexity Analysis

Time: O(k) where k is the number of set bits
Space: O(1)

Pattern

Brian Kernighan's Algorithm

Why It Works

Subtracting 1 flips all bits from the lowest set bit downward, so ANDing with the original clears exactly one set bit per iteration.

Updated Mar 2026