How To Count Grade Out Of Develop Bits Or 1'S Of Integer Inward Java?

There are multiple ways to count lay out of 1's or develop bits inwards a integer lay out inwards Java. You tin utilization bitwise too flake shift operator past times your own, or, you lot tin utilization Java API to count lay out of develop bits. Java 1.5 added ii utility method called bitCount(int i) which returns lay out of 1's inwards your integer number, java.lang.Long cast has similar bitCount(long number) for long primitives. As I accept said earlier, Coding questions are of import constituent of whatsoever Java interview, too from that recursion too bitwise operations are most popular. Questions like, How to Swap ii numbers without temp variable or How to notice if a lay out is positive or negative are about of such questions, which you lot come across straight off too hence inwards diverse Java interviews.

In this Java tutorial, nosotros volition see, How to count lay out of develop bits inwards a number, for those who don't know what is develop bit, it's flake alongside value 1. For instance 2, which is binary 0010 has but 1 develop bit. On the other paw 10, which is 1010 in binary has ii develop flake or lay out of one's.

In most of cases, Interviewer volition inquire you lot to write a Java method without using API. In this article, nosotros volition come across pair of ways to calculate lay out of develop flake inwards a lay out on Java program.

Question:

Write a role alongside signature int countOnes(int a), method should render lay out of bits that are "set" or "on" inwards the binary representation of lay out provided. For example, countOne(10) should render 2, because binary format of 10, which is 1010 has ii bits on.

Counting lay out of develop flake using Java API method

Before writing your ain method to count lay out of 1's let's accept a await at Java API. Integer.bitCount(int number) too Long.bitCount(int number) are ii super tardily method which tin hand you lot count of lay out of develop bits inwards Java int or Java long primitive type. These methods are added from Java 1.5 too at that spot code is based on Hacker Delight book. Here is how bitCount(int i) looks similar cast java.lang.Integer cast :

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 tin see, its based on hacker delight, figure 5-2.

Simple way to count lay out of 1's inwards a Java Integer

Integral numbers represented past times int and long primitive are represented equally 2's complement binary format. Also worth knowing is size of int primitive is 32 flake too size of long is 64 bit. If nosotros instruct alongside simplest way, nosotros tin banking venture gibe LSB(Least Significant Bit) of lay out past times doing AND performance alongside 1. This tin hand us count of 1's if nosotros shift bits on correct direction. We tin utilization right shift without sign operator for that. Here is sample code to count lay out of 1's inwards Java integers :

 public static int countOne(int number){

        int count = 0;         for(int i =0; i<32; i++){             if( (number&1) == 1) {                 count++;             }             lay out = lay out >>> 1;         }         return count; }

Now if you lot write this method, Interviewer volition most probable inquire you lot well-nigh optimization. If you lot await closely, you lot tin come across that this method e'er loop 32 times, which is size of int. If you lot write similar method for long, it volition loop 64 times, tin you lot holler back what to optimize now? You tin optimize this loop. Instead of making loop proportional to size of bits, you lot tin move inwards proportional to lay out of develop bits. hither is a modified version :

public static int countSetBits(long number){         int count = 0;         while(number>0){             ++count;             lay out &= number-1;         }         return count; }

In this function, nosotros are using AND performance too lay out -1 to gradually cut lay out of 1's from master copy number. It means, this loop volition entirely runs four times, if lay out contains four develop bits. Here is consummate Java plan to count lay out of develop bits on numbers.

/**   * Java Program to count lay out of 1's inwards a integer.   * @author Javin Paul   */ public class CountSetBits {         public static void main(String args[]){         System.out.println("Java method to count lay out of 1's inwards a integer");         System.out.printf("Number of one's inwards %d is %d %n", 2, countOne(2));         System.out.printf("Number of one's inwards %d is %d %n", 3, countOne(3));         System.out.printf("Number of 1's inwards %d is %d %n", 10, countOne(10));                         //A curt too sugariness Java API fox to notice count of develop bits inwards a integer or long         System.out.println("Counting lay out of develop bits on integer too long using Java API");         int count = Integer.bitCount(2);         System.out.printf("Number of develop flake on %d is %d  %n", 2, count);         System.out.printf("Number of develop flake on %d is %d  %n", 3, Integer.bitCount(10));                 //One optimized way to count lay out of one's inwards a lay out inwards Java         //this method is proportional to lay out of develop bit's rather than flake size e.g. 32 for int, 64 for long         System.out.println("Another optimized Java method to count lay out of develop bits");         System.out.printf("Number of develop flake on %d is %d  %n", 2, countSetBits(2));         System.out.printf("Number of develop flake on %d is %d  %n", 3, countSetBits(3));     }             /**        * This method is non optimized, equally it iterates 32 times for integer numbers       * inwards all cases, tin you lot optimize it?       */     public static int countOne(int number){         int count = 0;         for(int i =0; i<32; i++){             if( (number&1) == 1) {                 count++;             }             lay out = lay out >>> 1;         }         return count;     }         /**       * Optimized version of previous one, loop is proportional to lay out of 1's       * instead flake size of number.       */     public static int countSetBits(long number){         int count = 0;         while(number>0){             ++count;             lay out &= number-1;         }         return count;     }        } Output: Java method to count lay out of 1's inwards a integer Number of one's inwards 2 is 1 Number of one's inwards three is 2 Number of 1's inwards 10 is 2 Counting lay out of develop bits on integer too long using Java API Number of develop flake on 2 is 1  Number of develop flake on 3 is 2  Another optimized Java method to count lay out of develop bits Number of develop flake on 2 is 1  Number of develop flake on 3 is 2 

That's all on How to count lay out of develop bits or 1's on integer lay out inwards Java. We accept seen 1 way of doing it using Java bitwise too flake shift operator too farther optimized that. By the way, at that spot tin live on multiple ways of doing this, using bitwise operator. If you lot honey playing alongside bits, you lot must banking venture gibe hackers delight, an awesome mass on flake twiddling.


Further Learning
The Coding Interview Bootcamp: Algorithms + Data Structures
Data Structures too Algorithms: Deep Dive Using Java
Algorithms too Data Structures - Part 1 too 2

Sumber https://javarevisited.blogspot.com/

Share this post