Problem Description
Given a positive integer n, write a function that returns the number of set bits in its binary representation (also known as the Hamming weight).
Key Insights
- The task is to count the number of bits that are set to 1 in the binary representation of a given integer.
- The binary representation of an integer can be easily derived using bit manipulation techniques.
- There are various methods to count set bits, including:
- Iterating through each bit and checking if it is set.
- Using bit manipulation tricks such as Brian Kernighan's algorithm.
Space and Time Complexity
Time Complexity: O(log n) - The number of bits in the integer. Space Complexity: O(1) - Constant space is used regardless of the input.
Solution
The solution involves using bit manipulation to efficiently count the number of set bits. We can iterate through the bits of the integer n, checking each bit to see if it is set (i.e., equal to 1). We can achieve this by repeatedly checking the least significant bit (LSB) and shifting n to the right until it becomes 0. Each time we find a set bit, we increment our count.