Given a non-negative integer n
, your task is to count the number of set bits (1s) in its binary representation.
For example, the number 13
has binary form 1101
, which contains three set bits. The expected output is 3
.
#include <stdio.h>
int countSetBits(unsigned int n) {
int count = 0;
while (n) {
n = n & (n - 1); // remove rightmost set bit
count++;
}
return count;
}
int main() {
unsigned int number = 13;
printf("Number of set bits in %u: %d\n", number, countSetBits(number));
return 0;
}
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(1) | In the best case, the input number n is 0, which immediately satisfies the loop condition and returns the count without any iterations. |
Average Case | O(k) | The algorithm runs in O(k), where k is the number of set bits in the binary representation of n. This is because each iteration removes one set bit. |
Worst Case | O(log n) | In the worst case, all bits in n are set (e.g., n = 2^k - 1). Since there are log n bits in total, the loop runs log n times. |
Comments
Loading comments...