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? It is also asked as how to count the number of 1s 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. Best way to learn why a given algorithm works is to take a pencil and run though 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. When no set bit is left (i.e. number==0) than 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.

##

As I said, there are many techniques to count number of set bits in a given bit sequence, and one of them is start 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 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

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 by your own, I suggest you to 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, once who knows binary, and others who doesn't.

Here is a nice slide of algorithm to understand the technique better:

##

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

That's all about

The Coding Interview Bootcamp: Algorithms + Data Structures

Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures - Part 1 and 2

Related

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

As I said, there are many techniques to count number of set bits in a given bit sequence, and one of them is start 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 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

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 by your own, I suggest you to 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, once who knows binary, and others who doesn't.

Here is a nice slide of algorithm to understand the technique better:

##
__How to find 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 way to count number of set bits in given binary number in Java. If you have any difficult 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

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 on learning more about how to work with bits and bytes in Java, I strongly suggest you to read Hacker's delight one of the best book to learn binary manipulation. IT contains many essential tricks to deal with bit sequence.**Further Learning**The Coding Interview Bootcamp: Algorithms + Data Structures

Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures - Part 1 and 2

Related

**bit manipulation tutorials**on Java- How to check if a number is 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 arithmetic operator in Java? (tip)
- What is difference between left and right shift operator in Java? (answer)

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