How to reverse bits of an integer in Java? [LeetCode Solution]

Hello guys In this Java article, you will learn how to reverse bits of an integer in Java. This is one of the common coding problems which is often asked during phone round of technical interviews on companies like Amazon, Google, and Microsoft. If you have appeared in any programming interviews then there is a good chance that you might have already seen this problem before. If you know the solution then you are in a good place but if you don't know the solution then don't disappoint as many experienced Java developers also struggle to solve this problem.

There are a couple of reasons for that, first not every Java developer is good with the bitwise operator, also understanding binary is not every programmer's cup of tea.

If you know binary and can find your way around different bitwise operation like AND, OR, XOR, and already read the Hacker Delight book then you are way ahead of many Java developers.  While the bitwise operator is not very common on Java application, you may need them on occasions like Coding interviews.

How to reverse bits of an integer in Java? [Example]

This is also one of the most popular LeetCode coding problem, which I haven't tried to submit my solution, you can submit it. You may need to make some changes as they also have test cases which are run against the solution.


How to reverse bits of an integer in Java

Anyway, let's focus on the coding problem in the hand, here is the problem statement and sample input  and output were given by the interviewer:

Statement:  Given an integer, reverse its bit sequence.
Sample Input:  00000000000000001111111111111110
Sample Output: 01111111111111110000000000000000

This is a crucial junction in coding interviews. The interviewer has given you the problem and now either you can start working on them or spend some time thinking about it and ask some relevant questions to the interviewer to show that you pay attention to details and have good knowledge of how things work inside the machine.

In this problem, It is necessary to know whether the decimal number being passed as input is of type byte (8-bit) or short (16-bit) or int (32-bit) or long (64-bit): because Java will discard leading zeroes. Yes, that's the devil in the detail which many Java programmers don't know.

For example, if number = 0011010, Java will trim it to 11010 and then cause the reverse to look like 1011.  Under such cases, your reverse algorithm may not work.  To keep things simple, the presented algorithm treats int (32-bit)  inputs.

If you are preparing for coding interviews then I also suggest you spend some time on Data Structure and algorithms. If you need recommendations to refresh your Data Structure and algorithm skills then I highly recommend checking out Data Structures and Algorithms: Deep Dive Using Java course on Udemy. It's a hands-on course and covers all essential data structures.





Java Program to Reverse bits of an Integer in Java

Here is my sample program to reverse bits of an integer in Java. In this program, I have used an interactive algorithm to reverse all the bits of a given integer number.

The number is passed as String from the console and that's why I have first converted the given String to Integer using Integer.parseInt() method.

In some cases, the Interviewer can also ask why you use that particular method and why not Integer.valueOf() so be prepared for that.  If you need an answer then you can also see this article.  After that, I pass that integer to our method called the reverseBits(int number) which reverse the bits one at a time.

/**
 * Java Program to reverse bit sequence of an integer.
 * input : 11111111111111111111111111111110
 * output : 01111111111111111111111111111111
 * 
 * @author WINDOWS 8
 */

public class ReverseBitsDemo {

    public static void main(String args[]) {

        System.out.println("Testing our reverseBits() method by"
                + " reversing ints in Java");
        String number = "000000000000000000000000000001";
        String expected = "10000000000000000000000000000000";
        
        int binary = Integer.parseInt(number, 2);
        int actual = reverseBits(binary);
        
        System.out.println("original number : " + number);
        System.out.println("reversed number : " 
                       + Integer.toBinaryString(actual));
        
        System.out.println(expected.equals(Integer.toBinaryString(actual)));

    }

    /*
     * Java method to reverse bits of specified integer
     */
    public static int reverseBits(int number) {
        int sizeOfInt = 32;
        int reverse = 0;
        for (int position = sizeOfInt - 1; position > 0; position--) {
            reverse += ((number & 1) << position);
            number >>= 1;
        }
        return reverse;
    }

}

Output
Testing our reverseBits() method by reversing ints in Java
original number : 000000000000000000000000000001
reversed number : 10000000000000000000000000000000
true


That's all about how to reverse bits of an integer in Java. This is the brute force solution and there are some clever solutions also possible using a bitwise operator. If you know one, feel free to post in the comments, that will help our readers a lot. I'll also be going to update the article with the top 3 clever solutions posted on comments.

This is also a popular LeetCode coding problem, which I haven't tried to submit my solution, you can and if you need more coding problems, particularly based upon bit manipulation then LeetCode has some good ones.  If you need some resources to level up your essential skills, the following courses are highly recommended.

Further Learning
Data Structures and Algorithms: Deep Dive Using Java
Algorithms and Data Structures - Part 1 and 2
Cracking the Coding Interview book
Grokking the Coding Interview: Patterns for Coding Questions


Other Programming Interview problems you may like to solve
  • How to reverse a String in place in Java? (solution)
  • How to find all permutations of a given String in Java? (solution)
  • 100+ Data Structure and Algorithms Problems (solved)
  • 10 Books to learn Data Structure and Algorithms (books)
  • How to check if two given Strings are Anagram in Java? (solution)
  • 10 Data Structure and Algorithms course to crack coding interview (courses)
  • How to find a missing value from an array containing 1 to 100? (solution)
  • How to check if the given String is palindrome or not in Java? (solution)
  • 101 Coding Problems and few tips for Tech interviews (tips)
  • When to use ArrayList vs LinkedList in Java? (answer)
  • 10 Free Data Structure and Algorithm Courses for Programmers (courses)
  • How to find the highest occurring word from a text file in Java? (solution)
  • How to check if a String contains duplicate characters in Java? (solution)
  • Top 5 Books to Learn Data Structure and Algorithms (books)
  • How to count the number of leaf nodes in a given binary tree in Java? (solution)
  • Top 5 Books for Programming and Coding Interviews (books)
  • How to count vowels and consonants in a given String in Java? (solution)
  • How to remove duplicate characters from String in Java? (solution)
  • How to check if a given number is prime or not? (solution)
  • 10 Free Courses to learn Data Structure and Algorithms (courses)
  • How to convert a linked list to an array in Java? (example)
  • My favorite free courses to learn data Structure in-depth (FreeCodeCamp)
  • How to find the first and last element of a linked list in Java? (solution)
  • How to search elements inside a linked list in Java? (solution)
  • What is the difference between LinkedList and ArrayList in Java? (answer)
  • 21 String coding Problems from Technical Interviews (questions)
  • How to reverse words in a given String in Java? (solution)

Thanks for reading this article so far. If you find this logic-based Java coding problem from Google and my explanation useful then please share it with your friends and colleagues. If you have any questions or feedback then please drop a note.

P. S. - If you are preparing for a programming job interview, then you must prepare for an all-important topic like data structure, String, array, etc. One course which can help you with this task is the Grokking the Coding Interview: Patterns for Coding Questions course. It contains popular coding interview patterns which will help you to solve most of the problems in your coding interviews.

1 comment:

  1. for (int position = sizeOfInt - 1; position > 0; position--) { reverse += ((number & 1) << position); number >>= 1; } return reverse;

    why we are taking &gt as we can use < in java and also please describe me in detail the processing flow of below code
    reverse += ((number & 1) << position); number >>= 1; } return reverse;

    ReplyDelete

Feel free to comment, ask questions if you have any doubt.