Good morning folks, In today's article, we are going to discuss one of the frequently asked bit manipulation based interview question, how do you count the number of set bits in given bit sequence? Bit Manipulation is an important topic on programming interview and a good programmer should have sufficient knowledge and skill to work with binary numbers. This kind of questions tests that skill of the programmer. Sometimes, it is also asked as for how to count the number of 1s (ones) in given number? Both are the same question because 1 is also known as set bit. For example, if given input is 1000110010 than your program should return 4, as three are only four set bits in this bit sequence.

There are many techniques to solve this problem and you might have your unique way as well, but let's explore some tried and tested a way to solve the problem. Btw, if you are the first time seeing this problem then I suggest you solve it yourself first because the best way to learn why a given algorithm works are to take a pencil and run through a few examples.

The solution presented in this article, you might have seen this already in hackers delight, runs through a loop and clears the lowest set bit of number during each iteration. This means you must know how to move bits and how to test a particular bit to find whether it's one or zero.

When no set bit is left in the number i.e. number becomes zero then the number of iterations is returned. That's your number of 1s or set bits in given bit sequence. Let's learn more about how this algorithm works.

Btw, I am assuming that you are familiar with binary numbers and understand how they are represented in Java e.g. in 2's complement form. I also assume that you know how to use bitwise operators like &, | and ^, I mean bitwise AND, OR and XOR operators, and bit shift operators like <<, >>, and >>> i.e. left shift operator, right shift operator, and right shift without sign operator.

If you are not familiar with them then I suggest you to first understand them by joining a comprehensive course like The Complete Java MasterClass, otherwise, it would be really difficult to understand and solve bit manipulation based problems.

##

As I said, there are many techniques to count a number of set bits in a given bit sequence, and one of them is starting a loop and in each step clear the lowest set bit,

Once all set bit will be cleared number will become zero and your loop should stop there. The number of iteration required is equal to a number of set bits in given number.

Here are

1. set the loop counter to zero to start with

2. loop until number > 0

-- clear the least significant bit of number : number &= (number-1)

-- increment the loop counter by 1 : count++;

3. return the loop counter

The second step is most important where we are using bitwise AND operator, to clear the least significant bit of number.

If you like to solve this problem another way, here is an alternate algorithm:

If you cannot understand it on your own, I suggest you read Hacker's delight at least once. One of the best book for Programmers interested in learning binary, and you know, there are only two types of programmers, one who know binary, and others who don't.

If you have difficulty reading this book, which is quite possible becuase it's not one of the easiest book to read, I also suggest to check a good data structure and algorithm course like Data Structures and Algorithms: Deep Dive Using Java which covers this topic in much more simpler language.

##

Here is our Java program which is based upon the first algorithm we have seen in this article. It's one of the simplest ways to count the number of set bits in given binary number in Java.

If you have any difficulty understanding this program, feel free to comment.

Btw, if you have any difficulty learning the algorithm, here is a nice slide which explains, step by step, how this bit manipulation algorithm works:

That's all about

Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures - Part 1 and 2

The Coding Interview Bootcamp: Algorithms + Data Structures

Related

P. S. - If you don't mind learning from free resources then you can also check this list of free algorithms courses to start with.

There are many techniques to solve this problem and you might have your unique way as well, but let's explore some tried and tested a way to solve the problem. Btw, if you are the first time seeing this problem then I suggest you solve it yourself first because the best way to learn why a given algorithm works are to take a pencil and run through a few examples.

The solution presented in this article, you might have seen this already in hackers delight, runs through a loop and clears the lowest set bit of number during each iteration. This means you must know how to move bits and how to test a particular bit to find whether it's one or zero.

When no set bit is left in the number i.e. number becomes zero then the number of iterations is returned. That's your number of 1s or set bits in given bit sequence. Let's learn more about how this algorithm works.

Btw, I am assuming that you are familiar with binary numbers and understand how they are represented in Java e.g. in 2's complement form. I also assume that you know how to use bitwise operators like &, | and ^, I mean bitwise AND, OR and XOR operators, and bit shift operators like <<, >>, and >>> i.e. left shift operator, right shift operator, and right shift without sign operator.

If you are not familiar with them then I suggest you to first understand them by joining a comprehensive course like The Complete Java MasterClass, otherwise, it would be really difficult to understand and solve bit manipulation based problems.

##
__The algorithm to count the number of 1s in Given Bit Sequence__

As I said, there are many techniques to count a number of set bits in a given bit sequence, and one of them is starting a loop and in each step clear the lowest set bit,Once all set bit will be cleared number will become zero and your loop should stop there. The number of iteration required is equal to a number of set bits in given number.

Here are

**exact steps of this algorithm**:1. set the loop counter to zero to start with

2. loop until number > 0

-- clear the least significant bit of number : number &= (number-1)

-- increment the loop counter by 1 : count++;

3. return the loop counter

The second step is most important where we are using bitwise AND operator, to clear the least significant bit of number.

If you like to solve this problem another way, here is an alternate algorithm:

**n = n & ~(n & ~(n-1));**If you cannot understand it on your own, I suggest you read Hacker's delight at least once. One of the best book for Programmers interested in learning binary, and you know, there are only two types of programmers, one who know binary, and others who don't.

If you have difficulty reading this book, which is quite possible becuase it's not one of the easiest book to read, I also suggest to check a good data structure and algorithm course like Data Structures and Algorithms: Deep Dive Using Java which covers this topic in much more simpler language.

##
__How to find the number of set bits in given binary number__

Here is our Java program which is based upon the first algorithm we have seen in this article. It's one of the simplest ways to count the number of set bits in given binary number in Java.If you have any difficulty understanding this program, feel free to comment.

/** * Java Program to count number of 1s in the given bit sequence * input : 1001010100111 * output : 7 * * @author WINDOWS 8 */ public class BitSequenceTest{ public static void main(String args[]) { System.out.println("Testing our countBits() method with bit sequences"); String[] input = {"000000", "001000", "101", "111", "1110001", "111110000"}; for(int i=0; i<input.length; i++){ int binary = Integer.parseInt(input[i], 2); int count = countBits(binary); System.out.println("bit sequence : " + input[i] + ", number of 1s : " + count); } } /** * Java method to calculate number of set bits in a given bit sequence. * * @param number is the integer but represent binary value * @return count of set bits in bit sequence */ public static int countBits(int number) { if (number == 0) { return number; } int count = 0; while (number != 0) { number &= (number - 1); count++; } return count; } } Output : Testing our countBits method with bit sequences bit sequence: 000000, number of 1s : 0 bit sequence : 001000, number of 1s : 1 bit sequence : 101, number of 1s : 2 bit sequence : 111, number of 1s : 3 bit sequence : 1110001, number of 1s : 4 bit sequence : 111110000, number of 1s : 5

Btw, if you have any difficulty learning the algorithm, here is a nice slide which explains, step by step, how this bit manipulation algorithm works:

That's all about

**how to count the number of set bits or 1s in the given bit sequence in Java**. If you are interested in learning more about how to work with bits and bytes in Java, I strongly suggest you join a good course on Algorithms like Algorithms and Data Structures - Part 1 and 2 one of the best books to learn binary manipulation. It contains many essential tricks to deal with bit sequence.**Further Learning**Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures - Part 1 and 2

The Coding Interview Bootcamp: Algorithms + Data Structures

Related

**Bit Manipulation and Data Structure Algorithms tutorials**on Java- How to check if a number is a power of two in Java? (answer)
- How to find GCD of two numbers in Java? (answer)
- How to check if a given number is even or odd in Java? (answer)
- How to swap two integers without using temp variable? (trick)
- The difference between bitwise and bit-shift operator in Java? (answer)
- How to add two numbers without using the arithmetic operator in Java? (tip)
- What is the difference between left and right shift operator in Java? (answer)
- 100+ Data Structure and Algorithm Questions for Programmers (list)
- 75+ Coding Questions to crack any programming interviews (questions)
- 10 Data Structure and Algorithm courses for Interviews (courses)

P. S. - If you don't mind learning from free resources then you can also check this list of free algorithms courses to start with.

That's funny. I thought there were 10 kinds of programmer...

ReplyDeleteThis comment has been removed by the author.

ReplyDeletegreat explanation.

ReplyDeleteawesome work. keep it up!!!

Thanks!! guys

Delete