leetcode/190EReverseBits

反转二进制

my solution

我选的方法是直接调用 bits.Reverse 函数来解决, 如果自己写的话, 应该会循环获取每一位, 重新构造一个数字

func reverseBits(num uint32) uint32 {
	return bits.Reverse32(num)
}

best solution

这也是为什么一道 easy 的题会单独做笔记的原因, 因为这道题的解法很有意思

func reverseBits(num uint32) uint32 {
    constNums := []uint32{0xAAAAAAAA, 0x55555555, 0xCCCCCCCC, 0x33333333, 0xF0F0F0F0, 0x0F0F0F0F, 0xFF00FF00, 0x00FF00FF, 0xFFFF0000, 0x0000FFFF}
    var index, power uint32
    for index, power = 0, 0; index <= 8; index, power = index+2, power+1 {
        num = ((num & constNums[index]) >> (1 << power)) | ((num & constNums[index+1]) << (1 << power))
    }
    return num
}

乍看之下理解不了, 特别是循环中的那句代码, 先给个例子来展示一下 :

原二进制:       00000010100101000001111010011100
第一次循环后:       00000001011010000010110101101100
第二次循环后:       00000100100100101000011110010011
第三次循环后:       01000000001010010111100000111001
第四次循环后:       00101001010000000011100101111000
第五次循环后:       00111001011110000010100101000000

((num & constNums[index]) >> (1 << power)) | ((num & constNums[index+1]) << (1 << power))

代码的含义是这样的(诶… 我想想怎么解释一下 = =)

emmm, 先看一个最简单的例子, 那么就能理解了, 首先, 取二进制 01, 只执行一次循环, 看看效果

num & constNums[index] = 0, (num & constNums[index+1]) = 1, power = 0, 所以结果是 10, 我们得到了反转字符串

那么再来难点的例子, 1101, 这样需要执行两次循环

num & constNums[index] = 1000, (num & constNums[index+1]) = 0101, power = 0, 所以第一次循环的结果是 0100 | 1010 = 1110

num & constNums[index] = 1100, (num & constNums[index+1]) = 0010, power = 1, 所以结果是 0011 | 1000 = 1011

这样大概就能了解了吧, 第一次循环是两位为一组交换位置, 第二次循环是四位为一组交换位置, 所以第一次的二进制是 0xAAAAAAAA, 0x55555555 类似与 101010… 010101… 这样的, 他们的二进制位是相反的, 同理直到达到足够的位数为止, 这道题的复杂度是 O(logn) 级别的, 其中 s = 数字的位数, s = 2 的 n 次方

真是个不错的算法 :)

这个算法能见到 二分 和 递归 的影子, 理解了就会非常简单

看了 go 对于该算法的实现, 也是这样的

顺便, 看了 go 的源码, 其实句子可以更简单

constNums[index] & num >> (1 << power) | constNums[index+1] & num << (1 << power)

整个代码也可以重构

func reverseBits(n uint32) uint32 {
    var m0 uint32 = 0x55555555
    var m1 uint32 = 0x33333333
    var m2 uint32 = 0x0F0F0F0F
    var m3 uint32 = 0x00FF00FF

    n = n >> 1 & m0 | n & m0 << 1
    n = n >> 2 & m1 | n & m1 << 2
    n = n >> 4 & m2 | n & m2 << 4
    n = n >> 8 & m3 | n & m3 << 8
    return n >> 16 | n << 16
}

这基本与 go 的 reverse32 源码一致, 不愧是源码啊…

这个版本的代码进一步减少了变量和常量, 其中那 index 所代表的一对本就可以用移位来代替