算法篇：位运算基本操作

灰子学技术

发布于 2020-09-23 15:33:22

2330

发布于 2020-09-23 15:33:22

算法:

本章介绍位操作的基本操作，具体操作见下面的几类具体题目：

异或操作，与操作，或操作和偏移操作

题目1: 计算位1的个数

https://leetcode-cn.com/problems/number-of-1-bits/

代码实现：

func hammingWeight(num uint32) int {
   count := 0
   for i := 0; i < 32; i++ {
     if num&(1<<i) != 0 {
         count++
     }
   }
   return count
}
// 算法： 
// 利用单个bit上面的 a&1=1 表示a=1；a&1=0 表示a=0

执行结果：

题目2:2的幂

https://leetcode-cn.com/problems/power-of-two/

代码实现：

func isPowerOfTwo(n int) bool {
    if n == 0 {
        return false
    }
    return n&(n-1) ==0
}
// 算法：
// 2的幂转换成二进制，如下图所示，所以可以利用n&(n-1) == 0 来判断
// 0000 0001  ->1
// 0000 0010  ->2 
// 0000 0100  ->4
// 0000 1000  ->8
// 0001 0000  ->16
// 0010 0000  ->32
// 0100 0000  ->64
// 1000 0000  ->128

执行结果：

题目3: 两个整数的和

https://leetcode-cn.com/problems/sum-of-two-integers/

代码实现：

func getSum(a int, b int) int {
    // b作为进位，当为0的时候，说明计算结束
    for b != 0 {
    sum := a ^ b // 不进位的加法
    carry := (a & b) << 1 // 计算进位
    a = sum
    b = carry
  }
  return a
}
// 算法：
// 1. 异或操作，a^b 得到的结果，a+b不进位的和的数值
// 2. 与操作，a&b向右偏移1位，表示的就是进位数值
// 3. 循环操作，直到进位数为0，表示计算结束了。

执行结果：

题目4:

https://leetcode-cn.com/problems/swap-numbers-lcci/

代码实现：

func swapNumbers(numbers []int) []int {
    numbers[0] ^= numbers[1]
    numbers[1] ^= numbers[0]
    numbers[0] ^= numbers[1]
    return numbers
}
// 算法：
// 交换a,b，位操作步骤：a ^=b; b ^= a; a ^= b;

执行结果：