Java count one bits

Integer.bitCount() method in Java with Examples

The bitCount() is a static method of the Integer class that counts the number of 1 bit in the two’s complement binary representation of the integer. It was introduced in Java 1.5, and this post will discuss the bitCount() method in detail.

• Method declaration – public static int bitCount(int i)
• What does it do? It will count the number of 1’s in the two’s complement binary representation of the number passed in the argument
• What does it return? It will return an int value denoting the number of 1’s in the two’s complement binary representation

What is the two’s complement of a number? We can easily count the number of 1 bit for a positive number, but what about negative numbers? How to calculate the bit count for negative numbers? For that, we first have to understand the 2’s complement.

This StackOverflow answer has explained 2’s complement quite well. We recommend reading it to get the basic idea of 2’s complement.

But here is a small conclusion on how we can calculate the 2’s complement of a number.

• Let’s say we have to calculate the 2’s complement of -6.
• First, write the binary representation of its corresponding positive integer +6.
• The binary representation of 6 is 110.
• Invert 0’s and 1’s. So, the new binary representation would be 001.
• Now, add 1 to it.
• After adding 1, we will get 010.

So, the 2’s complement of -6 would be 010. This is when we have only considered 3 bits. But if we have considered 32 bits, then 2’s complement of -6 would be 11111111111111111111111111111010.

Let’s first calculate the bit count for positive numbers

Let’s take an integer value = 6. The binary representation of 6 is 110, so the count of 1 bit should be 2.

Binary representation of i: 110 Number of 1 bits: 2 

Now, let’s calculate the bit count for the negative numbers

Let’s take the negative integer number = -6. The 2’s complement binary representation of -6 is 11111111111111111111111111111010. Thus the bit count for -6 would be 30.

Binary representation of i: 11111111111111111111111111111010 Number of 1 bit: 30 

Time Complexity of the bitCount() method

The time complexity of the Integer bitCount() method is O(1) as it performs only constant operations on the input. Below is the internal implementation of the bitCount() method –

public static int bitCount(int i) < // HD, Figure 5-2 i = i - ((i >>> 1) & 0x55555555); i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); i = (i + (i >>> 4)) & 0x0f0f0f0f; i = i + (i >>> 8); i = i + (i >>> 16); return i & 0x3f; >

Q- What if we passed a null Integer value to bitCount() argument?

It will throw a NullPointerException as illustrated by the below program.

Exception in thread "main" java.lang.NullPointerException: Cannot invoke "java.lang.Integer.intValue()" because "i" is null

Please visit this link to learn more about the Integer wrapper class of java and its other functions or methods.

We hope that you have liked the article. If you have any doubts or concerns, please feel free to write us in the comments or mail us at [email protected].

Источник

Java Integer bitCount() Method

Java bitCount() method belongs to the Integer class. This method is used to return a one-bit number into two’s complement binary form of the specified integer value and counts a number of set bits in a binary sequence.

This method takes an integer as a parameter and returns an integer too. For example, if the given input is 1000111110 than this method should return 6, as there are 6 set bits(1) in this input.

Syntax:

public static int bitCount(int i)

This method returns the one-bit number into two’s complement binary form of the integer number, hence its return type is also int.

Example 1:

Here, we are entering an integer number 365. The Integer.toBinaryString() method will convert the number into its equivalent binary string (101101101 for the integer 365). Then the converted binary number is passed through Integer.countBit() to count the number of bits.

import java.lang.Integer; public class StudyTonight < public static void main(String[] args) < int i = 365; int j = -365; System.out.println("Actual Number is " + i); // converting the number to its equivalent binary form with base 2 System.out.println("Binary conversion of" + i + " = " + Integer.toBinaryString(i)); //returning the number of one-bits System.out.println("Number of one bits = " + Integer.bitCount(i)); System.out.println("*******************"); System.out.println("Actual Number is " + j); System.out.println("Binary conversion of" + j + " = " + Integer.toBinaryString(j)); System.out.println("Number of one bits output"> 
Actual Number is 365 
Binary conversion of365 = 101101101 
Number of one bits = 6 
******************* 
Actual Number is -365 
Binary conversion of-365 = 11111111111111111111111010010011 
Number of one bits = 27
 
Example 2:
 
Here, we are taking an array of integers. The Integer.toBinaryString() method will convert the numbers in the array into its equivalent binary String. The binary string needs to be converted into Integer before passing it through the countBit() method, This is done through Integer.parseInt() method Then the converted binary number is passed through Integer.countBit() to count the number of bits.
 
import java.lang.Integer; public class StudyTonight < public static void main(String args[]) < int[] set = < 72, 78, 56, 89, 80, 66 >; try < for (int i = 0; i < 6; i++) < String b = Integer.toBinaryString(set[i]); //Converting the actual number to binary String int c = Integer.parseInt(b, 2); //Converting the binary String to binary integer of base 2 int d = Integer.bitCount(c); //Counting the set bits System.out.println("Actual number is " + set[i] + " binary sequence : " + b + ",number of set bits are : " + d); >> catch(Exception e) < System.out.println("Exception occurred.."); >> >
 
Actual number is 72 binary sequence : 1001000,number of set bits are : 2 
Actual number is 78 binary sequence : 1001110,number of set bits are : 4 
Actual number is 56 binary sequence : 111000,number of set bits are : 3 
Actual number is 89 binary sequence : 1011001,number of set bits are : 4 
Actual number is 80 binary sequence : 1010000,number of set bits are : 2 
Actual number is 66 binary sequence : 1000010,number of set bits are : 2
 
Example 3:
 
Here is a general example where the user can enter the number of his choice and get the desired output. The try and catch block is used for handling any exception taking place during the execution of the program. (For example, the user enters a String, etc. in place of the integer).
 
import java.lang.Integer; import java.util. * ; public class StudyTonight < public static void main(String[] args) < System.out.println("Enter number"); Scanner sc = new Scanner(System. in ); try < int i = sc.nextInt(); System.out.println("Actual Number is " + i); // converting the number to its equivalent binary form with base 2 System.out.println("Binary conversion of" + i + " = " + Integer.toBinaryString(i)); //returning the number of one-bits System.out.println("Number of one bits = " + Integer.bitCount(i)); >catch(Exception e) < System.out.println("Error!!"); >> >
 
Enter number 
67 
Actual Number is 67 
Binary conversion of 67 = 1000011 
Number of one bits = 3 
************************************** 
Enter number 
0x896 
Error!!
 
Live Example:
 
Here, you can test the live code example. You can execute the example for different values, even can edit and write your examples to test the Java code.
 
Источник
 
 How to Count number of Set bits or 1's of Integer in Java? Example 
 
There are multiple ways to count the number of 1's or set bits in an integer number in Java. You can use a bitwise and bit shift operator on your own, or, you can use Java API to count the number of set bits. Java 1.5 added two utility methods called bitCount(int i) which returns a number of 1's in your integer number, java.lang.Long class has a similar bitCount(long number) for long primitives. As I have said earlier, Coding questions are an important part of any Java interview, and from that recursion and bitwise operations are most popular.
 
Questions like, How to Swap two numbers without a temp variable or How to find if a number is positive or negative are some of such questions, which you see now and then in various Java interviews.
 
In this Java tutorial, we will see, How to count the number of set bits in a number, for those who don't know what is set bit is, it's a bit with value 1. For example, 2, which is binary 0010 has just one set bit. On the other hand, 10, which is 1010 in binary has two set bit or a number of one's.
 
In most cases, the Interviewer will ask you to write a Java method without using API. In this article, we will see a couple of ways to calculate the number of set bits in a number on a Java program. 
 
Question:
 
Write a function with signature int countOnes(int a) , the method should return a number of bits that are "set" or "on" in the binary representation of the number provided. For example, countOne(10) should return 2, because the binary format of 10, which is 1010 has two bits on it.
 
Counting number of set bit using Java API method- Example
 
Before writing your own method to count a number of 1's let's have a look at Java API. Integer.bitCount(int number) and Long.bitCount(int number) are two super easy methods that can give you a count of a number of set bits in Java int or Java long primitive type. These methods are added from Java 1.5 and their code is based on Hacker Delight book. Here is how bitCount(int i) looks like from java.lang.Integer class :
 
public static int bitCount(int i) < // HD, Figure 5-2 i = i - ((i >>> 1) & 0x55555555); i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); i = (i + (i >>> 4)) & 0x0f0f0f0f; i = i + (i >>> 8); i = i + (i >>> 16); return i & 0x3f; >
 
You can see, it's based on hacker delight, figure 5-2.
 
1. Simple way to count the number of 1's in a Java Integer
 
Integral numbers represented by int and long primitive are represented as 2's complement binary format. Also worth knowing is size of int primitive is 32 bit and size of long is 64 bit. If we go with simplest way, we can check LSB(Least Significant Bit) of number by doing AND operation with 1. This can give us count of 1's if we shift bits on the right direction.
 
We can use right shift without sign operator for that. Here is sample code to count number of 1's in Java integers :
 
public static int countOne( int number) < 
 
int count = 0; for(int i =0; i32; i++)< if( (number&1) == 1) < count++; > number = number >>> 1; > return count; >
 
Now if you write this method, the interviewer will most likely ask you about optimization. If you look closely, you can see that this method always loops 32 times, which is the size of int . If you write a similar method for long, it will loop 64 times, can you think of what to optimize now? You can optimize this loop. Instead of making a loop proportional to the size of bits, you can make it proportional to a number of set bits. here is a modified version :
 
public static int countSetBits(long number)< int count = 0; while(number>0)< ++count; number &= number-1; > return count; >
 
In this function, we are using AND operation and number -1 to gradually reduce the number of 1's from the original number. It means this loop will only run 4 times if the number contains 4 set bits. Here is a complete Java program to count a number of set bits on numbers.
 
/** * Java Program to count number of 1's in a integer. * @author Javin Paul */ public class CountSetBits < public static void main(String args[])< System.out.println("Java method to count number of 1's in a integer"); System.out.printf("Number of one's in %d is %d %n", 2, countOne(2)); System.out.printf("Number of one's in %d is %d %n", 3, countOne(3)); System.out.printf("Number of 1's in %d is %d %n", 10, countOne(10)); //A short and sweet Java API trick to find count of set //bits in a integer or long System.out.println("Counting number of set bits on integer and long using Java API"); int count = Integer.bitCount(2); System.out.printf("Number of set bit on %d is %d %n", 2, count); System.out.printf("Number of set bit on %d is %d %n", 3, Integer.bitCount(10)); //One optimized way to count number of one's in a number in Java //this method is proportional to number of set bit's rather //than bit size e.g. 32 for int, 64 for long System.out.println("Another optimized Java method to count number of set bits"); System.out.printf("Number of set bit on %d is %d %n", 2, countSetBits(2)); System.out.printf("Number of set bit on %d is %d %n", 3, countSetBits(3)); > /** * This method is not optimized, as it iterates 32 times for * integer numbers in all cases, can you optimize it? */ public static int countOne(int number)< int count = 0; for(int i =0; i32; i++)< if( (number&1) == 1) < count++; > number = number >>> 1; > return count; > /** * Optimized version of previous one, loop is proportional to number * of 1's instead bit size of number. */ public static int countSetBits(long number)< int count = 0; while(number>0)< ++count; number &= number-1; > return count; > > Output: Java method to count number of 1's in a integer Number of one's in 2 is 1 Number of one's in 3 is 2 Number of 1's in 10 is 2 Counting number of set bits on integer and long using Java API Number of set bit on 2 is 1 Number of set bit on 3 is 2 Another optimized Java method to count number of set bits Number of set bit on 2 is 1 Number of set bit on 3 is 2 
 
That's all on How to count a number of set bits or 1's on integer numbers in Java. We have seen one way of doing it using Java bitwise and bit shift operator and further optimized that. By the way, there can be multiple ways of doing this, using the bitwise operator. If you love playing with bits, you must check hackers delight, an awesome book on bit twiddling.
 
Источник