Skip to content

190. Reverse Bits

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

Thinking

Reverse the \(32\) bits of an unsigned integer. Pull each bit and write it to the mirrored index. Scan \(32\) times from the low end: take \(n\)'s lowest bit, write it at position \(31-i\), then shift \(n\) right. The width is fixed.

We can extract each bit of \(n\) from the lowest bit to the highest bit, and then place it at the corresponding position of \(\textit{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 \(\textit{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)\).

1
2
3
4
5
6
7
class Solution:
    def reverseBits(self, n: int) -> int:
        ans = 0
        for i in range(32):
            ans |= (n & 1) << (31 - i)
            n >>= 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
    }
};

1
2
3
4
5
6
7
func reverseBits(n uint32) (ans uint32) {
    for i := 0; i < 32; i++ {
        ans |= (n & 1) << (31 - i)
        n >>= 1
    }
    return
}

1
2
3
4
5
6
7
8
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
/**
 * @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;
};

Comments