不用加减乘除做加法,求2个数的平均数

1.不用加减乘除做加法

1.分析二进制加法规律:
╔═══════╤═════════════╗
║ Input │   Output    ║
╠═══╤═══╪═══════╤═════╣
║ A │ B │ carry │ sum ║
╟───┼───┼───────┼─────╢
║ 0 │ 0 │   0   │  0  ║
╟───┼───┼───────┼─────╢
║ 1 │ 0 │   0   │  1  ║
╟───┼───┼───────┼─────╢
║ 0 │ 1 │   0   │  1  ║
╟───┼───┼───────┼─────╢
║ 1 │ 1 │   1   │  0  ║
╚═══╧═══╧═══════╧═════╝
carry  = A&B
sum    = A^B
output = carry<<1 + sum = (A&B)<<1 + (A^B)
2.上面仍然用了加法,因此还要继续拆分加法,直到carry=0及没有进位结束
3.因此可以用下面方法计算A+B
  表示:进位<<1 + 无进位和
  最终得到:A+B = (A&B)<<1 + (A^B)
func getSum(A, B int) int {
    for B != 0 {
        carry := (A & B) << 1 // 进位
        A ^= B                // 无进位和
        B = carry             // 继续作为下一个加法迭代
    }
    return A
}
4.其实还有一种方案,我们可以观察(A|B)<<1
  表示:(进位+无进位和)<<1
  拆开:进位<<1 + 无进位和<<1 = 进位<<1 + 无进位和*2
  根据步骤3,可以将上面减去一个无进位和
  最终得到:A+B = (A|B)<<1 - (A^B)

2.求(A+B)/2

  1. 正常解法:(A+B)/2
  2. 高效解法:(A+B)>>1
  3. 防止溢出,二分查找常用:A+(A-B)/2 或 A+(A-B)>>1
  4. 根据上面步骤3推导:(A&B) + (A^B)>>1
  5. 根据上面步骤4推导:(A|B) - (A^B)>>1

3.比较求A,B平均数结果

package main

import (
    "fmt"
)

func main() {
    a, b := 123, 456
    check(a, b)
    check(-a, b)
    check(a, -b)
    check(b, a)
    check(-b, a)
    check(b, -a)
}

func check(A, B int) {
    fmt.Printf("(%d + %d)/2 = %d\n", A, B, (A+B)/2)
    fmt.Printf("(%d + %d)>>1 = %d\n", A, B, (A+B)>>1)
    fmt.Printf("%d + (%d - %d)/2 = %d\n", B, A, B, B+(A-B)/2)
    fmt.Printf("%d + (%d - %d)>>1 = %d\n", B, A, B, B+(A-B)>>1)
    fmt.Printf("%d + (%d - %d)>>1 = %d\n", B, A, B, B+(A-B)>>1)
    fmt.Printf("(%d & %d) + (%d ^ %d)>>1 = %d\n", A, B, A, B, (A&B)+(A^B)>>1)
    fmt.Printf("(%d | %d) - (%d ^ %d)>>1 = %d\n", A, B, A, B, (A|B)-(A^B)>>1)
}

根据结果可以看出最后2种方案在(A+B)为奇数时的表现结果不同
结果为正奇数时:
    (A&B) + (A^B)>>1为向下取整,(A|B) - (A^B)>>1为向上取整
结果为负奇数时相反

captcha