未分類

Sum of Two Integers

BitManipulation, Go, LeetCode

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對進位做相加，一直到沒有進位的狀況即可完成加法實作。

分享到