Count set bits in an integer
Count how many 1 bits appear in the binary representation of a non-negative integer.
Course progress
Problem 74 of 100
Example → approach → runnable solution
Worked example
See the problem in action
Trace a concrete input through to the verified result.
Example input
number = 45
Expected output
4
What is happening?
45 is 101101 in binary. That representation contains four 1 bits.
Solution strategy
Build the right mental model
Repeatedly clear the lowest set bit with value AND value minus one, counting how many operations are needed to reach zero.
Core concepts
bitwise operations · loops
Complexity
Time O(k), space O(1), where k is the number of set bits.
Runnable solution
Learn from working code
Compare languages, copy the code, or open it in the compiler.
Complete C# solution for count-set-bits
using System;
class Program
{
static int CountSetBits(int number)
{
if (number < 0) throw new ArgumentOutOfRangeException("number");
int count = 0;
while (number != 0)
{
number &= number - 1;
count++;
}
return count;
}
static void Main()
{
Console.WriteLine(CountSetBits(45));
}
}Knowledge check
Questions students often ask
What is the main idea behind count set bits in an integer?
Repeatedly clear the lowest set bit with value AND value minus one, counting how many operations are needed to reach zero.
What is the time and space complexity of this solution?
Time O(k), space O(1), where k is the number of set bits.
Do all language tabs solve the same problem?
Yes. Every program uses the same example and produces the verified output shown on this page. The syntax and a few language-specific data structures differ.