顛倒給定的 32 位無符號整數(shù)的二進(jìn)制位。
示例 1：
輸入: 00000010100101000001111010011100
輸出: 00111001011110000010100101000000
解釋: 輸入的二進(jìn)制串 00000010100101000001111010011100 表示無符號整數(shù) 43261596，
因此返回 964176192，其二進(jìn)制表示形式為 00111001011110000010100101000000。
示例 2：
輸入：11111111111111111111111111111101
輸出：10111111111111111111111111111111
解釋：輸入的二進(jìn)制串 11111111111111111111111111111101 表示無符號整數(shù) 4294967293，
因此返回 3221225471 其二進(jìn)制表示形式為 10111111111111111111111111111111 。</pre>
方法一：從最后一位一位的顛倒
復(fù)雜度分析：
時(shí)間復(fù)雜度：O(1)。最多循環(huán)右移32位，常數(shù)級。
空間復(fù)雜度：O(1)。
func reverseBits(num uint32) uint32 {
//直接從最后面開始循環(huán)，一個(gè)一個(gè)轉(zhuǎn)換到前面
res := uint32(0)
p := uint32(31) //左移的位數(shù)，初始為31
for num != 0 {
res += (num&1) << p
num = num >> 1 //num位數(shù)-1
p-- //左移的位數(shù)-1
}
return res
}
方法二：利用分治法的思想
首先將原來的 32 位分為 2 個(gè) 16 位的塊，然后進(jìn)行或（|）運(yùn)算，此時(shí)就相當(dāng)于這兩個(gè)16位的塊顛倒了一次了
然后再將2個(gè)16位的塊分別再分成2個(gè)8位的塊，也是進(jìn)行或運(yùn)算來合并
然后一直分割，直到全部分成1位的塊，因?yàn)槊看畏指詈筮M(jìn)行或運(yùn)算來合并，到最后1位塊合并之后其實(shí)就是整個(gè)二進(jìn)制已經(jīng)顛倒好了
復(fù)雜度分析
時(shí)間復(fù)雜度：O(1)，沒有使用循環(huán)。
空間復(fù)雜度：O(1)，沒有使用變量。
func reverseBits(num uint32) uint32 {
num = num<<16 | num>>16
//0xff00ff00 的二進(jìn)制 11111111000000001111111100000000
//0x00ff00ff 的二進(jìn)制 00000000111111110000000011111111
num = ((num & 0xff00ff00) >> 8) | ((num & 0x00ff00ff) << 8)
//0xf0f0f0f0 的二進(jìn)制 11110000111100001111000011110000
//0x0f0f0f0f 的二進(jìn)制 00001111000011110000111100001111
num = ((num & 0xf0f0f0f0) >> 4) | ((num & 0x0f0f0f0f) << 4)
//0xcccccccc 的二進(jìn)制 11001100110011001100110011001100
//0x33333333 的二進(jìn)制 00110011001100110011001100110011
num = ((num & 0xcccccccc) >> 2) | ((num & 0x33333333) << 2)
//0xaaaaaaaa 的二進(jìn)制 10101010101010101010101010101010
//0x55555555 的二進(jìn)制 01010101010101010101010101010101
num = ((num & 0xaaaaaaaa) >> 1) | ((num & 0x55555555) << 1)
return num
?
}
