蓝桥杯day01——负二进制数相加

题目描述

给出基数为 -2 的两个数 arr1 和 arr2，返回两数相加的结果。

数字以 数组形式 给出：数组由若干 0 和 1 组成，按最高有效位到最低有效位的顺序排列。例如，arr = [1,1,0,1] 表示数字 (-2)^3 + (-2)^2 + (-2)^0 = -3。数组形式 中的数字 arr 也同样不含前导零：即 arr == [0] 或 arr[0] == 1。

返回相同表示形式的 arr1 和 arr2 相加的结果。两数的表示形式为：不含前导零、由若干 0 和 1 组成的数组。

示例 1：

输入：arr1 = [1,1,1,1,1], arr2 = [1,0,1] 输出：[1,0,0,0,0] 解释：arr1 表示 11，arr2 表示 5，输出表示 16 。

示例 2：

输入：arr1 = [0], arr2 = [0] 输出：[0]

示例 3：

输入：arr1 = [0], arr2 = [1] 输出：[1]

提示：

1 <= arr1.length, arr2.length <= 1000arr1[i] 和 arr2[i] 都是 0 或 1arr1 和 arr2 都没有前导0

 

解析

实现两个以负二进制形式表示的数的加法。让我们一步步来解析下面的代码：

函数首先获取两个输入数组的长度，分别为arr1和arr2，并计算它们的和sum1和sum2。在这个过程中，它是从数组的最低位（右边）开始，并使用负二的幂（从1到m和n）进行加权。之后，将这两个和相加，得到的结果是两个数的和s。然后，进入一个循环，该循环会一直执行，直到s变为0。在每次循环中，它都会取s的绝对值的余数，然后插入到结果列表的开头。然后，它会将s减去这个余数并除以-2，然后再检查s是否为0。如果s为0，那么就会跳出循环。最后，返回结果列表。这个列表就是原始的输入数组的负二进制表示形式的和。

这个代码的主要思想是模拟在常规二进制系统中的加法运算，但所有的运算都以负二进制的格式进行。

python代码 class Solution: def addNegabinary(self, arr1: list[int], arr2: list[int]) -> list[int]: m=len(arr1) n=len(arr2) sum1=0 sum2=0 for i in range(m): sum1+=arr1[m-i-1]*(-2)**(i) for j in range(n): sum2+=arr2[n-j-1]*(-2)**(j) i=0 s = sum1 + sum2 ls=[] while 1: yv=int(abs(s%(-2))) ls.insert(0,yv) s=(s-yv)//(-2) if s==0: break return ls 运行结果