Counting Bits
Counting the Number of 1’s in Binary Representations of Numbers in a Range
In the world of programming, understanding binary numbers and efficiently processing them is a critical skill.
A common problem involves counting how many 1 bits are present in the binary representation of numbers within a given range.In this article, we will explore a solution to count the number of 1 bits in every number from 0 to n.
Problem Overview
You are given an integer n. Your task is to count the number of 1 bits (also known as set bits) in the binary representation of each number in the range [0, n].
The goal is to return an array output where output[i] represents the number of 1 bits in the binary representation of i.
Input
- An integer
n, where0 <= n <= 1000.
Output
- An array of integers, where each element
output[i]represents the number of1bits in the binary representation ofi.
Example 1
Input: n = 4
Output: [0,1,1,2,1]
We need to count the number of 1 bits in the binary representations of numbers from 0 to 4. Let’s convert these numbers to binary:
0in binary:0→ Number of1bits:01in binary:1→ Number of1bits:12in binary:10→ Number of1bits:13in binary:11→ Number of1bits:24in binary:100→ Number of1bits:1
Example 2
Input: n = 01111111111111111111111111111101
Output: 30
This is the binary representation of the integer 2147483645:
Binary: 01111111111111111111111111111101
Number of 1 bits: There are 30 ones in this binary number.
Approach to Solving the Problem
To solve this problem efficiently, let’s explore a few strategies:
Brute Force Approach:
- For each number
iin the range[0, n], convert it to binary and count the number of1bits. This can be done by converting the number to its binary representation (e.g., using Python’sbin()function) and counting the number of1bits (usingstr.count('1')). - This approach, while straightforward, is not the most optimized.
- For each number
Optimized Approach (Using Dynamic Programming):
- Instead of converting each number to binary individually, we can use dynamic programming to compute the result for each number based on the previous number.
- The key insight is that the number of
1bits in a numberiis related to the number of1bits ini // 2(i.e., the number obtained by right-shiftingiby 1 bit). Specifically:- If
iis even, theni // 2has the same number of1bits asi, and we just append0to its binary representation. - If
iis odd, theni // 2has one less1bit, but adding1toirestores the count.
- If
There are mainly 4 approach to solve this problem –
- Bit Manipulation – I
- Bit Manipulation – II
- In-Built Function
- Bit Manipulation (DP)
1. Bit Mask – I
Time & Space Complexity
- Time complexity: O(1)
- Space complexity: O(1)
Python
C++
Java
JavaScript
Python
class Solution:
def hammingWeight(self, n: int) -> int:
res = 0
for i in range(32):
if (1 << i) & n:
res += 1
return res
C++
class Solution {
public:
int hammingWeight(uint32_t n) {
int res = 0;
for (int i = 0; i < 32; i++) {
if ((1 << i) & n) {
res++;
}
}
return res;
}
};
Java
public class Solution {
public int hammingWeight(int n) {
int res = 0;
for (int i = 0; i < 32; i++) {
if ((1 << i & n) != 0) {
res++;
}
}
return res;
}
}
JavaScript
class Solution {
/**
* @param {number} n - a positive integer
* @return {number}
*/
hammingWeight(n) {
let res = 0;
for (let i = 0; i < 32; i++) {
if ((1 << i) & n) {
res++;
}
}
return res;
}
}
2. Bit Mask – II
Time & Space Complexity
- Time complexity: O(1)
- Space complexity: O(1)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
int hammingWeight(uint32_t n) {
int res = 0;
while (n != 0) {
res += (n & 1) ? 1 : 0;
n >>= 1;
}
return res;
}
};
Java
public class Solution {
public int hammingWeight(int n) {
int res = 0;
while (n != 0) {
res += (n & 1) == 1 ? 1 : 0;
n >>= 1;
}
return res;
}
}
Python
class Solution:
def hammingWeight(self, n: int) -> int:
res = 0
while n:
res += 1 if n & 1 else 0
n >>= 1
return resJavaScript
class Solution:
def hammingWeight(self, n: int) -> int:
res = 0
while n:
res += 1 if n & 1 else 0
n >>= 1
return res;
}
}3. Bit Mask (Optimal)
- Time complexity: O(1)
- Space complexity: O(1)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
int hammingWeight(uint32_t n) {
int res = 0;
while (n) {
n &= n - 1;
res++;
}
return res;
}
};
Java
class Solution:
def hammingWeight(self, n: int) -> int:
res = 0
while n:
n &= n - 1
res += 1
return res
Python
class Solution:
def hammingWeight(self, n: int) -> int:
res = 0
while n:
n &= n - 1
res += 1
return res
JavaScript
class Solution {
/**
* @param {number} n - a positive integer
* @return {number}
*/
hammingWeight(n) {
let res = 0;
while (n !== 0) {
n &= n - 1;
res++;
}
return res;
}
}
4. Built-In Function
Time & Space Complexity
- Time complexity: O(1)
- Space complexity: O(1)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
int hammingWeight(uint32_t n) {
return __builtin_popcount(n);
}
};
Java
public class Solution {
public int hammingWeight(int n) {
return Integer.bitCount(n);
}
}
Python
class Solution:
def hammingWeight(self, n: int) -> int:
return bin(n).count('1')
JavaScript
class Solution {
/**
* @param {number} n - a positive integer
* @return {number}
*/
hammingWeight(n) {
return n.toString(2).split('0').join('').length;
}
}
