In this blog post, I will teach you how to write C/C++ program to count set bits in an integer using Lookup Table.
For Example,
Input : n = 3 Output : 2 Binary representation of 3 is 0011 and has 2 set bits Here's a simple ASCII representation of 9 (an 8-bit integer): 7 6 5 4 3 2 1 0 (Bit position) +---+---+---+---+---+---+---+---+ | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | (Example bit values)
In our previous blog post, we have discussed many ways to count the total set bits including the naive solution and Brian Kernighan’s algorithm. Here we will primarily discus the how to count the set bits using the lookup table. This approach is very optimizing way to count set bits and time complexity is O(1) for it.
Let’s see the problem statements for this question.
Problem Statement: Given an integer n, count set bits in “n” using the lookup table.
Disclaimer: Try to solve the problem yourself first otherwise it would be not worth solving this problem.
Now let’s say how the lookup table approach is used to count the set bits for a given integer. We assume here the size of the integer is 4-Bytes. In lookup table approach each index of the table represent the total count of set bits. So, it’s not a good idea to create lookup table of size 232-1; it consumes a lot of memory.
Don’t worry, you can solve this problem using a simple trick. Below I am explaining this simple trick.
As you know each byte can have values ranging from 0 to 255. So, here trick is to break 32 bits into 8 bits of chunks. Now beside creating a huge lookup table you can create a small lookup table that can efficiently handle the count of set bits for each byte within the integer.
This lookup table have count of total set bits count for all possible value (from 0 to 255). It helps us to quickly retrieve the count of set bits for any byte value in constant time, without needing to any extra calculations.
Here is a simple representation of a lookup table that have the set bits count for the value range 0-255 (8 bits). It helps you to understand the logic to count set bits using the lookup table.
In the below table column header have the following meanings,
- Index: – Indicates the index of the lookup table array.
- Byte Value: – Indicates the decimal value of the byte.
- Binary Representation: – Indicates the binary representation of the byte.
- Count of Set Bits: – Indicates the count of set bits in the binary representation.
Index | Byte Value | Binary Representation | Count of Set Bits -------------------------------------------------------------- 0 | 0 | 00000000 | 0 1 | 1 | 00000001 | 1 2 | 2 | 00000010 | 1 3 | 3 | 00000011 | 2 4 | 4 | 00000100 | 1 5 | 5 | 00000101 | 2 6 | 6 | 00000110 | 2 7 | 7 | 00000111 | 3 8 | 8 | 00001000 | 1 9 | 9 | 00001001 | 2 10 | 10 | 00001010 | 2 11 | 11 | 00001011 | 3 12 | 12 | 00001100 | 2 13 | 13 | 00001101 | 3 14 | 14 | 00001110 | 3 15 | 15 | 00001111 | 4 16 | 16 | 00010000 | 1 17 | 17 | 00010001 | 2 18 | 18 | 00010010 | 2 19 | 19 | 00010011 | 3 20 | 20 | 00010100 | 2 21 | 21 | 00010101 | 3 22 | 22 | 00010110 | 3 23 | 23 | 00010111 | 4 24 | 24 | 00011000 | 2 25 | 25 | 00011001 | 3 26 | 26 | 00011010 | 3 27 | 27 | 00011011 | 4 28 | 28 | 00011100 | 3 29 | 29 | 00011101 | 4 30 | 30 | 00011110 | 4 ... | ... | ... | ... 255 | 255 | 11111111 | 8
C program to count set bits in an integer using Lookup Table:
// C Program to count number of set bits
// using lookup table in O(1) time
#include<stdio.h>
// C Program to count number of set bits
// using lookup table in O(1) time
// Generate a lookup table for 32 bit integers
#define B2(n) n, n + 1, n + 1, n + 2
#define B4(n) B2(n), B2(n + 1), B2(n + 1), B2(n + 2)
#define B6(n) B4(n), B4(n + 1), B4(n + 1), B4(n + 2)
/*
Lookup table to store the total number of
bits set for each index in the table.
*/
const unsigned char lookuptable[256]
= { B6(0), B6(1), B6(1), B6(2) };
/*
Function to count the total
number of set bits in `n` using a lookup table
*/
unsigned int countSetBits(int n)
{
// first chunk of 8 bits from right
unsigned int count = lookuptable[n & 0xff] +
// second chunk from right
lookuptable[(n >> 8) & 0xff] +
// third and fourth chunks
lookuptable[(n >> 16) & 0xff]
+ lookuptable[(n >> 24) & 0xff];
return count;
}
// C Program to check function countSetBits
int main()
{
unsigned int i = 30;
printf("%d", countSetBits(i));
return 0;
}
Output: 4
C++ program to count set bits in an integer using Table:
// C++ Program to count number of set bits
// using lookup table in O(1) time
#include <iostream>
// Generate a lookup table for 32 bit integers
#define B2(n) n, n + 1, n + 1, n + 2
#define B4(n) B2(n), B2(n + 1), B2(n + 1), B2(n + 2)
#define B6(n) B4(n), B4(n + 1), B4(n + 1), B4(n + 2)
/*
Lookup table to store the total number of
bits set for each index in the table.
*/
const unsigned char lookuptable[256]
= { B6(0), B6(1), B6(1), B6(2) };
/*
Function to count the total
number of set bits in `n` using a lookup table
*/
unsigned int countSetBits(int n)
{
// first chunk of 8 bits from right
unsigned int count = lookuptable[n & 0xff] +
// second chunk from right
lookuptable[(n >> 8) & 0xff] +
// third and fourth chunks
lookuptable[(n >> 16) & 0xff]
+ lookuptable[(n >> 24) & 0xff];
return count;
}
int main()
{
unsigned int N = 255;
std::cout << countSetBits(N) << std::endl;
return 0;
}
Output: 8
Recommended Post
- How to set, clear or toggle a single bit in C/C++?
- Different ways to Count Set bits in an Integer.
- Macros for Bit Manipulation in C/C++.
- 5 Ways to Check if Two Integers have Opposite Signs.
- C Program to Find whether a given integer is a power of three or not.
- Operator Precedence And Associativity In C.
- Operators in C language