[LeetCode] 190. Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).

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

Related problem: Reverse Integer

Thought process:

Right shift the number until it's 0. For every bit, if it's 1, add n & 1 to the reversed number, and right-shift n. Because input number is a 32 bits unsigned integer, and Java int is 32 bits signed, I should not left-shift reversed if it's the last bit.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

public class Solution { // you need treat n as an unsigned value public int reverseBits(int n) { int reversed = 0; for (int i = 0; i < 32; i++) { reversed += n & 1; n >>>= 1; if (i < 31) { reversed <<= 1; } } return reversed; } }

Time complexity: O(1).

Follow-up:
I can divide the number into 4 bytes, reverse each byte and combine them into an integer. For each byte, I can use cache to improve performance.