Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.
Example:
Given a = 1 and b = 2, return 3.
package main
import (
“fmt”
“math”
)
func getSum(a int, b int) int {
var result int
// 分别判断几种情况
// a,b是否同号，a,b的绝对值谁大(也就是转换成二进制之后谁的长度更大)
if a * b < 0 {
if math.Abs(float64(a)) < math.Abs(float64(b)) {
if a < b {
result = one_negative(int(math.Abs(float64(a))), int(math.Abs(float64(b))), true)
} else {
result = one_negative(int(math.Abs(float64(a))), int(math.Abs(float64(b))), false)
}
} else {
if a < b {
result = one_negative(int(math.Abs(float64(a))), int(math.Abs(float64(b))), false)
} else {
result = one_negative(int(math.Abs(float64(a))), int(math.Abs(float64(b))), true)
}
}
} else {
if a < 0 {
result = both_positive(int(math.Abs(float64(a))), int(math.Abs(float64(b))), false)
} else {
result = both_positive(int(math.Abs(float64(a))), int(math.Abs(float64(b))), true)
}
}
return result
}
// a,b同号的情况
func both_positive(a int, b int, negative bool) int {
var binary_a = get_binary(a)
var binary_b = get_binary(b)
if len(binary_a) > len(binary_b) {
binary_a, binary_b = binary_b, binary_a
}
for i := len(binary_a) – 1; i >= 0; i– {
if binary_a[i] == 1 {
for j := len(binary_b) – 1 – (len(binary_a) – 1 – i); j >= 0; j– {
if binary_b[j] == 1 {
binary_b[j] = 0
if j == 0 {
// 向高位进1
var temp_b = make([]int, len(binary_b)+1)
copy(temp_b[1:], binary_b)
binary_b = temp_b
j++
}
} else {
binary_b[j] = 1
break
}
}
}
}
if negative {
return get_decimal(binary_b)
} else {
return 0 – get_decimal(binary_b)
}
}
// a,b不同号的情况，其中b的绝对值大于a
func one_negative(a int, b int, negative bool) int {
var binary_a = get_binary(a)
var binary_b = get_binary(b)
for i := len(binary_a) – 1; i >= 0; i– {
if binary_a[i] == 1 {
for j := len(binary_b) – 1 – (len(binary_a) – 1 – i); j >= 0; j– {
if binary_b[j] == 0 {
binary_b[j] = 1
} else {
binary_b[j] = 0
break
}
}
}
}
if negative {
return get_decimal(binary_b)
} else {
return 0 – get_decimal(binary_b)
}
}
// 从二进制slice转换成十进制
func get_decimal(slice []int) int {
var sum = 0
for i := 0; i < len(slice); i++ {
sum += int(math.Exp2(float64(len(slice)-1-i))) * slice[i]
}
return sum
}
// 转换成二进制slice
func get_binary(num int) []int {
var remainder int
var slice = make([]int, 0)
for num >= 2 {
remainder = num % 2
slice = append(slice, remainder)
num = num / 2
}
slice = append(slice, num)
for i, j := 0, len(slice)-1; i < j; i, j = i+1, j-1 {
slice[i], slice[j] = slice[j], slice[i]
}
return slice
}
func main() {
fmt.Println(getSum(1, -1))
}
[/go]
另一种简单的算法
[go]
package main
import "fmt"
func getSum(a int, b int) int {
if b == 0 {
return a
}
sum := a ^ b
fmt.Println(sum)
carry := (a & b) < < 1
return getSum(sum, carry)
}
func main() {
fmt.Println(getSum(-1, 3))
}
[/go]
参考地址：http://www.cnblogs.com/grandyang/p/5631814.html