[Go版]算法通关村第十一关白银——位运算的高频算法题

专题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
}