002.位移运算与乘除

实验 §

实验 1 §

package main
 
import (
  "fmt"
  "math"
)
 
func main() {
  for i := -1; i > -5; i-- {
    v1 := div2(i)
    v2 := rightShift(i)
    mark := ""
    if v1 != v2 {
      mark = "!!!!!!"
    }
    fmt.Printf("[%d] 除法: %d; 右移: %d\t%s\n", i, v1, v2, mark)
  }
  fmt.Println()
 
  for i := -1; i > -5; i-- {
    v1 := times2(i)
    v2 := leftShift(i)
    mark := ""
    if v1 != v2 {
      mark = "!!!!!!"
    }
    fmt.Printf("[%d] 乘法: %d; 左移: %d\t%s\n", i, v1, v2, mark)
  }
  for i := math.MinInt/2 + 1; i < math.MinInt/2+6; i++ {
    v1 := times2(i)
    v2 := leftShift(i)
    mark := ""
    if v1 != v2 {
      mark = "!!!!!!"
    }
    fmt.Printf("[%d] 乘法: %d; 左移: %d\t%s\n", i, v1, v2, mark)
  }
  for i := math.MinInt; i < math.MinInt+5; i++ {
    v1 := times2(i)
    v2 := leftShift(i)
    mark := ""
    if v1 != v2 {
      mark = "!!!!!!"
    }
    fmt.Printf("[%d] 乘法: %d; 左移: %d\t%s\n", i, v1, v2, mark)
  }
}
 
func div2(a int) int {
  return a / 2
}
 
func rightShift(a int) int {
  return a >> 1
}
 
func times2(a int) int {
  return a * 2
}
 
func leftShift(a int) int {
  return a << 1
}

输出：

[-1] 除法: 0; 右移: -1  !!!!!!
[-2] 除法: -1; 右移: -1
[-3] 除法: -1; 右移: -2 !!!!!!
[-4] 除法: -2; 右移: -2
 
[-1] 乘法: -2; 左移: -2
[-2] 乘法: -4; 左移: -4
[-3] 乘法: -6; 左移: -6
[-4] 乘法: -8; 左移: -8
[-4611686018427387903] 乘法: -9223372036854775806; 左移: -9223372036854775806
[-4611686018427387902] 乘法: -9223372036854775804; 左移: -9223372036854775804
[-4611686018427387901] 乘法: -9223372036854775802; 左移: -9223372036854775802
[-4611686018427387900] 乘法: -9223372036854775800; 左移: -9223372036854775800
[-4611686018427387899] 乘法: -9223372036854775798; 左移: -9223372036854775798
[-9223372036854775808] 乘法: 0; 左移: 0
[-9223372036854775807] 乘法: 2; 左移: 2
[-9223372036854775806] 乘法: 4; 左移: 4
[-9223372036854775805] 乘法: 6; 左移: 6
[-9223372036854775804] 乘法: 8; 左移: 8

实验 2 §

package main
 
import (
  "fmt"
)
 
func main() {
  for i := -1; i > -9; i-- {
    v1 := div(i, 4)
    v2 := rightShift(i, 2)
    mark := ""
    if v1 != v2 {
      mark = "!!!!!!"
    }
    fmt.Printf("[%d] 除法: %d; 右移: %d\t%s\n", i, v1, v2, mark)
  }
}
 
func div(a, n int) int {
  return a / n
}
 
func rightShift(a, n int) int {
  return a >> n
}

输出：

[-1] 除法: 0; 右移: -1  !!!!!!
[-2] 除法: 0; 右移: -1  !!!!!!
[-3] 除法: 0; 右移: -1  !!!!!!
[-4] 除法: -1; 右移: -1
[-5] 除法: -1; 右移: -2 !!!!!!
[-6] 除法: -1; 右移: -2 !!!!!!
[-7] 除法: -1; 右移: -2 !!!!!!
[-8] 除法: -2; 右移: -2

实验 3 §

右移：向下取整

package main
 
import (
  "fmt"
  "math"
)
 
func main() {
  for i := -1; i > -999999; i-- {
    for j := 1; j <= 64; j++ {
      v1 := int(math.Floor(float64(i) / math.Pow(2, float64(j))))
      v2 := i >> j
      if v1 != v2 {
        fmt.Println("!!!!!!") // 没有打印
      }
    }
  }
}

实验 4 §

除法：向零取整

package main
 
import (
  "fmt"
  "math"
)
 
func main() {
  for i := -1; i > -999999; i-- {
    for j := 1; j <= 64; j++ {
      v1 := int(math.Ceil(float64(i) / math.Pow(2, float64(j))))
      v2 := i / int(math.Pow(2, float64(j)))
      if v1 != v2 {
        fmt.Println("!!!!!!") // 没有打印
      }
    }
  }
}

结论 §

• 非负数
  • 可以用左移 n 位代替乘 2 的 n 次方
  • 可以用右移 n 位代替除以 2 的 n 次方
• 负数
  • 可以用左移 n 位代替乘 2 的 n 次方
  • 不完全可以用右移 n 位代替除以 2 的 n 次方
    • a / n
      • a % n == 0 （整除）：可以代替
      • a % n != 0（不整除）：不可以代替
    • 本质：除法：向零取整；右移：向下取整