题目描述：
给出基数为 $-2$ 的两个数arr1和 arr2，返回两数相加的结果。数字以数组的方式给出，高位到低位，不含前导零。返回的结果也不包含前导零。
数据范围： $1\le n \le 1000$
题解：
基数为 $-2$ ，则每一位表示 $(-2)^i$ ，并且每一位的权重是正负交替的。
进位情况：第 $i$ 位全为 $1$ ，相加的话，产生进位。 $1\times (-2)^i + 1\times(-2)^i = 2 \times (-2) ^ i = -1\times(-2)^{i + 1}$ ，可以看到进位为 $-1$ 。
但是需要考虑，如果前面一位为 $0$ ，那么就会出现 $-1$ ，需要把 $-1$ 转为 $0$ 或 $1$ 。根据上面的公式可以得知，两个该位加可以得到一个高位减，因此可以先转为 $1$ ，那么高位就需要进位 $1$ 。 $-1\times(-2)^i = 1\times(-2)^i - 2\times(-2)^i = 1\times(2)^i + 1\times (-2)^{i + 1}$ 。可以看出来 $-1$ 修改更改为 $1$ ，并且产生一个 $1$ 的进位。
写代码时，可以写成一下这种形式，循环条件写成 ||，里面的根据 i,j的值选择当前的操作数。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
vector<int> addNegabinary(vector<int> &arr1, vector<int> &arr2)
{
vector<int> ans;
int add = 0, i, j, tmp, a, b;
for (i = arr1.size() - 1, j = arr2.size() - 1; i >= 0 || j >= 0 || add; --i, --j)
{
a = (i >= 0 ? arr1[i] : 0);
b = (j >= 0 ? arr2[j] : 0);
tmp = a + b + add;
if (tmp >= 2)
{
add = -(tmp / 2);
tmp = tmp % 2;
}
else if (tmp == -1)
{
tmp = 1;
add = 1;
}
else
add = 0;
ans.emplace_back(tmp);
}
i = ans.size() - 1;
while (i > 0 && ans[i] == 0)
i--;
ans.resize(i + 1);
reverse(ans.begin(), ans.end());
return ans;
}
};
|