未分類

Sum of Two Integers

Sum of Two Integers

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

For Example:

1
Given a = 1 and b = 2, return 3.
提示 解題應用
BitManipulation XOR,AND

Default:

1
2
3
func getSum(a int, b int) int {
}

解答思路:

這讓我想到很久以前做的加法器Verilog,總之需要知道一些關於二進位上的實作,否則可能需要想一段時間,一般來說相加用XOR實作,因為1與0可以被保留,而1與1則歸0表示進位,正好是我們所需要的結果,但是還要再對那些進位的狀況做處理,會進位的狀況只有兩個1,所以先用AND來實做,接著才向左位移1,而這時候我們再用XOR對進位做相加,一直到沒有進位的狀況即可完成加法實作。

程式碼解說:

這邊用遞回來實作,a是兩數XOR不包含進位的狀況運算後的結果,而b則是兩數AND後左移代表進位後的結果,如果b為0表示沒有進位的問題就直接回傳a,否則就再重覆上述動作直到b為0為止

1
2
3
4
5
6
func getSum(a int, b int) int {
if b == 0 {
return a
}
return getSum(a^b, (a&b)<<1)
}

完整程式碼:

1
2
3
4
5
6
func getSum(a int, b int) int {
if b == 0 {
return a
}
return getSum(a^b, (a&b)<<1)
}

總結:

要用XOR與AND來實作二進位加法,一般來說相加用XOR實作,因為1與0可以被保留,而1與1則歸0表示進位,正好是我們所需要的結果,但是還要再對那些進位的狀況做處理,會進位的狀況只有兩個1,所以先用AND來實做,接著才向左位移1,而這時候我們再用XOR對進位做相加,一直到沒有進位的狀況即可完成加法實作。

分享到