EasyFoundational
Count Set Bits in an Integer
- Time limit
- 1 s
- Memory limit
- 128 MB
- Estimated
- 10 min
- Bit Manipulation
Description
Given a non-negative integer n, return the number of bits set to 1 in its binary representation.
A bit is set when its value is 1. For example, the binary representation of 13 is 1101, which contains three set bits, so the answer is 3.
Your function must return the count only. Do not convert the integer to a string or use input/output operations.
Example 1: n = 13 returns 3.
Example 2: n = 0 returns 0.
Example 3: n = 255 returns 8.
Constraints
- 0 <= n <= 2^31 - 1
- The solution should run in O(number of bits) time or better.
- The function must use constant auxiliary space.
Sample cases
3Sample 1
Input
n = 0
Expected output
0
Sample 2
Input
n = 13
Expected output
3
Sample 3
Skills and languages
Concepts
- Bit Masks and Bit Tricks
- Number Bases and Digit Manipulation
Languages
- Python 3
Solve this problem
Create a free account to write, run and submit your solution.
- Write Python or Java in the browser, with your draft saved as you type
- Run your code on the examples as often as you like
- Submit to a sandboxed judge and see exactly which case failed
- Ask the AI mentor for a hint without being handed the answer