个人评价：位运算循环操作位移的方式掌握不难，分治就有点像汇编了，秀啊 😂
题目难度：🌟 （参考 LeeCode 简单🌟 、中等🌟 🌟 、困难🌟 🌟 🌟 ）
另，通常算法题会考察分析时间复杂度和空间复杂度，可参考笔者之前的文章
颠倒二进制位
题目描述
颠倒给定的 32 位无符号整数的二进制位。
提示：
请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。
进阶: 如果多次调用这个函数，你将如何优化你的算法？
示例 1：
输入: 00000010100101000001111010011100
输出: 00111001011110000010100101000000
解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。
示例 2：
输入：11111111111111111111111111111101
输出：10111111111111111111111111111111
解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293， 因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。
提示：
输入是一个长度为 32 的二进制字符串
解题思路
方法一
位运算根据题目要求使用循环迭代处理操作，思路如下：
原数 nums 从低位循环，如 k 位是 1，结果增加 1 的 k 位二进制数（相当于 31-k 次位移，2^(31-k) 次方）
Go 代码如下：
func reverseBits(num uint32) uint32 {
res := uint32(0)
for i := 0; i < 32; i++ {
if 1 << i & num > 0 {
res += 1 << (31-i)
}
}
return res
}
复杂度？ 🙌 时间 O(n) ，虽然 n = 32 ；空间 O(1)
方法二
其实和方法一差不多，但是可以省去原二进制数高位为 0 的计算
思路为改变循环判断条件为 nums > 0，Go 代码如下：
func reverseBits(num uint32) uint32 {
res := uint32(0)
i := 31
for ; num > 0; num >>= 1 { // 高位为 0 的不循环
if num & 1 == 1 {
res += 1 << i
}
i--
}
return res
}
复杂度？ 🙌 时间 O(logn) 空间 O(1)
方法三
分治，思想是分而治之，把数字分为两半，然后交换这两半的顺序；然后把前后两个半段都再分成两半，交换内部顺序……直至最后交换顺序的时候，交换的数字只有 1 位。
截一张网友图解（先以 8 位二进制数字为例）：
32 位则是 16 =》8 =》4 =》2 =》 1
先上代码如下：
func reverseBits(n uint32) uint32 {
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;
}
常数理解 & 转换
// 0xff00ff00 00000000111111110000000011111111 // 0xf0f0f0f0 00001111000011110000111100001111 // 0xcccccccc 00110011001100110011001100110011 // 0xaaaaaaaa 01010101010101010101010101010101
个人觉得网友的评论方法更易理解
// 32位无符号整数，如 1111 1111 1111 1111 1111 1111 1111 1111
// 表示成16进制 f f f f f f f f
// 一个16进制的f代表二进制的4位
// ffff ffff右移16位，变成 0000 ffff
// ffff ffff左移16位，变成 ffff 0000
// 它们俩相或，就可以完成低16位与高16位的交换
// 之后的每次分治，都要先与上一个掩码，再进行交换
总结
此题和 【每日一题】Go题解 2. 位1的个数 很相像，个人感觉，能直出方法二就够了
没想到，被分治法给秀到了😂