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?
解题方法
bit shift
- 在一个while loop循环中，因为已经定了是32位的整数，所以要Loop32次
- 将当前的bit加到另一个变量result上
- n不断右shfit, result不断左shift
swap 2 bits at a time
每次swap对应的两位
public int reverseBits(int n) {
for (int i = 0; i < 16; i++) {
n = swapBits(n, i, 32 - i - 1);
}
return n;
}
public int swapBits(int n, int i, int j) {
//find the value of these 2 bits
int a = (n >> i) & 1;
int b = (n >> j) & 1;
//if they are not the same, swap them
if ((a ^ b) != 0) {
//因为它们肯定不同，所以直接用^,将0变成1，将1变成0
return n ^= (1 << i) | (1 << j);
}
return n;
}
follow up优化
根据leetcode上的一个discuss而来，思想就是将每4位直接建立一个Lookup table
value -> reverse
0 ------> 0
1 ------> 8
... ------> ...
15 ------> 15
然后每次将这4位找到对应的reverse,每次shift4位来计算
其实这种思想可以继续优化，建立更大的Lookup table就可以
Solution
class Solution(object):
def reverseBits(self, n):
"""
:type n: int
:rtype: int
"""
if not n:
return 0
result = 0
times = 0
while times < 32:
curBit = n & 1
result = (result << 1) + curBit
n = n >> 1
times += 1
return result