Leetcode[190] Reverse Bits
16 Nov 2015###Task1 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
###Python
class Solution(object):
def reverseBits(self, n):
"""
:type n: int
:rtype: int
"""
for i in range(16):
n = self.reverse(n, i, 31 - i)
return n
def reverse(self, n, start, end):
start_bit = (n >> start) & 1
end_bit = (n >> end) & 1
if start_bit == end_bit:
return n
else:
n = n ^ (1 << start)
n = n ^ (1 << end)
return n
###Java
public class Solution {
public int swapBits(int n, int a, int b) {
int aint = (n >> a) & 1;
int bint = (n >> b) & 1;
if ((aint ^ bint) != 0) {
n = n ^ (1 << a);
n = n ^ (1 << b);
}
return n;
}
// you need treat n as an unsigned value
public int reverseBits(int n) {
for (int i = 0; i < 16; i++) {
n = swapBits(n, i, 32 - i - 1);
}
return n;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.reverseBits(43261596));
}
}
###Points
- (n » a) & 1 –> get one bit
- n ^ (1 « a) –> rotate one bit