adding-two-negabinary-numbers.go

package problem1073

func addNegabinary(A, B []int) []int {
	i, j := len(A)-1, len(B)-1
	res := make([]int, 0, i+j)
	carry := 0
	for i >= 0 || j >= 0 || carry != 0 {
		if i >= 0 {
			carry += A[i]
			i--
		}
		if j >= 0 {
			carry += B[j]
			j--
		}
		res = append(res, carry&1)
		carry = -(carry >> 1)
	}

	res = reverse(res)

	// cut leading zero
	i, end := 0, len(res)-1
	for i < end && res[i] == 0 {
		i++
	}
	return res[i:]
}

func reverse(A []int) []int {
	i, j := 0, len(A)-1
	for i < j {
		A[i], A[j] = A[j], A[i]
		i++
		j--
	}
	return A
}