191. Number of 1 Bits
Number of 1 Bits (LeetCode 191) is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Bit Manipulation Patterns pattern, in the Bitwise AND - Counting Set Bits (Hamming Weight) subpattern.
- Blind 75 · #71 of 75 · Bit Manipulation
- NeetCode 150 · #145 of 150 · Bit Manipulation
- NeetCode 250 · #242 of 250 · Bit Manipulation
How to solve Number of 1 Bits
Number of 1 Bits is a Hamming Weight problem, part of Bit Manipulation Patterns. Count number of 1 bits (Hamming weight) using bitwise AND operations.
Work towards the solution in these steps:
- Consider how you can analyze the binary representation of the number to count specific bits.
- Think about iterating through each bit position and checking whether that bit is set or not.
- Recall that bitwise AND operations can help isolate individual bits for inspection.
The reference solution runs in O(1) time and O(1) space.
The Number of 1 Bits solution and editorial walks through the full approach with reference code.
Problem statement
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).
Example 1:
Input: n = 11
Output: 3
Explanation:
The input binary string 1011 has a total of three set bits.
Example 2:
Input: n = 128
Output: 1
Explanation:
The input binary string 10000000 has a total of one set bit.
Example 3:
Input: n = 2147483645
Output: 30
Explanation:
The input binary string 1111111111111111111111111111101 has a total of thirty set bits.
Constraints:
- 1 <= n <= 231 - 1
Follow up: If this function is called many times, how would you optimize it?
Topics and companies
Topics: Divide and Conquer, Bit Manipulation.
Reported in interviews at Box, Cisco, Microsoft, Qualcomm.
How to practise Number of 1 Bits on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(1) time and O(1) space.
Open Number of 1 Bits in the code editor, or read the Number of 1 Bits editorial for a worked solution with its approach and complexity analysis.
Where Number of 1 Bits sits in the DSA pattern sheet
- Bit Manipulation Patterns pattern guide
- Bitwise AND - Counting Set Bits (Hamming Weight) subpattern
- The full DSA patterns sheet
Problems related to Number of 1 Bits
Other problems that use the same Bitwise AND - Counting Set Bits (Hamming Weight) and Bit Manipulation Patterns techniques:
- Power of Two — Easy, same subpattern
- Reverse Bits — Easy, same subpattern
- Bitwise AND of Numbers Range — Medium, same pattern
- Counting Bits — Easy, same pattern
- Find the Difference — Easy, same pattern
- Minimum Array End — Medium, same pattern
Number of 1 Bits FAQ
What is the LeetCode number of Number of 1 Bits?
Number of 1 Bits is LeetCode problem 191, rated Easy.
What pattern is used to solve Number of 1 Bits?
Number of 1 Bits is a Hamming Weight problem. It belongs to the Bit Manipulation Patterns pattern, in the Bitwise AND - Counting Set Bits (Hamming Weight) subpattern.
What is the time complexity of Number of 1 Bits?
The reference solution runs in O(1) time and O(1) space.
Which companies ask Number of 1 Bits?
Number of 1 Bits has been reported in interviews at Box, Cisco, Microsoft, Qualcomm.