给出基数为 -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 组成的数组。
示例：
输入：arr1 = [1,1,1,1,1], arr2 = [1,0,1] 输出：[1,0,0,0,0] 解释：arr1 表示 11，arr2 表示 5，输出表示 16 。
提示：
1 <= arr1.length <= 1000 1 <= arr2.length <= 1000 arr1 和 arr2 都不含前导零 arr1[i] 为 0 或 1 arr2[i] 为 0 或 1题解：普通的二进制数运算，就是1+1=0，然后进1，怎么来的，比如给样例 1010和110 注意这是普通的二进制数运算，那么1010=2 ^ 3 + 2 ^ 1，110=2 ^ 2 + 2 ^ 1。那么相加就是 2 ^ 3 + 2 ^ 2 + (1+1)*2 ^ 1=2 ^ 3 + 2 ^ 2 + 2 ^ 2 =2 ^ 3 + (1+1)*2 ^ 2=2 ^ 3 + 2 ^ 3=2 ^ 4。
所以分析这个题目的运算本质，以样例1来说明， [1,1,1,1,1]和[1,0,1] 等于=(-2) ^ 4 +(-2) ^ 3+(-2) ^ 2+(-2) ^ 1+(-2) ^ 0 + (-2) ^ 2+(-2) ^ 0 你会发现，-2就是指数为偶数时为正，奇数时为负，所以上面的可以看成
=2 ^ 4 - 2 ^ 3 + 2 ^ 2 - 2 ^ 1+2 ^ 0 + 2 ^ 2+2 ^ 0 =2 ^ 4 - 2 ^ 3 + (1+1)*2 ^ 2 - 2 ^ 1 + (1+1) * 2 ^ 0 =2 ^ 4 - 2 ^ 3 + 2 ^ 3 - 2 ^ 1 + 2 ^ 1 =2 ^ 4 所以最后的答案为10000
于是我们利用上面这种计算，进行同指数的合并计算，因为每次计算后都会产生新的指数，所以我们不断循环这个操作，直到没有重复的指数结束循环。
那么问题来了，我们知道，指数为奇数为负数，指数为偶数为正数，那么如果最后的运算结果恰好为一个2 ^ 3，怎么处理呢？
这里巧妙的地方来了，因为-2 ^ 3为1000，那么 2 ^ 3为什么呢？可以看成2 ^ 3 =2 ^ 4 - 2 ^ 3，所以2 ^ 3 为11000，哈哈，是不是很有趣，也因为这个，在每次我们不断合并同指数的数据时，还要再做一个判断，判断是否存在 2 ^ 3这样的违法数据，如果存在，就按我说的这种方法把2 ^ 3删除，把2 ^ 4和-2 ^3添加进去，同理-2 ^ 2这种违法数据可以看成2 ^ 2 - 2 ^ 3，同样的方式处理，然后呢，因为我们进行违法数据判断后可能产生新的指数类型数据，于是又要再进入反复合并同指数运算的循环中，所以比较冗余，很烦。
我写的代码感觉比较麻烦，大体思路就是这样，希望方便你理解。
AC代码
class Solution { public: struct Node { int key,index; }; vector<Node>q; static int cmp(Node a1,Node a2) { return a1.index>a2.index; } int INDEX[1010]; bool check() { memset(INDEX,0,sizeof(INDEX)); for(int i=0;i<q.size();i++) { INDEX[q[i].index]++; if(INDEX[q[i].index]>1)return false; } return true; } void fun() { vector<Node>p; while(check()==false)//反复合并同指数数据的循环 { sort(q.begin(),q.end(),cmp); p.clear(); p.push_back(q[0]); for(int i=1;i<q.size();i++) { int n=p.size()-1; if(p[n].index==q[i].index) { if(p[n].key==q[i].key) { p[n].index++; } else p[n].key=0; } else p.push_back(q[i]); } q.clear(); for(int i=0;i<p.size();i++) { if(p[i].key==0)continue; q.push_back(p[i]); } /* puts("*****************************"); for(int i=0;i<q.size();i++) cout<<q[i].key<<" "<<q[i].index<<endl; */ } p=q; q.clear(); for(int i=0;i<p.size();i++) { if(p[i].key==0)continue; if(p[i].index%2==0&&p[i].key==1||p[i].index%2==1&&p[i].key==-1)//判断是否有违法数据 q.push_back(p[i]); else { Node t1,t2; if(p[i].index%2==0) { t1.index=p[i].index; t1.key=1; t2.index=p[i].index+1; t2.key=-1; } else { t1.index=p[i].index+1; t1.key=1; t2.index=p[i].index; t2.key=-1; } q.push_back(t1); q.push_back(t2); } } /* puts("%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%"); for(int i=0;i<q.size();i++) cout<<q[i].key<<" "<<q[i].index<<endl; */ } vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) { int index=-1; for(int i=arr1.size()-1;i>=0;i--) { index++; if(arr1[i]==0)continue; Node t; if(index%2==0) t.key=1; else t.key=-1; t.index=index; q.push_back(t); } index=-1; for(int i=arr2.size()-1;i>=0;i--) { index++; if(arr2[i]==0)continue; Node t; if(index%2==0) t.key=1; else t.key=-1; t.index=index; q.push_back(t); } //再判断是否完全处理完毕，也就是，没有违法数据，也没有同指数类型数据 while(check()==false) fun(); // for(int i=0;i<q.size();i++) // cout<<q[i].key<<" ------ "<<q[i].index<<endl; //最后计算得到答案 vector<int>res; if(q.size()==0) { res.push_back(0); return res; } sort(q.begin(),q.end(),cmp); memset(INDEX,0,sizeof(INDEX)); for(int i=0;i<q.size();i++) INDEX[q[i].index]=1; for(int i=q[0].index;i>=0;i--) { if(INDEX[i]==1) res.push_back(1); else res.push_back(0); } return res; } };