https://leetcode.com/problems/reverse-bits

We are asked to reverse bits in our number. What is the most logical way to do it? Create number out, process original number bit by bit from end and add this bit to the end of our out number, and that is all! Why it is works?

  1. out = (out << 1)^(n & 1) adds last bit of n to out
  2. n >>= 1 removes last bit from n.

Imagine number n = 11011010, and out = 0

  1. out = 0, n = 1101101
  2. out = 01, n = 110110
  3. out = 010, n = 11011
  4. out = 0101, n = 1101
  5. out = 01011, n = 110
  6. out = 010110, n = 11
  7. out = 0101101, n = 1
  8. out = 01011011, n = 0

Compexity: time complexity is O(32), space complexity is O(1).

Follow up There is O(5) smart solution which quite impressive, see the most voted post in discussion by @tworuler. We also can hash some 8-bits parts, so we can inverse 4 parts on the fly, with time complexity O(4) and memory complexity O(256) (and preprocessing O(256) as well).

class Solution:
    def reverseBits(self, n):
        out = 0
        for i in range(32):
            out = (out << 1)^(n & 1)
            n >>= 1
        return out

If you like the solution, you can upvote it on leetcode discussion section: Problem 0190