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 1: Set the loop counter to zero to start with
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:
1010
2
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).