190.Reverse_Bits.md

190. Reverse Bits

简单 https://leetcode-cn.com/problems/reverse-bits/

Reverse bits of a given 32 bits unsigned integer.

Note that in some languages such as Java, there is no unsigned integer type. In this case, both input and output will be given as signed integer type and should not affect your implementation, as the internal binary representation of the integer is the same whether it is signed or unsigned.
In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 2 above the input represents the signed integer -3 and the output represents the signed integer -1073741825.

Example

Example 1:

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.

Example 2:

Input: 11111111111111111111111111111101
Output:   3221225471 (10111111111111111111111111111111)
Explanation: 
The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293
so return 3221225471 which its binary representation is 10101111110010110010011101101001.

Constraints:

• The input must be a binary string of length 32  

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

相关企业

• 苹果 Apple|2
• 亚马逊 Amazon|2

相关标签

• Bit Manipulation
• Divide and Conquer

相似题目

• Reverse Integer 中等
• Number of 1 Bits 简单

Prerequisite:

位且 any bits AND d1-> 取决于最后一个bit (The result is up to last bit)
d2 & d1 -> b000010 & b000001 => b000000 => b0 =>d0
d3 & d1 -> b0011 & b0001 => b0001 =>b1 =>d1
d4 & d1 -> b0100 & b0001 => b0000 => b0 =>d0

位移>>
d2 >> d1 : b0010 => b0001 =>d1
d3 >> d1 : b0011 => b0001 =>d1
d4 >> d1 : b0100 => b0010 =>d2

this one pass both in lintcode and leetcode.
public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        return reverseBits(n, 0);
    }

    private int reverseBits(int n, int pos){
        if (pos >= 32){ 
            return 0;
        }

        int lastBit = n & 1; 
        n = n >> 1;
        int ret = reverseBits(n, pos + 1); 
        ret += lastBit << (31 - pos) ; 
        return ret;
    }
}

this one pass in lintcode but not leetcode.
The reason is for "n>>1" the lintcode fill the left part with 0 but leetcode fill it with 1 or 0:
        n = 0b01111111111111111111111111111101;
        System.out.printf("n: %x\n",n);
        n = n >> 2;
        System.out.printf("n: %x\n",n);
        - n: 7ffffffd
        - n: 1fffffff (fill with 0)

        n = 0b11111111111111111111111111111101;
        System.out.printf("n: %x\n",n);
        n = n >> 2;
        System.out.printf("n: %x\n",n);
        - n: fffffffd
        - n: ffffffff (fill with 0)



 public class Solution {
    // you need treat n as an unsigned value
    public long reverseBits(long n) {
        return reverseBits(n, 0);
    }

    private long reverseBits(long n, int pos){
        if (pos >= 31){ 
            return n;
        }

        long lastBit = n & 1; 
        n = n >> 1;
        long ret = reverseBits(n, pos + 1); 
        ret += lastBit << (31 - pos) ; 
        return ret;
    }
}

class Solution:
    def reverseBits(self, n: int, pos=0) -> int:
        
        if (pos >= 32):
            return 0

        lastBit = n & 1;
        ret = self.reverseBits(n >> 1, pos + 1)
        ret += lastBit << (31 - pos)
        return ret

The above one passed but the below error.
Because 'python does not support method overload'.

class Solution:
    def reverseBits(self, n: int) -> int:
        return self.reverseBits(n, 0);

    def reverseBits(self, n, pos):
        if (pos >= 32):
            return 0

        lastBit = n & 1;
        ret = self.reverseBits(n >> 1, pos + 1)
        ret += lastBit << (31 - pos)
        return ret