專題1：位移的妙用

題目：位1的個數（也被稱為漢明重量）

題目鏈接：LeetCode-191. 位1的個數

解法1：遍歷所有位，判斷每個位的數字是否是1

Go代碼

func hammingWeight(num uint32) int {count := 0for i:=0; i<32; i++ {count += int((num >> i) & 1)}return count   
}

或者

func hammingWeight(num uint32) int {count := 0for i:=0; i<32; i++ {if num & (1 << i) != 0 {count++}}return count   
}

解法2：依次消除每個1的位 num=num&(num-1)

Go代碼

func hammingWeight(num uint32) int {count := 0for num != 0 {// 除了最后1個1在&之后被去掉了，前面的&之后 1還是1 0還是0num = num & (num-1)count++}return count
}

題目：比特位計數

題目鏈接：LeetCode-338. 比特位計數

思路分析：遍歷每個數，使用上面的位1的個數計算即可

Go代碼

func countBits(n int) []int {ret := make([]int, 0)for i:=0;i<=n;i++ {ret = append(ret, hammingWeight(i))}return ret
}func hammingWeight(n int) int {count := 0for n != 0 {n = n & (n-1)count++}return count
}

題目：顛倒二進制位

題目鏈接：LeetCode-190. 顛倒二進制位

思路分析：獲得低位的數值，左移到高位去

Go代碼

func reverseBits(num uint32) uint32 {var ret uint32for i,j:=0,31; i<32 && j>=0; i,j=i+1,j-1 {v := num >> i & 1ret = ret | (v<<j)}return ret
}

專題2：位實現加減乘除

題目：兩整數之和

題目鏈接：LeetCode-371. 兩整數之和

思路分析：a&b<<1得進位，a^b得非進位

Go代碼

func getSum(a int, b int) int {for b!= 0 {carry := (a & b)<<1 //計算進位a = a ^ b  //計算非進位部分的和b = carry   //更新 b 為進位}return a
}

題目：遞歸乘法

題目鏈接：LeetCode-面試題 08.05. 遞歸乘法

思路分析：循環 + 位移

在循環中不斷將其中一個數加倍（左移），然后根據另一個數的每一位是否為1，來決定是否將加倍后的數累加到最終的結果中。

Go代碼

func multiply(A int, B int) int {min := getMin(A, B)max := getMax(A, B)ret := 0for min != 0{//位為1時才更新到ret，否則max一直更新if min & 1 == 1 {ret += max}min = min >> 1  //min除以2max = max << 1  //max乘以2}return ret
}
func getMin(a int, b int) int {if a >= b {return b}return a
}
func getMax(a int, b int) int {if a >= b {return a}return b
}