Upside-Down Light Strip

Easybit manipulationAlso known as Reverse Bits

A shop window has a strip of exactly 32 lights, controlled by one 32-bit number. Bit 0 (the lowest bit) switches the leftmost light, bit 1 the next one, and so on up to bit 31 on the far right. The window designer has a library of patterns stored as these numbers.

The installer mounted the strip the wrong way round, so every pattern now shows mirrored. Rewiring is not an option. Instead, the controller should mirror each number before sending it, so the window looks the way the designer meant.

Your task

Write mirrorPattern(pattern). Treat pattern as exactly 32 bits, including leading zeros. Return the number you get by reversing the order of those 32 bits: bit 0 moves to bit 31, bit 1 to bit 30, and so on.

Both the input and the result are unsigned: whole numbers from 0 to 4,294,967,295. Never return a negative number.

mirrorPattern(pattern: int) → int

Examples

Example 1

Input

pattern = 1

Output

2147483648

Why

Only the leftmost light is on: bit 0. Mirrored, only bit 31 is on, which is 2³¹ = 2,147,483,648. Reversing the short string "1" would give 1, which is wrong: the 31 leading zeros count too.

Example 2

Input

pattern = 6

Output

1610612736

Why

6 is ...00110: bits 1 and 2 are on. They move to bits 30 and 29, so the answer is 2³⁰ + 2²⁹ = 1,610,612,736.

Example 3

Input

pattern = 4294967295

Output

4294967295

Why

All 32 lights are on. A mirror of a full strip is still a full strip.

Constraints

0 ≤ pattern ≤ 4,294,967,295 (that is, 2³² - 1)

Start with brute force

Convert the number to a binary string, pad it with zeros to 32 characters, reverse the string, and parse it back. That works and runs in O(32), which is fine.

The trap is the padding. Forget it and 1 mirrors to 1 instead of 2,147,483,648. The string version also hides what is really happening. Doing it with shifts teaches you how to move bits around directly, which you need whenever you pack data into integers.

Hints

0 of 4 shown

Hint 1
Take a 4-bit strip instead of 32. Mirror 0011 and 0001 by hand. Where did each lit bit go, and why do the zeros on the left matter?
Hint 2
Bit i of the input becomes bit 31 - i of the output. You can read bit i with (pattern >> i) & 1.
Hint 3
Instead of computing positions, build the answer like a queue of bits: take the input's lowest bit, push it into the answer from the right, and shift both. After 32 rounds, which input bit ends up highest?
Hint 4
Loop exactly 32 times: result = (result << 1) | (pattern & 1), then shift pattern right by one. In JavaScript, bit operators work on signed 32-bit numbers, so use >>> for the shift and finish with result >>> 0 to read the result as unsigned.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

Pop bits off the bottom of the input and push them onto the bottom of the answer. The first bit you pop gets pushed up 31 more times, so it ends at the top. The last bit you pop stays at the bottom. That is exactly a reversal.

Trace it on a 4-bit strip with input 0011 (3), looping 4 times instead of 32:

Input 0011, lowest bit 1. Result 1.
Input 001, lowest bit 1. Result 11.
Input 00, lowest bit 0. Result 110.
Input 0, lowest bit 0. Result 1100 (12).

The last two rounds read only zeros, yet they matter: they push the two 1s up into place. That is why the loop must run the full width, 32 times, even after the input has run out of 1 bits. With 32 bits, the same input 3 ends up at bits 31 and 30: 3,221,225,472.

In JavaScript, << and | produce signed 32-bit values, so a result with bit 31 set reads as negative. >>> 0 reinterprets the same bits as unsigned. Python integers have no fixed width, so nothing extra is needed there.

Reference solution

function mirrorPattern(pattern) {
  let result = 0;
  for (let i = 0; i < 32; i++) {
    // push the lowest input bit onto the right end of result
    result = (result << 1) | (pattern & 1);
    pattern >>>= 1;
  }
  return result >>> 0; // read the 32 bits as unsigned
}

def mirror_pattern(pattern):
    result = 0
    for _ in range(32):
        # push the lowest input bit onto the right end of result
        result = (result << 1) | (pattern & 1)
        pattern >>= 1
    return result

TimeO(1)Always exactly 32 rounds, each a few bit operations.

SpaceO(1)Two integer variables.

Learn the idea: Bit Manipulation

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code