负二进制加法实现
一、背景知识
首先简单了解下什么是进制？
N进制，即表示位数可表示范围为 [0, N)(数学表示法，包括首，不包括尾)，比如二进制，位数上可用数字只有0或者1，遇2进位，而我们常用的十进制，位数可用数字为0-9，遇10进位，依此类推。
接着我们简单了解下 N(N!=10)进制与十进制的相互转换。
因为我们最熟悉的数字是十进制，所以当出现其他进制时，我们想知道它表示什么数，通常会先把它转换为十进制。N进制转十进制公式如下：
N进制数：
AnAn-1...A1A0
对应十进制：
A0 * N^0 + A1 * N^1 + ... + An * N^n而十进制转N进制：
十进制化n进制：反复除n取余数，除n的得数再取余数，直到得数为0，把余数按顺序从低位到高位写出即可，比如1234换八进制，第1次除8得154余2，154除8得19余2，19除8得2余3，2除8得0余2，所以最后得到2322
二、题意分析
而今天要做的题目有一点特殊，它是负二进制，且题目给出来的定义是可用数字为0或者1，但基数是 -2，计算举例如下：
-2进制：
1011
对应十进制：
1 * (-2)^0 + 1 * (-2)^2 + 0 * (-2)^2 + 1 ^ (-2)^3可以看到转换公式依然可以套用，到这里题目还没有什么太多的难度，但最后题目要求输出也要是负二进制，如果我们依然换上面的相互转换方法，也可以完成，但要去理解负二进制转十进制，有点难度，这里我们采用按位计算的方法来实现，时间复杂度为 O(n)，n为加数的位数。
按位计算，其实和十进制里列竖式计算是很像的，我们来看下：
其实同样道理，如果是以 -2 为基数，按位加法规律如下：
1、位数上按二进制的计算方式计算 2、如果位数相加超过2，需要进位，但进位方式是高两位均需要进1，因为以 -2 为基数，结果是一负一正的，高两位均进1，则可以抵掉一半，得到正确结果 3、如果在进位时，高位已经有为1的，可以直接将这个1变为0 4、如果相加小于2，则直接得结果即可
原理计算图如下：
三、上代码
class Solution:
def add(self, arr1, arr2):
"""
不管奇数位还是偶数位，只要相加大于2，高两位补1
其他照常
有一个需要注意点，如果有进位，且高位已经有一个为1，其实是可以抵消的
在代码实现里，只判断补位是否为1，如果为1则抵消，否则不抵消
"""
llen = len(arr2)
result = []
add_list = [0] * 1005 # 进位数字
i = llen - 1
j = 0
while True:
cur_sum = arr1[i] + arr2[i] + add_list[j] if i >= 0 else 0 + add_list[j]
if cur_sum == 0 and i < 0:
break
if cur_sum >= 2:
# 如果进位上有数字，且数字为1，直接抵消
if add_list[j + 1] == 1:
add_list[j + 1] = 0
cur_sum -= 2
result.append(cur_sum % 2)
else:
add_list[j + 1] = 1
add_list[j + 2] = 1
result.append(cur_sum % 2)
else:
result.append(cur_sum)
i -= 1
j += 1
result.reverse()
llen = len(result)
for i in range(0, llen):
if result[i] != 0:
return result[i:llen]
return [0]
def addNegabinary(self, arr1, arr2):
"""
:type arr1: List[int]
:type arr2: List[int]
:rtype: List[int]
"""
len1 = len(arr1)
len2 = len(arr2)
if len1 > len2:
arr2 = [0] * (len1 - len2) + arr2
return self.add(arr1, arr2)
else:
arr1 = [0] * (len2 - len1) + arr1
return self.add(arr1, arr2)
if __name__ == "__main__":
s = Solution()
print(s.addNegabinary([1], [1, 1]))代码说明： 因为不好控制结果输出长度，所以这里按照题目意思，位数不超过1000，所以提前申请了一个 1005 长度的列表，用空间换便利