# Number of 1 Bits in Java

In this tutorial, we will learn about number of 1 bits in Java. The total bits in a number can be counted by using its binary representation. The bitCount() method of integer class of java.lang package returns the count of the number of one-bits in the two’s complement binary representation of an int value. The function is sometimes referred to as the population count. The Integer.bitCount() method is used for counting the number of set bits in an integer.

Examples:

Example1:

Input: n = 00000011000000001011

Output: 5

Explanation: Binary representation of 00000011000000001011 has five set bits.

Example2:

Input: n = 00001000011000000100000010000000110000

Output: 7

Explanation: Binary representation of 00001000011000000100000010000000110000 has seven set bits.

Example3:

Input: n = 11111101111111111111111111111111

Output: 31

Explanation: Binary representation of 11111101111111111111111111111111 has thirty one set bits.

Example 4:

Input: n = 6
Output: 2
Binary representation of 6 is 110 and has two set bits.

Example 5:

Input: n = 13
Output: 3

`Binary representation of 13 is 1101 and has three set bits.`

## Approach 1: To count the number of 1s

### ALGORITHM:

Step 2: Loop until number > 0
Step 2.1: Clear the least significant bit of number: number &= (number-1)
Step 2.2: Increment the loop counter by 1: count++;
Step 3: Return the loop counter

Filename: BitSequenceTest.java

`public class BitSequenceTest{    public static void main(String args[])    {        System.out.println("Testing our countBits() method with bit sequences");       // array of bit sequences are represented as strings        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);        }       }public static int countBits(int number){    if (number == 0)    {        return number;     }    int count = 0;    while (number != 0)    {        number &= (number - 1);        count++;    }    return count;    } }`

## Approach 2: Using java.lang.Integer.bitCount() method.

### ALGORITHM:

Step 1: Import the ‘java.lang.Integer’ package.

Step 2: Create a class called ‘Number’.

Step 3: Implement the ‘main’ method for the program execution.

Step 4: Declare an integer variable ‘a’.

Step 5: Initialize an integer variable with the value 10.

Step 6: Use Integer.toBinaryString(a) to translate an integer into its binary equivalent. The integer is changed into a binary string using this method.

Step 7: Use Integer.bitCount(a) to find the number of one bits, or set bits, in the binary representation.

Filename: BitCount.java

`import java.lang.Integer;public class BitCount           {            public static void main(String args[])            {                        int a = 10;                        // Convert integer number to binary format                        System.out.println(Integer.toBinaryString(a));                        // to print number of 1's in the number a                        System.out.println(Integer.bitCount(a));            }}`

Output:

`10102`

Time complexity: The time complexity of the program is O(1).

Space complexity: The space complexity of the program is O(log n).

## Approach 3: Using Brian Kernighan’s Algorithm

### ALGORITHM:

`Step 1: Initialize count: = 0.`
`Step 2: If integer n is not zero.`
`            Step 2.1: Do bitwise & with (n-1) and assign the value back to n: = n&(n-1).`
`            Step 2.2: Increment count by 1.`
`            Step 2.3: Go to step 2.`
` `
`Step 3: Else return count.`
` `
`Filename: CountSetBits.java`
`import java.io.*;`
`public class CountSetBits {`
`               /* Function to get no of set `
`               bits in binary representation `
`               of passed binary no. */`
`               static int countSetBits(int n)`
`               {`
`                               int count = 0;`
`                               while (n > 0) {`
`                                              n &= (n - 1);`
`                                              count++;`
`                               }`
`                               return count;`
`               }`
`               // driver program`
`               public static void main(String args[])`
`               {`
`                               int i = 9;`
`                               System.out.println(countSetBits(i));`
`               }`
`}`
` `
`Output: `
`2`
` `

Time complexity: The time complexity of the program is O(log n).

Space complexity: The space complexity of the program is O(1).