LeetCode Notes: Reverse Bits

#leetcode

Question

Reverse bits of a given 32 bits unsigned integer.

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Ā above, the input represents the signed integer -3Ā and the output represents the signed integer -1073741825.

Follow up:

If this function is called many times, how would you optimize it?

Example 1:

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.

Example 2:

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.

Constraints:

  • The input must be a binary string of length 32

Solution One

Analysis:

Simple and ordinary thinking, manipulation of strings and arrays.

  1. Convert decimal numbers to binary numbers
  2. Split into an array, reverse this array and merge it into a new string, this new string is the reversed binary string we are looking for
  3. Prefix 0 for binary strings
  4. Finally, the result is converted into a decimal number and output

Code:

/**
  * @param {number} n - a positive integer
  * @return {number} - a positive integer
  */
var reverseBits = function(n) {
     // Converted to an array, reversed, and then converted back
     let nr = n.toString(2).split('').reverse().join('');

     // prefix 0
     nr = nr.length < 32 ? nr + '0'.repeat(32 - nr.length) : nr;

     // Convert to decimal output
     return parseInt(nr,2)
};

Solution Two

Analysis:

Advanced method, using bit operations

  1. Get the last binary number of the input value n and put it at the end of the result number result
  2. The result number result moves 1 digit to the left
  3. Enter the value of n to move 1 digit to the right, loop the entire n, move all the numbers of n to the end of result from right to left, and complete the reverse
  4. Pay attention to the use of unsigned >>> to move left to handle negative numbers

Code:

/**
  * @param {number} n - a positive integer
  * @return {number} - a positive integer
  */
var reverseBits = function(n) {
     // Result array
     let result = 0;

     // loop the entire n
     for(let i = 0; i < 32; i++){
         // 1. result << 1: Shift one bit to the left, free up the space on the right, and set it to 0
         // 2. n & 1: get the rightmost number of n, 0 or 1
         // 3. (result << 1) | (n & 1): put the rightmost number of n to the rightmost of result
         result = (result << 1) | (n & 1);
        
         // n shift left
         n >>>= 1;
     }

     // To use unsigned left shift
     return result >>> 0
};

Reference

Comments