算法-每天一道题(29)-371. Sum of Two Integers-进制转换

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

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部