LeetCode190 Reverse Bits

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

Reverse bits of a given 32 bits unsigned integer.

样例

1
2
3
4
Input:
43261596 (represented in binary as 00000010100101000001111010011100)
Output:
964176192 (represented in binary as 00111001011110000010100101000000)

思路

翻转32bits无符号整数。

暴力的做法是,对称着遍历然后swap即可。

不过,还有类似LeetCode191 Number of 1 Bits的优雅做法 (ノ゚∀゚)ノ

比如,翻转32bits无符号整数1001 1011 0101 0010 1001 1111 0001 0010

那么可以先每16位翻转

1
2
3
Input:  [1001 1011 0101 0010] [1001 1111 0001 0010]
X
Output: [1001 1111 0001 0010] [1001 1011 0101 0010]

再每8位翻转

1
2
3
Input:  [1001 1111] [0001 0010] | [1001 1011] [0101 0010]
X | X
Output: [0001 0010] [1001 1111] | [0101 0010] [1001 1011]

接着每4位翻转

1
2
3
Input:  [0001] [0010] | [1001] [1111] | [0101] [0010] | [1001] [1011]
X | X | X | X
Output: [0010] [0001] | [1111] [1001] | [0010] [0101] | [1011] [1001]

然后每2位翻转 …(就不给出具体的过程啦)

最后每1位翻转即可得到答案 0100 1000 1111 1001 0100 1010 1101 1001

如果有仔细阅读LeetCode191 Number of 1 Bits 这篇文章,代码应该不难实现 (~ ̄▽ ̄)~

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
int l = 0, r = 31;
while (l < r) {
// 当前比特位不相同
if (((n >> l) & 1) ^ ((n >> r) & 1)) {
// 各自取反
n ^= (1 << l);
n ^= (1 << r);
}
l++; r--;
}
return n;
}
};
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
n = (n >> 16) | (n << 16);
n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);
n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);
n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);
n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);
return n;
}
};
分享到 评论