位运算常用技巧以及练习

几个有趣的操作

• 利用或操作|和空格将英文字符转换成小写

  	// 可以变成小写
  	i := 'a' | ' '
  	fmt.Printf("%c\n", i)
  	j := 'A' | ' '
  	fmt.Printf("%c\n", j)
  1
  2
  3
  4
  5

• 利用与操作&和下划线把英文字符转换成大写

  	// 可以变成大写
  	m := 'b' & '_'
  	n := 'B' & '_'
  	fmt.Printf("%c\n", m)
  	fmt.Printf("%c\n", n)
  1
  2
  3
  4
  5

• 大小写转换

  	// 可以大小写转换
  	a := 'd' ^ ' '
  	b := 'D' ^ ' '
  	fmt.Printf("%c\n", a)
  	fmt.Printf("%c\n", b)
  1
  2
  3
  4
  5

• 判断两个数是否异号

  	x := -1
  	y := 2
  	f := (x ^ y) < 0
  	fmt.Println(f) // true
  
  	m := 3
  	n := 2
  	z := (m ^ n) < 0
  	fmt.Println(z) // false
  1
  2
  3
  4
  5
  6
  7
  8
  9

• 临时交换两个数字

  	a := 1
  	b := 2
  	a ^= b
  	b ^= a
  	a ^= b
  	fmt.Println(a)
  	fmt.Println(b)
  1
  2
  3
  4
  5
  6
  7

• 加1

  	n := 0
  	n = -^n
  	fmt.Println(n) // 1
  1
  2
  3

• 减1

  	n := 0
  	n = ^-n
  	fmt.Println(n) // -1
  1
  2
  3

n & (n - 1)的运用

作用：消除数字n的二进制表示中的最后一个1

本图借用了labuladong算法，特此声明

其核心逻辑就是，n - 1 一定可以消除最后一个 1，同时把其后的 0 都变成 1，这样再和 n 做一次 & 运算，就可以仅仅把最后一个 1 变成 0 了。

练习

191. 位1的个数

func hammingWeight(num uint32) int {
    count := 0
    for num != 0{
        num = num & (num - 1)
        count++
    }
    return count
}
1
2
3
4
5
6
7
8

231. 2 的幂

func isPowerOfTwo(n int) bool {
    if n <= 0 {
        return false
    }
    // 如果一个数是2的幂次方，那么它的二进制中一定只有一个1
    return n & (n - 1) == 0
}
1
2
3
4
5
6
7

a ^ a = 0的运用

一个数和它本身的异或运算结果为0，即a ^ a = 0；一个数和0做异或运算的结果为它本身，即a ^ 0 = a

练习

136. 只出现一次的数字

func singleNumber(nums []int) int {
    N := len(nums)
    res := nums[0]
    for i := 1; i < N; i++ {
        res = res ^ nums[i]
    }
    return res
}
1
2
3
4
5
6
7
8

268. 丢失的数字

• 思路1：排序

• 思路2：HashSet

• 思路3：等差数列

  func missingNumber(nums []int) int {
      N := len(nums)
      sum := (0 + N) * (N + 1) / 2
      res := 0
      for i := 0; i < N; i++ {
          res += nums[i]
      }
      return sum - res
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9

• 思路4：异或运算

  找缺失数、找出现一次数都是异或的经典应用。

  我们可以先求得 （1，n）的异或和 ，然后用这个结果对各个数字进行异或。

  这样最终得到的异或和表达式中，只有缺失元素出现次数为一次，其余元素均出现两次，即最终答案为缺失元素。

  func missingNumber(nums []int) int {
      N := len(nums)
      ans := 0
      for i := 0; i <= N; i++ {
          ans ^= i
      }
      for i := 0; i < N; i++ {
          ans ^= nums[i]
      }
      return ans
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11