颠倒二进制位
📌 定义
颠倒给定的 32 位无符号整数的二进制位。
示例:
输入: 00000010100101000001111010011100
输出: 00111001011110000010100101000000
解释: 将二进制位完全颠倒
输入: 11111111111111111111111111111101
输出: 10111111111111111111111111111111
核心思路
三种主要方法：
- 逐位颠倒：从右往左逐位取出，从左往右放入
- 分治法：递归地交换相邻的位、字节等
- 查表法：预计算所有可能的字节反转结果
逐位颠倒示例:
原数字: 1011 (11)
步骤1: result = 0000, 取出最右位1
result = 0001, n右移 → 101
步骤2: result = 0010, 取出最右位1
result = 0011, n右移 → 10
步骤3: result = 0110, 取出最右位0
result = 0110, n右移 → 1
步骤4: result = 1100, 取出最右位1
result = 1101, n右移 → 0
结果: 1101 (13)
复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 逐位颠倒 | O(log n) | O(1) | 32次循环 |
| 分治法 | O(1) | O(1) | 固定次数操作 |
| 查表法 | O(1) | O(256) | 空间换时间 |
Go 代码
Go 实现
package main
import "fmt"
// 方法1: 逐位颠倒
func reverseBits(n uint32) uint32 {
var result uint32 = 0
for i := 0; i < 32; i++ {
result <<= 1
result |= n & 1
n >>= 1
}
return result
}
// 方法2: 分治法
func reverseBitsDivideConquer(n uint32) uint32 {
// 交换相邻的1位
n = ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1)
// 交换相邻的2位
n = ((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2)
// 交换相邻的4位
n = ((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4)
// 交换相邻的8位
n = ((n & 0xFF00FF00) >> 8) | ((n & 0x00FF00FF) << 8)
// 交换相邻的16位
n = (n >> 16) | (n << 16)
return n
}
// 方法3: 查表法
var reverseByteTable [256]uint8
func init() {
for i := 0; i < 256; i++ {
reverseByteTable[i] = reverseByte(uint8(i))
}
}
func reverseBitsLookup(n uint32) uint32 {
return (uint32(reverseByteTable[n&0xFF]) << 24) |
(uint32(reverseByteTable[(n>>8)&0xFF]) << 16) |
(uint32(reverseByteTable[(n>>16)&0xFF]) << 8) |
(uint32(reverseByteTable[(n>>24)&0xFF]))
}
func reverseByte(b uint8) uint8 {
var result uint8 = 0
for i := 0; i < 8; i++ {
result = (result << 1) | (b & 1)
b >>= 1
}
return result
}
func main() {
n := uint32(0b00000010100101000001111010011100)
result := reverseBits(n)
fmt.Printf("输入: %032b\n", n)
fmt.Printf("输出: %032b\n", result)
}思路展开
方法1详解：逐位颠倒
示例: n = 1011 (4位演示)
初始: result = 0000, n = 1011
循环1:
result <<= 1 → 0000
result |= 1 → 0001 (取n的最右位)
n >>= 1 → 0101
循环2:
result <<= 1 → 0010
result |= 1 → 0011
n >>= 1 → 0010
循环3:
result <<= 1 → 0110
result |= 0 → 0110
n >>= 1 → 0001
循环4:
result <<= 1 → 1100
result |= 1 → 1101
n >>= 1 → 0000
最终: result = 1101
方法2详解：分治法
示例: n = 10110011 (8位演示)
步骤1: 交换相邻1位
原数: 10 11 00 11
掩码: 10101010 (0xAA) 和 01010101 (0x55)
操作: ((10110011 & 10101010) >> 1) | ((10110011 & 01010101) << 1)
= (10100010 >> 1) | (00010001 << 1)
= 01010001 | 00100010
= 01110011
步骤2: 交换相邻2位
原数: 0111 0011
掩码: 11001100 (0xCC) 和 00110011 (0x33)
操作: ((01110011 & 11001100) >> 2) | ((01110011 & 00110011) << 2)
= (01000000 >> 2) | (00110011 << 2)
= 00010000 | 11001100
= 11011100
步骤3: 交换相邻4位
原数: 1101 1100
掩码: 11110000 (0xF0) 和 00001111 (0x0F)
操作: ((11011100 & 11110000) >> 4) | ((11011100 & 00001111) << 4)
= (11010000 >> 4) | (00001100 << 4)
= 00001101 | 11000000
= 11001101
结果: 11001101 (原数10110011的反转)
查表法详解
预计算0-255的反转:
0 (00000000) → 0 (00000000)
1 (00000001) → 128 (10000000)
2 (00000010) → 64 (01000000)
3 (00000011) → 192 (11000000)
...
255 (11111111) → 255 (11111111)
32位拆分成4个字节:
n = ABCD (每个字母代表一个字节)
反转:
reverse(n) = reverse(D) << 24 |
reverse(C) << 16 |
reverse(B) << 8 |
reverse(A)
示例:
n = 0x12345678
= 0001 0010 | 0011 0100 | 0101 0110 | 0111 1000
reverse(0x12) << 24 = 0x48000000
reverse(0x34) << 16 = 0x002C0000
reverse(0x56) << 8 = 0x00006A00
reverse(0x78) = 0x0000001E
result = 0x482C6A1E
经典题目
LeetCode 问题
- 颠倒二进制位 - LeetCode 190
- 颠倒整数 - LeetCode 7（十进制反转）
- 回文数 - LeetCode 9（判断回文）
扩展问题
- 反转字符串
- 反转链表
⚖️ 优缺点
优点
- ✅ 逐位法简单直观：易于理解和实现
- ✅ 分治法效率高：固定次数操作
- ✅ 查表法最快：适合大量调用
- ✅ 无需额外空间：原地操作
缺点
- ❌ 分治法不直观：需要理解掩码
- ❌ 查表法占空间：需要256字节表