LeetCode 190. Reverse Bits

The Problem

Link to original problem on Leetcode.

Reverse bits of a given 32 bits unsigned integer.

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

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.

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.

My Solution

Naïve Approach

If you choose to ignore that this is a problem about binary operations, you can very simply return the integer representing the reverse of the input’s bits by converting to a string, splitting it, reversing the array, joining it, padding any necessary zeroes back on, then finally making it an integer again.

const reverseBits = n => {
	return Number.parseInt(
		n.toString(2).split('').reverse().join('').padEnd(32, '0'),
		2,
	);
};

Of course, we know that we really ought to use binary operations because…well, it’s a question about bits, isn’t it?

Better Bitwise Approach

A more appropriate approach is to loop 32 times (because 32-bit int) and fill in a result variable with the results of shifting the binary number in each step.

const reverseBits = n => {
	let result = 0;
	for (let i = 0; i < 32; i++) {
		// We're going to add to the result whatever is the ith
		// bit from the right of n. So we shift right 0 times,
		// then once, then twice, until we've shifted right 32
		// times. By using AND to compare that bit to 1, we can
		// add either 1 or 0 to result as appropriate.
		result += (n >>> i) & 1;
		// Don't shift on the final loop!
		if (i < 31) {
			result <<= 1;
		}
	}
	// This is particular to JavaScript. When we were shifting
	// left (<<) above, JS coerced the result to a signed int!
	// By right-shifting 0 places, we can coerce it back to an
	// unsigned integer. You could also use Math.abs() on the
	// result. Or in the loop, instead of left-shifting, you
	// could multiply the result by 2 for the same effect.
	return (result >>>= 0);
};

This is a perfectly good way to get the reversed binary value with bitwise operators. Having $O(32)$ isn’t too shabby! But is there an even simpler way? Uh, yeah, sort of.

Next-Level Bitwise Approach

const reverseBits = n => {
	let result = n;
	result = (result >>> 16) | (result << 16);
	result = ((result & 0xff00ff00) >>> 8) | ((result & 0x00ff00ff) << 8);
	result = ((result & 0xf0f0f0f0) >>> 4) | ((result & 0x0f0f0f0f) << 4);
	result = ((result & 0xcccccccc) >>> 2) | ((result & 0x33333333) << 2);
	result = ((result & 0xaaaaaaaa) >>> 1) | ((result & 0x55555555) << 1);
	// Don't forget to coerce to unsigned int for JavaScript!
	return result >>> 0;
};

Um, what?

Yeah, this one will probably need explaining. We start by setting the result equal to n. Then the first step is easy enough to understand: we’re basically cutting the number n in half, and swapping those halves.

Here’s an example of what’s happening using letters to represent the unique binary digits and show how they are moving.

n = abcdefghijklmnopqrstuvwxyzABCDEF
n >>> 16 = 0000000000000000abcdefghijklmnop
n << 16 = qrstuvwxyzABCDEF0000000000000000
n >>> 16 | n << 16 = qrstuvwxyzABCDEFabcdefghijklmnop

But what’s with these hexidecimal numbers in the next steps? Well, we’re sort of doing the same thing, but now we’re breaking our halves into halves and swapping them. You can think of a number like 0xff00ff00 as the binary 11111111000000001111111100000000. In each step, the hexidecimal numbers represent the 1s that we’re trying to intersect with an isolate to perform our shifts correctly.¹

result = qrstuvwxyzABCDEFabcdefghijklmnop
(n & 0xff00ff00) = qrstuvwx00000000abcdefgh00000000
(n & 0x00ff00ff) = 00000000yzABCDEF00000000ijklmnop
(n & 0xff00ff00) >>> 8 = 00000000qrstuvwx00000000abcdefgh
(n & 0x00ff00ff) << 8 = yzABCDEF00000000ijklmnop00000000
(n & 0xff00ff00) >>> 8 | (n & 0x00ff00ff) << 8 = yzABCDEFqrstuvwxijklmnopabcdefgh

With each step, we break the previously shifted sections in half and shift them. Here’s how each step transforms the result, color coded to make it easier to see the pattern:²

abcdefghijklmnopqrstuvwxyzABCDEF to qrstuvwxyzABCDEFabcdefghijklmnop

qrstuvwxyzABCDEFabcdefghijklmnop to yzABCDEFqrstuvwxijklmnopabcdefgh

yzABCDEFqrstuvwxijklmnopabcdefgh to CDEFyzABuvwxqrstmnopijklefghabcd

CDEFyzabuvwxqrstmnopijklefghabcd to EFCDabyzwxuvstqropmnklijghefcdab

EFCDabyzwxuvstqropmnklijghefcdab to FEDCbazyxwvutsrqponmlkjihgfedcba

We’ve reduced our already amazing $O(32)$ to $O(1)$! This is much better optimized if you’ve got an absolute ton of binary numbers to reverse, though it’s perhaps not the most intuitive or legible.