Reverse Bits

Easy Bit Manipulation Basics Original on LeetCode

Reverse Bits is a easy bit manipulation problem solved with the basics pattern. The best approach, optimal (swap halves with masks), runs in O(1) time and O(1) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (via a 32-character string) up.

Problem

Treat the integer n as a 32-bit binary number (leading zeros included) and reverse the order of its bits: the bit at position i moves to position 31 - i. Return the value of the reversed bit pattern.

For this version n is even and at most 2^31 - 2, so its lowest bit is 0 and the answer always fits in a signed 32-bit integer.

Examples

Example 1

Input
n = 6
Output
1610612736
Why
6 is 000...0110 in 32 bits. Reversed, the two 1s move to positions 30 and 29: 2^30 + 2^29 = 1610612736.

Example 2

Input
n = 1024
Output
2097152
Why
The single 1 at position 10 moves to position 31 - 10 = 21, which is 2^21.

Example 3

Input
n = 0
Output
0
Why
Reversing all zeros gives all zeros.

Constraints

  • 0 <= n <= 2^31 - 2
  • n is even, so the reversed value also fits in a signed 32-bit integer.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (via a 32-character string)O(32)O(32)
Bit by bitO(32)O(1)
Optimal (swap halves with masks)O(1)O(1)

1Brute force (via a 32-character string)

TimeO(32)A fixed number of characters is built, reversed and parsed.
SpaceO(32)The 32-character strings.

Write n as a 32-character binary string padded with leading zeros, reverse the string and parse it back as a binary number.

  1. Format n in binary, left-padded with zeros to length 32.
  2. Reverse the string.
  3. Parse it as a base-2 number.
class Solution {
    public int reverseBits(int n) {
        String bits = String.format("%32s", Integer.toBinaryString(n)).replace(' ', '0');
        String reversed = new StringBuilder(bits).reverse().toString();
        return (int) Long.parseLong(reversed, 2);
    }
}

2Bit by bit

TimeO(32)Exactly 32 iterations of constant work.
SpaceO(1)Two integers.

Repeat 32 times: shift the result left by one, copy n's lowest bit into the result's lowest bit, and shift n right by one (unsigned). The bit that was first in n ends up last in the result.

  1. result = 0.
  2. 32 times: result = (result << 1) | (n & 1); n = n >>> 1.
  3. Return result.
class Solution {
    public int reverseBits(int n) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            result = (result << 1) | (n & 1);
            n >>>= 1;
        }
        return result;
    }
}

3Optimal (swap halves with masks)

TimeO(1)Five fixed word operations (log2 32), no loop.
SpaceO(1)Only n itself.

Reversing 32 bits is the same as swapping the two 16-bit halves, then swapping the two bytes inside each half, then the two nibbles inside each byte, then the bit pairs, then neighbouring bits. Each level is one mask-and-shift on the whole word, so five steps reverse everything.

  1. n = (n >>> 16) | (n << 16).
  2. n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8).
  3. n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4).
  4. n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2).
  5. n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1).
class Solution {
    public int reverseBits(int n) {
        n = (n >>> 16) | (n << 16);
        n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8);
        n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4);
        n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2);
        n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1);
        return n;
    }
}

Edge cases to test

  • n = 0
  • A palindromic bit pattern that maps to itself (for example 2^31 - 2)
  • A single set bit
  • Leading zeros of the 32-bit form become trailing zeros of the answer

Hints

Hint 1

Always think of n as exactly 32 bits, including its leading zeros.

Hint 2

Peel bits off the low end of n one at a time and push them onto the low end of the result, shifting the result left each time.

Hint 3

For a branch-free version, swap the two 16-bit halves, then the bytes inside each half, then nibbles, pairs and single bits, each with one mask.

FAQ

What is the best time complexity for Reverse Bits?

Optimal (swap halves with masks) runs in O(1) time and O(1) extra space. Five fixed word operations (log2 32), no loop.

Which pattern does Reverse Bits use?

It is a bit manipulation problem that uses the basics pattern. Other problems with the same pattern: Decimal to binary, Convert Binary Number in a Linked List to Integer, K-th Bit is Set or Not.

Is there a brute force solution for Reverse Bits?

Yes. Brute force (via a 32-character string) takes O(32) time and O(32) space. Write n as a 32-character binary string padded with leading zeros, reverse the string and parse it back as a binary number.

Which edge cases should I test for Reverse Bits?

n = 0; A palindromic bit pattern that maps to itself (for example 2^31 - 2); A single set bit; Leading zeros of the 32-bit form become trailing zeros of the answer.