# LeetCode Notes: Reverse Bits

## 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`.

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:

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
};
``````