Solution Review: Count Set Bits Or Number of 1 bit's
We saw an algorithm to solve this problem in the previous lesson. Let’s see how to solve this more efficiently using Briann’s Algorithm. This is a faster execution than the previous naive approach.
Table of Contents
This review provides a detailed analysis to solve the count set bits.
Solution review
We saw an algorithm to solve this problem in the previous lesson. Let’s see how to solve this more efficiently using Briann’s Algorithm.
Brian Kernighan’s algorithm
This is a faster execution than the previous naive approach.
In this approach, we count only the set bits. So,
- The while loop runs twice if a number has 2 set bits.
- The while loop runs four times if a number has 4 set bits.
For example, let us consider the example n = 125
and calculate using this algorithm.
Java
class CountSetBit {
private static int helper(int n) {
int count = 0;
while (n > 0) {
n &= (n - 1);
count++;
}
return count;
}
public static void main(String[] args) {
int number = 125;
System.out.println("SetBit Count is : " + helper(number));
}
}
Python
def CountSetBits(n):
count=0
while n > 0:
n &= (n - 1)
count+=1
return count
number=125
print('SetBit Count is : ', CountSetBits(number))
JavaScript
const CountSetBits = (n) => {
let count = 0;
while (n > 0) {
n &= (n - 1);
count++;
}
return count;
}
console.log ('SetBit Count is', CountSetBits (125));
C++
#include <iostream>
using namespace std;
int helper(int n){
int count = 0;
while (n > 0){
n &= (n - 1);
count++;
}
return count;
}
int main() {
int number = 125;
cout << "SetBit count is : " << helper(number);
}
TypeScript
export const CountSetBits = (n: number): number => {
let count: number = 0;
while (n > 0) {
n &= (n - 1);
count++;
}
return count;
}
console.log('SetBit Count is', CountSetBits(125));
Explanation
n = 40 => 00000000 00000000 00000000 00101000
n - 1 = 39 => 00000000 00000000 00000000 00100111
-----------------------------------------------------------
(n & (n - 1)) = 32 => 00000000 00000000 00000000 00100000
-----------------------------------------------------------
Now n is 32, so we can calculate this to:
n = 32 => 00000000 00000000 00000000 00100000
n - 1 = 31 => 00000000 00000000 00000000 00011111
-----------------------------------------------------------
(n & (n - 1)) = 0 => 00000000 00000000 00000000 00000000
-----------------------------------------------------------
Time and space complexities
Time complexity: O(Set Bit count)
/ O(1)
in simple terms
The time taken is proportional to set bits in binary representation.
So, the time taken is O(SetBit Count).
The run time depends on the number of set bits in n. In the worst case, all bits in n are 1-bits. In the case of a 32-bit integer, the run time is O(32)
or O(1)
.
Space complexity: O(1)
extra space
The space complexity is O(1)
. No additional space is allocated.
Lookup table approach
This approach is considered one of the fastest, using a lookup table.
Why is the below algorithm faster than previous approaches?
- Lookup-based approach.
- This approach requires a
O(1)
time solution to count the set bits. - However, this requires some preprocessing.
- So, we divide our 32-bit input into 8-bit chunks, with four chunks.
- We have 8 bits in each chunk. Then the range is from
0 - 255
(0 to 27). - So, we may need to count set bits from
o
to255
in individual chunks.
Java
class CountSetBit {
private static int helper(int n) {
int[] table = new int[256];
table[0] = 0;
for (int i = 1; i < 256; i++) {
table[i] = (i & 1) + table[i >> 1]; // i >> 1 equals to i/2
}
int res = 0;
for (int i = 0; i < 4; i++) {
res += table[n & 0xff];
n >>= 8;
}
return res;
}
public static void main(String[] args) {
int number = 125;
System.out.println("SetBit Count is : " + helper(number));
}
}
Python
def CountSetBits(n):
table = [0] * 256
table[0] = 0
for i in range(1, 256):
table[i] = (i & 1) + table[i >> 1]
res = 0
for i in range(4):
res += table[n & 0xff]
n >>= 8
return res
n=125
print ('SetBit Count is', CountSetBits (n))
JavaScript
const CountSetBits = (n) => {
const table = [];
table[0] = 0;
for(let i = 1; i < 256; i++) {
table[i] = (i & 1) + table[i >> 1]; // i >> 1 equals to i/2
}
let res = 0;
for (let i = 0; i < 4; i++) {
res += table[n & 0xff];
n >>= 8;
}
return res;
}
console.log ('SetBit Count is', CountSetBits (125));
C++
#include <iostream>
using namespace std;
int helper(int n){
int table[256];
table[0] = 0;
for (int i = 1; i < 256; i++){
table[i] = (i & 1) + table[i >> 1]; // i >> 1 equals to i/2
}
int res = 0;
for (int i = 0; i < 4; i++) {
res += table[n & 0xff];
n >>= 8;
}
return res;
}
int main() {
int number = 125;
cout << "SetBit count is : " << helper(number);
return 0;
}
TypeScript
export const CountSetBits = (n: number): number => {
const table: number[] = [];
table[0] = 0;
for (let i = 1; i < 256; i++) {
table[i] = (i & 1) + table[i >> 1]; // i >> 1 equals to i/2
}
let res: number = 0;
for (let i: number = 0; i < 4; i++) {
res += table[n & 0xff];
n >>= 8;
}
return res;
}
console.log('SetBit Count is', CountSetBits(125));
Explanation
In the code snippet below, we store the set bit count value in the lookup table.
table[0] = 0;
for (i = 1; i < 256; i++) {
table[i] = (i & 1) + table[i >> 1]; // i >> 1 equals to i/2
}
We are initializing the table with the set bit count for each i
th place.
Algorithm:
- Initialize
table[0]
with0
. - Loop through, in the range from 1 to 256
- for
i = 1
,table[1] = (1&1) + table[1/2]
=>table[1] = 1 + table[0]
=>table[1] = 1.
table[2] = (2&1) + table[2/2]
=>table[2] = 0 + table[1];
=>table[2] = 1
.table[3] = (3&1) + table[3/2]
=>table[3] = 1 + table[1];
=>table[3] = 2
. so on…
- Initialize int res = 0.
- Loop through, in the range from 0 to 3
- To check on each of the 4
8-bit
chunks usingres += table[n & 0xff]
; - Shift
n
by 8 bits (n >>= 8
). we do this to get the second last 8 bits… - End loop.
- To check on each of the 4
- Return
res
.
Time and space complexities
Time complexity: O(1)
in simple terms
This requires an O(1)
time solution to count the set bits in each of the 8-bit chunks.
Space complexity: O(1)
extra space
The space complexity is O(1)
. No additional space is allocated.
👨🏻💻 Gopi Gorantala Newsletter
Join the newsletter to receive the latest updates in your inbox.