LeetCode 0190. Reverse Bits Solution in Java, C++, Python & More | Explanation + Code

Description

Reverse bits of a given 32 bits signed integer.

 

Example 1:

Input: n = 43261596

Output: 964176192

Explanation:

Integer	Binary
43261596	00000010100101000001111010011100
964176192	00111001011110000010100101000000

Example 2:

Input: n = 2147483644

Output: 1073741822

Explanation:

Integer	Binary
2147483644	01111111111111111111111111111100
1073741822	00111111111111111111111111111110

 

Constraints:

• 0 <= n <= 231 - 2
• n is even.

 

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

Solutions

Solution 1: Bit Manipulation

We can extract each bit of n from the lowest bit to the highest bit, and then place it at the corresponding position of ans.

For example, for the i-th bit, we can extract the i-th bit of n and place it at the (31 - i)-th bit of ans by (n & 1) \ll (31 - i), and then right shift n by one bit.

The time complexity is O(log n), and the space complexity is O(1).

PythonJavaC++GoTypeScriptRustJavaScript

class Solution: def reverseBits(self, n: int) -> int: ans = 0 for i in range(32): ans |= (n & 1) << (31 - i) n >>= 1 return ans(code-box)

public class Solution { // you need treat n as an unsigned value public int reverseBits(int n) { int ans = 0; for (int i = 0; i < 32 && n != 0; ++i) { ans |= (n & 1) << (31 - i); n >>>= 1; } return ans; } }(code-box)

class Solution { public: uint32_t reverseBits(uint32_t n) { uint32_t ans = 0; for (int i = 0; i < 32 && n; ++i) { ans |= (n & 1) << (31 - i); n >>= 1; } return ans; } };(code-box)

func reverseBits(n uint32) (ans uint32) { for i := 0; i < 32; i++ { ans |= (n & 1) << (31 - i) n >>= 1 } return }(code-box)

function reverseBits(n: number): number { let ans = 0; for (let i = 0; i < 32 && n; ++i) { ans |= (n & 1) << (31 - i); n >>= 1; } return ans >>> 0; }(code-box)

impl Solution { pub fn reverse_bits(mut n: u32) -> u32 { let mut ans = 0; for i in 0..32 { ans |= (n & 1) << (31 - i); n >>= 1; } ans } }(code-box)

/** * @param {number} n - a positive integer * @return {number} - a positive integer */ var reverseBits = function (n) { let ans = 0; for (let i = 0; i < 32 && n; ++i) { ans |= (n & 1) << (31 - i); n >>= 1; } return ans >>> 0; };(code-box)