"""
颠倒二进制位

链接：https://leetcode-cn.com/problems/reverse-bits

颠倒给定的 32 位无符号整数的二进制位。

示例 1：
输入: 00000010100101000001111010011100
输出: 00111001011110000010100101000000
解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
     因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。

示例 2：
输入：11111111111111111111111111111101
输出：10111111111111111111111111111111
解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
     因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。


提示：
请注意，在某些语言（如 Java）中，没有无符号整数类型。
在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。

进阶:
如果多次调用这个函数，你将如何优化你的算法？

官方解法：
1. 逐位颠倒。
例如：
                2^7  2^6  2^5  2^4  2^3  2^2  2^1  2^0
                1    0    1    0    1    0    1    0
    ↓ reverse
                0    1    0    1    0    1    0    1

逐步将整数 n 中的最右位取出，并累加到反转位中。
1) 要检索整数 n 中最右位，可以使用模运算（n % 2）或与运算（n & 1）;
2) 要组合反转位（2^a, 2^b）的结果，可以使用加法运算（2^a + 2^b）或位或运算（2^a | 2^b）。

关键思想是将索引 i 处的位，再反转后，其位置为 31 - i。
算法：
1) 从右到左遍历整数 n 的位字符串，即 n = n >> 1，每次取 n 的最右位，可用与运算（n & 1）取得；
2) 将取得的位放到反转结果的正确位置，即 (n & 1) << 31 - i，并累加反转结果值；
3) 当 n 等于 0 时，遍历结束。

时间复杂度：O(log2^N)。在算法中，我们有一个循环来迭代输入的最高非零位，即 log2^N。
空间复杂度：O(1)，因为不管输入是什么，内存的消耗是固定的。

"""
import unittest


class OfficialSolution:
    def reverse_bits(self, n: int) -> int:
        """逐位颠倒。"""
        rev = 0
        power = 31
        while n:
            rev += (n & 1) << power
            n >>= 1
            power -= 1
        return rev


class TestOfficialSolution(unittest.TestCase):
    def setUp(self) -> None:
        self.s = OfficialSolution()

    def test_reverse_bits(self) -> None:
        self.assertEqual(
            self.s.reverse_bits(43261596),
            964176192,
        )


if __name__ == '__main__':
    unittest.main()
