DEV Community

Cover image for LeetCode Meditations: Reverse Bits
Eda
Eda

Posted on • Originally published at rivea0.github.io

LeetCode Meditations: Reverse Bits

The description for Reverse Bits is very brief:

Reverse bits of a given 32 bits unsigned integer.

There is also a note:

  • Note that in some languages, such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.

  • In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 2, the input represents the signed integer -3 and the output represents the signed integer -1073741825.

For example:

Input: n = 00000010100101000001111010011100
Output:    964176192 (00111001011110000010100101000000)

Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.
Enter fullscreen mode Exit fullscreen mode

Or:

Input: n = 11111111111111111111111111111101
Output:   3221225471 (10111111111111111111111111111111)

Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.
Enter fullscreen mode Exit fullscreen mode

It's also stated that The input must be a binary string of length 32 in the constraints.


Since we know that the input is a 32-bit integer, we can easily calculate the reversed position of each bit. For example, the 0th one corresponds to the 31st, the 1st to the 30th, and so on.

But we're doing bit manipulation, which means we have to deal with each bit one by one.
So, we can run a for loop to do just that. Each time, we can shift the bit by the index to the rightmost position, which can look like this:

n >>> idx
Enter fullscreen mode Exit fullscreen mode

Getting a bit (whether it is 0 or 1) can be easily done with an AND operation with 1.
If the bit is 0, 0 & 1 will result in 0.
If it's 1, 1 & 1 will result in 1.

Note
We can think of ANDing with 1 as the multiplicative identity (for example, 71=77 \cdot 1 = 7 ).

First, we can get the bit:

for (let i = 0; i < 32; i++) {
  let bit = (n >>> i) & 1;

  /* ... */
}
Enter fullscreen mode Exit fullscreen mode

Then, we need to put the bit we have in the reversed position. For that, we can left shift the bit, adding to the result as we do so:

let result = 0;

for (let i = 0; i < 32; i++) {
  /* ... */

  // put the bit to the reversed position
  let position = 31 - i;
  result += (bit << position);
}
Enter fullscreen mode Exit fullscreen mode

We need to return the result as a 32-bit integer, to do that, we can do a trick using the unsigned right shift operator:

function reverseBits(n: number): number {
  /* ... */

  return result >>> 0;
}
Enter fullscreen mode Exit fullscreen mode

And, the final solution looks like this:

function reverseBits(n: number): number {
  let result = 0;
  for (let i = 0; i < 32; i++) {
    let bit = (n >>> i) & 1;
    // put the bit to the reversed position
    let position = 31 - i;
    result += (bit << position);
  }

  return result >>> 0; // return as a 32-bit integer
}
Enter fullscreen mode Exit fullscreen mode

Time and space complexity

We know that the input and our result are always 32-bit integers (and, we don't have to use any other additional data structure), we run a loop 32 times as well, which is a fixed number, so both the time and space complexities are O(1)O(1) .


Up next, we'll take a look at Missing Number. Until then, happy coding.

Do your career a favor. Join DEV. (The website you're on right now)

It takes one minute and is worth it for your career.

Get started

Top comments (0)

This post blew up on DEV in 2020:

js visualized

🚀⚙️ JavaScript Visualized: the JavaScript Engine

As JavaScript devs, we usually don't have to deal with compilers ourselves. However, it's definitely good to know the basics of the JavaScript engine and see how it handles our human-friendly JS code, and turns it into something machines understand! 🥳

Happy coding!

👋 Kindness is contagious

Dive into an ocean of knowledge with this thought-provoking post, revered deeply within the supportive DEV Community. Developers of all levels are welcome to join and enhance our collective intelligence.

Saying a simple "thank you" can brighten someone's day. Share your gratitude in the comments below!

On DEV, sharing ideas eases our path and fortifies our community connections. Found this helpful? Sending a quick thanks to the author can be profoundly valued.

Okay