• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

1073. 负二进制数相加

给出两个基数为-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]

说明:arr1代表11,arr2代表5,输出代表16。

示例 2:

输入:arr1=[0],arr2=[0]

输出:[0]

示例 3:

输入:arr1=[0],arr2=[1]

输出:[1]

提示:

1=arr1.length,arr2.length=1000

Arr1和arr2都是0或1。

Arr1和arr2没有前导0。

我的解题:

这个问题属于一个数学思想问题,主要难点在于理解计数负二进制数的概念,而不是写代码。只要你明白这个概念代码的想法,你就可以很容易地想出来。现在我们来研究一下这个问题的题干:两个基数为2的数arr1和arr2。基数是多少?基数是一个非常基本的数学概念。这个概念因为太基础,属于底层数学研究的范畴。因为不包含在九年义务教育中,可能只有大学数学专业的学生学习。以上纯属推测。反正我没学过这个概念。基数的概念可以简单理解为每N进1。比如十进制数每十进一,那么基数就是10,二进制数每2进1,那么基数就是2。但从更基本的概念来理解基数,属于集合论,基数就是集合的值域。比如十进制的每一位都是0~9,二进制的每一位都是0~1。这里我们简单的理解为每个基数输入1就够了,所以负二进制数就是负二进制数,真的很难理解。其实上面说的知识对于负二进制数来说可能是废话,用进一的思想理解负二进制数其实很难。

幸运的是,我们还有另外一个理解负二进制数的思路,那就是拆数的思路。我们可以把一个十进制数1234分解成:$1103 2*102 3101 4*100$。同样,我们可以把二进制数100110拆成:$125 0*24 023 1*22 121 0*20$,对于负二进制数11111,我们可以拆成$ 1(-2)41 *(2)31(-2)21 *(2)11(-2)0 $=1-24-8 16=11,正好对应题目中的值,表示负二进制数的计算。

其实涉及到一部分朴素的中国传统哲学,就是二元论,阴阳对应,阴阳互变。二进制数和负二进制数的区别在于二进制数的每一位上面的数都是正的。所以小数的结果可以通过除以数字计算后直接相加得到。但负二进制数的每一位都有符号差,奇数为正,偶数为负。这不仅表明我们在计算和的时候需要引入符号,也意味着奇数和偶数是相反的。奇数和偶数上的数字不仅有数值大小的概念,还有正负性质,其实是可以转化的。一个数是正还是负实际上并不取决于它是奇数还是偶数,而是

取决于我们的出发视角,如果我们以其中的第n位出发,并认为其是正的,那么它相邻的两位必定都是负的,也就是说我们在负二进制数中位数之间两两为负,两两相反,简而言之,相邻位上的进位是负的,我们再具体一些,我们以11111+101为例:

image-20220502214647126

  可见结果完全正确,这实际上就是因为在负二进制数中,数位之间两两为负,低位相当于高位来说永远是负数,而低位的进位贡献,相当于高位来说自然是一个负贡献,因此向高位的进位就是减1,我们现在再来研究一下借位概念:

image-20220502215038678

  这里出现了不够减的现象,因此需要向高位借位,需要注意的是,借位的行为,在普通进制运算时本是一个负贡献,但是这里的低位相对高位来讲是负的,因此高位要是想要给低位进行一个正贡献,那么需要献给低位一个和低位相同性质的数,而这个数和低位性质相同,和自身自然性质相反,也就是说,这个数字的付出,是付出了一个和自身相反的数字,而负负得正,失去一个和自身相反的数字相当于得到了一个和自身性质相同的数字,也就是说向低位借位,实际上对自己做了一个正贡献,在二进制数中,向低位借位,会导致自身减1,低位加2,而在负二进制数中这个情况变得相当离奇,向低位借位,会让低位获得2,自己也获得1,如下:

image-20220502215901506

  在数字的计算当中,进位和借位就是加和计算的全部了,因此根据上面这些数学原理,我们就可以进行负二进制数的相加算法设计了。对于该问题的算法设计,我们可以根据这个计数原理设计成这样的:对于两个数组先直接相加,结果保留在较长的那个数组中,如果两个数组等长那么保存在任一个数组中,然后我们遍历这个保存结果的数组,如果某一位n是2或者2以上的数字,我们便将其置为(n-2),而往高位进一位,这个进位是-1,如果够减那么就直接减1,否则向更高位借位,并向那个更高位加1位,这种运算最终可能会在最高位发生一个进位,我们根据这个进位的具体情况进行数组的扩容,如果是一个-1,那么我们需要扩容两位,并先补零,然后按照借位法则进行运算,除了这种进位情况,无其他的进位情况了,这个和我们的负二进制数的性质有关,然后我们返回这个数组即可。我们以11111+101为例示范:

  1 1 1 1 1
+     1 0 1
—————————————
  1 1 2 1 2
  
第一步: 1 1 2 1 2
第二步: 1 1 2 0 0
第三布: 1 0 0 0 0

  对于有借位的情况我们这样计算,如1001+1001:

 1 0 0 1
+1 0 0 1
---------
2 0 0 2
第一步:2002
第二步:2110
第三步:002110
第四步:110110

  只有结果的第一位是2以及2以上的数字是才会向高位产生借位,此时我们就需要扩容两位,根据规律我们发现直接将这两位赋值为11就行了。因此我们可以书写算法如下:

class Solution {
    public int[] addNegabinary(int[] arr1, int[] arr2) {
        // 定义规则:0+1=1,进位向前边减一,够减则减,不够减则借位
        int[] outCome = null;
        if (arr1.length > arr2.length) {
            for (int i = 1; i <= arr2.length; i++) {
                arr1[arr1.length - i] += arr2[arr2.length - i];
            }
            outCome = arr1;
        } else {
            for (int i = 1; i <= arr1.length; i++) {
                arr2[arr2.length - i] += arr1[arr1.length - i];
            }
            outCome = arr2;
        }
        // System.out.println(Arrays.toString(outCome));
        int add = 0;
        for (int i = outCome.length - 1; i > 0; i--) {
            if (outCome[i] + add >= 2) {
                add = -1;
                outCome[i] -= 2;
            } else if (outCome[i] + add < 0) {
                outCome[i - 1] += 1;
                outCome[i] = 1;
                add = 0;
            } else {
                outCome[i] += add;
                add = 0;
            }
        }
        outCome[0] += add;
        //System.out.println(Arrays.toString(outCome));
        if (outCome[0] >= 2) {
            outCome[0] -= 2;
            int[] newOutCome = new int[outCome.length + 2];
            newOutCome[0] = 1;
            newOutCome[1] = 1;
            for (int i = 0; i < outCome.length; i++) {
                newOutCome[2 + i] = outCome[i];
            }
            outCome = newOutCome;
        }
        // System.out.println(Arrays.toString(outCome));
        if (outCome[0] == 0) {
            int zlength = 0;
            while (zlength < outCome.length && outCome[zlength] == 0) {
                zlength++;
            }
            System.out.println(zlength);
            if (zlength == outCome.length) {
                outCome = new int[1];
                outCome[0] = 0;
            } else {
                int[] newOutCome = new int[outCome.length - zlength];
                for (int i = 0; i < newOutCome.length; i++) {
                    newOutCome[i] = outCome[zlength + i];
                }
                outCome = newOutCome;
            }
        }
        return outCome;
    }
}
Link to comment
Share on other sites