1 /*
2  *  Licensed to the Apache Software Foundation (ASF) under one or more
3  *  contributor license agreements.  See the NOTICE file distributed with
4  *  this work for additional information regarding copyright ownership.
5  *  The ASF licenses this file to You under the Apache License, Version 2.0
6  *  (the "License"); you may not use this file except in compliance with
7  *  the License.  You may obtain a copy of the License at
8  *
9  *     http://www.apache.org/licenses/LICENSE-2.0
10  *
11  *  Unless required by applicable law or agreed to in writing, software
12  *  distributed under the License is distributed on an "AS IS" BASIS,
13  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  *  See the License for the specific language governing permissions and
15  *  limitations under the License.
16  */
17 
18 package java.math;
19 
20 /**
21  * The library implements some logical operations over {@code BigInteger}. The
22  * operations provided are listed below.
23  * <ul type="circle">
24  * <li>not</li>
25  * <li>and</li>
26  * <li>andNot</li>
27  * <li>or</li>
28  * <li>xor</li>
29  * </ul>
30  */
31 class Logical {
32 
33     /** Just to denote that this class can't be instantiated. */
34 
Logical()35     private Logical() {}
36 
37 
38     /** @see BigInteger#not() */
not(BigInteger val)39     static BigInteger not(BigInteger val) {
40         if (val.sign == 0) {
41             return BigInteger.MINUS_ONE;
42         }
43         if (val.equals(BigInteger.MINUS_ONE)) {
44             return BigInteger.ZERO;
45         }
46         int[] resDigits = new int[val.numberLength + 1];
47         int i;
48 
49         if (val.sign > 0) {
50             // ~val = -val + 1
51             if (val.digits[val.numberLength - 1] != -1) {
52                 for (i = 0; val.digits[i] == -1; i++) {
53                     ;
54                 }
55             } else {
56                 for (i = 0; (i < val.numberLength) && (val.digits[i] == -1); i++) {
57                     ;
58                 }
59                 if (i == val.numberLength) {
60                     resDigits[i] = 1;
61                     return new BigInteger(-val.sign, i + 1, resDigits);
62                 }
63             }
64             // Here a carry 1 was generated
65         } else {// (val.sign < 0)
66             // ~val = -val - 1
67             for (i = 0; val.digits[i] == 0; i++) {
68                 resDigits[i] = -1;
69             }
70             // Here a borrow -1 was generated
71         }
72         // Now, the carry/borrow can be absorbed
73         resDigits[i] = val.digits[i] + val.sign;
74         // Copying the remaining unchanged digit
75         for (i++; i < val.numberLength; i++) {
76             resDigits[i] = val.digits[i];
77         }
78         return new BigInteger(-val.sign, i, resDigits);
79     }
80 
81     /** @see BigInteger#and(BigInteger) */
and(BigInteger val, BigInteger that)82     static BigInteger and(BigInteger val, BigInteger that) {
83         if (that.sign == 0 || val.sign == 0) {
84             return BigInteger.ZERO;
85         }
86         if (that.equals(BigInteger.MINUS_ONE)){
87             return val;
88         }
89         if (val.equals(BigInteger.MINUS_ONE)) {
90             return that;
91         }
92 
93         if (val.sign > 0) {
94             if (that.sign > 0) {
95                 return andPositive(val, that);
96             } else {
97                 return andDiffSigns(val, that);
98             }
99         } else {
100             if (that.sign > 0) {
101                 return andDiffSigns(that, val);
102             } else if (val.numberLength > that.numberLength) {
103                 return andNegative(val, that);
104             } else {
105                 return andNegative(that, val);
106             }
107         }
108     }
109 
110     /** @return sign = 1, magnitude = val.magnitude & that.magnitude*/
andPositive(BigInteger val, BigInteger that)111     static BigInteger andPositive(BigInteger val, BigInteger that) {
112         // PRE: both arguments are positive
113         int resLength = Math.min(val.numberLength, that.numberLength);
114         int i = Math.max(val.getFirstNonzeroDigit(), that.getFirstNonzeroDigit());
115 
116         if (i >= resLength) {
117             return BigInteger.ZERO;
118         }
119 
120         int[] resDigits = new int[resLength];
121         for ( ; i < resLength; i++) {
122             resDigits[i] = val.digits[i] & that.digits[i];
123         }
124 
125         return new BigInteger(1, resLength, resDigits);
126     }
127 
128     /** @return sign = positive.magnitude & magnitude = -negative.magnitude */
andDiffSigns(BigInteger positive, BigInteger negative)129     static BigInteger andDiffSigns(BigInteger positive, BigInteger negative) {
130         // PRE: positive is positive and negative is negative
131         int iPos = positive.getFirstNonzeroDigit();
132         int iNeg = negative.getFirstNonzeroDigit();
133 
134         // Look if the trailing zeros of the negative will "blank" all
135         // the positive digits
136         if (iNeg >= positive.numberLength) {
137             return BigInteger.ZERO;
138         }
139         int resLength = positive.numberLength;
140         int[] resDigits = new int[resLength];
141 
142         // Must start from max(iPos, iNeg)
143         int i = Math.max(iPos, iNeg);
144         if (i == iNeg) {
145             resDigits[i] = -negative.digits[i] & positive.digits[i];
146             i++;
147         }
148         int limit = Math.min(negative.numberLength, positive.numberLength);
149         for ( ; i < limit; i++) {
150             resDigits[i] = ~negative.digits[i] & positive.digits[i];
151         }
152         // if the negative was shorter must copy the remaining digits
153         // from positive
154         if (i >= negative.numberLength) {
155             for ( ; i < positive.numberLength; i++) {
156                 resDigits[i] = positive.digits[i];
157             }
158         } // else positive ended and must "copy" virtual 0's, do nothing then
159 
160         return new BigInteger(1, resLength, resDigits);
161     }
162 
163     /** @return sign = -1, magnitude = -(-longer.magnitude & -shorter.magnitude)*/
andNegative(BigInteger longer, BigInteger shorter)164     static BigInteger andNegative(BigInteger longer, BigInteger shorter) {
165         // PRE: longer and shorter are negative
166         // PRE: longer has at least as many digits as shorter
167         int iLonger = longer.getFirstNonzeroDigit();
168         int iShorter = shorter.getFirstNonzeroDigit();
169 
170         // Does shorter matter?
171         if (iLonger >= shorter.numberLength) {
172             return longer;
173         }
174 
175         int resLength;
176         int[] resDigits;
177         int i = Math.max(iShorter, iLonger);
178         int digit;
179         if (iShorter > iLonger) {
180             digit = -shorter.digits[i] & ~longer.digits[i];
181         } else if (iShorter < iLonger) {
182             digit = ~shorter.digits[i] & -longer.digits[i];
183         } else {
184             digit = -shorter.digits[i] & -longer.digits[i];
185         }
186         if (digit == 0) {
187             for (i++; i < shorter.numberLength && (digit = ~(longer.digits[i] | shorter.digits[i])) == 0; i++)
188                 ;  // digit = ~longer.digits[i] & ~shorter.digits[i]
189             if (digit == 0) {
190                 // shorter has only the remaining virtual sign bits
191                 for ( ; i < longer.numberLength && (digit = ~longer.digits[i]) == 0; i++)
192                     ;
193                 if (digit == 0) {
194                     resLength = longer.numberLength + 1;
195                     resDigits = new int[resLength];
196                     resDigits[resLength - 1] = 1;
197 
198                     return new BigInteger(-1, resLength, resDigits);
199                 }
200             }
201         }
202         resLength = longer.numberLength;
203                 resDigits = new int[resLength];
204         resDigits[i] = -digit;
205         for (i++; i < shorter.numberLength; i++){
206             // resDigits[i] = ~(~longer.digits[i] & ~shorter.digits[i];)
207             resDigits[i] = longer.digits[i] | shorter.digits[i];
208         }
209         // shorter has only the remaining virtual sign bits
210         for ( ; i < longer.numberLength; i++){
211             resDigits[i] = longer.digits[i];
212         }
213 
214         return new BigInteger(-1, resLength, resDigits);
215     }
216 
217     /** @see BigInteger#andNot(BigInteger) */
andNot(BigInteger val, BigInteger that)218     static BigInteger andNot(BigInteger val, BigInteger that) {
219         if (that.sign == 0 ) {
220             return val;
221         }
222         if (val.sign == 0) {
223             return BigInteger.ZERO;
224         }
225         if (val.equals(BigInteger.MINUS_ONE)) {
226             return that.not();
227         }
228         if (that.equals(BigInteger.MINUS_ONE)){
229             return BigInteger.ZERO;
230         }
231 
232         //if val == that, return 0
233 
234        if (val.sign > 0) {
235             if (that.sign > 0) {
236                 return andNotPositive(val, that);
237             } else {
238                 return andNotPositiveNegative(val, that);
239                     }
240                 } else {
241             if (that.sign > 0) {
242                 return andNotNegativePositive(val, that);
243             } else  {
244                 return andNotNegative(val, that);
245             }
246         }
247     }
248 
249     /** @return sign = 1, magnitude = val.magnitude & ~that.magnitude*/
andNotPositive(BigInteger val, BigInteger that)250     static BigInteger andNotPositive(BigInteger val, BigInteger that) {
251         // PRE: both arguments are positive
252         int[] resDigits = new int[val.numberLength];
253 
254         int limit = Math.min(val.numberLength, that.numberLength);
255         int i;
256         for (i = val.getFirstNonzeroDigit(); i < limit; i++) {
257             resDigits[i] = val.digits[i] & ~that.digits[i];
258         }
259         for ( ; i < val.numberLength; i++) {
260             resDigits[i] = val.digits[i];
261         }
262 
263         return new BigInteger(1, val.numberLength, resDigits);
264     }
265 
266     /** @return sign = 1, magnitude = positive.magnitude & ~(-negative.magnitude)*/
andNotPositiveNegative(BigInteger positive, BigInteger negative)267     static BigInteger andNotPositiveNegative(BigInteger positive, BigInteger negative) {
268         // PRE: positive > 0 && negative < 0
269         int iNeg = negative.getFirstNonzeroDigit();
270         int iPos = positive.getFirstNonzeroDigit();
271 
272         if (iNeg >= positive.numberLength) {
273             return positive;
274         }
275 
276         int resLength = Math.min(positive.numberLength, negative.numberLength);
277         int[] resDigits = new int[resLength];
278 
279         // Always start from first non zero of positive
280         int i = iPos;
281         for ( ; i < iNeg; i++) {
282             // resDigits[i] = positive.digits[i] & -1 (~0)
283             resDigits[i] = positive.digits[i];
284         }
285         if (i == iNeg) {
286             resDigits[i] = positive.digits[i] & (negative.digits[i] - 1);
287             i++;
288         }
289         for ( ; i < resLength; i++) {
290             // resDigits[i] = positive.digits[i] & ~(~negative.digits[i]);
291             resDigits[i] = positive.digits[i] & negative.digits[i];
292         }
293 
294         return new BigInteger(1, resLength, resDigits);
295     }
296 
297     /** @return sign = -1, magnitude = -(-negative.magnitude & ~positive.magnitude)*/
andNotNegativePositive(BigInteger negative, BigInteger positive)298     static BigInteger andNotNegativePositive(BigInteger negative, BigInteger positive) {
299         // PRE: negative < 0 && positive > 0
300         int resLength;
301         int[] resDigits;
302         int limit;
303         int digit;
304 
305         int iNeg = negative.getFirstNonzeroDigit();
306         int iPos = positive.getFirstNonzeroDigit();
307 
308         if (iNeg >= positive.numberLength) {
309             return negative;
310         }
311 
312         resLength = Math.max(negative.numberLength, positive.numberLength);
313         int i = iNeg;
314         if (iPos > iNeg) {
315             resDigits = new int[resLength];
316             limit = Math.min(negative.numberLength, iPos);
317             for ( ; i < limit; i++) {
318                 // 1st case:  resDigits [i] = -(-negative.digits[i] & (~0))
319                 // otherwise: resDigits[i] = ~(~negative.digits[i] & ~0)  ;
320                 resDigits[i] = negative.digits[i];
321             }
322             if (i == negative.numberLength) {
323                 for (i = iPos; i < positive.numberLength; i++) {
324                     // resDigits[i] = ~(~positive.digits[i] & -1);
325                     resDigits[i] = positive.digits[i];
326                 }
327             }
328         } else {
329             digit = -negative.digits[i] & ~positive.digits[i];
330             if (digit == 0) {
331                 limit = Math.min(positive.numberLength, negative.numberLength);
332                 for (i++; i < limit && (digit = ~(negative.digits[i] | positive.digits[i])) == 0; i++)
333                     ; // digit = ~negative.digits[i] & ~positive.digits[i]
334                 if (digit == 0) {
335                     // the shorter has only the remaining virtual sign bits
336                     for ( ; i < positive.numberLength && (digit = ~positive.digits[i]) == 0; i++)
337                         ; // digit = -1 & ~positive.digits[i]
338                     for ( ; i < negative.numberLength && (digit = ~negative.digits[i]) == 0; i++)
339                         ; // digit = ~negative.digits[i] & ~0
340                     if (digit == 0) {
341                         resLength++;
342                         resDigits = new int[resLength];
343                         resDigits[resLength - 1] = 1;
344 
345                         return new BigInteger(-1, resLength, resDigits);
346                     }
347                 }
348             }
349                         resDigits = new int[resLength];
350             resDigits[i] = -digit;
351             i++;
352                     }
353 
354         limit = Math.min(positive.numberLength, negative.numberLength);
355         for ( ; i < limit; i++) {
356             //resDigits[i] = ~(~negative.digits[i] & ~positive.digits[i]);
357             resDigits[i] = negative.digits[i] | positive.digits[i];
358         }
359         // Actually one of the next two cycles will be executed
360         for ( ; i < negative.numberLength; i++) {
361             resDigits[i] = negative.digits[i];
362                 }
363         for ( ; i < positive.numberLength; i++) {
364             resDigits[i] = positive.digits[i];
365         }
366 
367         return new BigInteger(-1, resLength, resDigits);
368     }
369 
370     /** @return sign = 1, magnitude = -val.magnitude & ~(-that.magnitude)*/
andNotNegative(BigInteger val, BigInteger that)371     static BigInteger andNotNegative(BigInteger val, BigInteger that) {
372         // PRE: val < 0 && that < 0
373         int iVal = val.getFirstNonzeroDigit();
374         int iThat = that.getFirstNonzeroDigit();
375 
376         if (iVal >= that.numberLength) {
377             return BigInteger.ZERO;
378         }
379 
380         int resLength = that.numberLength;
381         int[] resDigits = new int[resLength];
382         int limit;
383         int i = iVal;
384         if (iVal < iThat) {
385             // resDigits[i] = -val.digits[i] & -1;
386             resDigits[i] = -val.digits[i];
387             limit = Math.min(val.numberLength, iThat);
388             for (i++; i < limit; i++) {
389                 // resDigits[i] = ~val.digits[i] & -1;
390                 resDigits[i] = ~val.digits[i];
391             }
392             if (i == val.numberLength) {
393                 for ( ; i < iThat; i++) {
394                     // resDigits[i] = -1 & -1;
395                     resDigits[i] = -1;
396                 }
397                 // resDigits[i] = -1 & ~-that.digits[i];
398                 resDigits[i] = that.digits[i] - 1;
399         } else {
400                 // resDigits[i] = ~val.digits[i] & ~-that.digits[i];
401                 resDigits[i] = ~val.digits[i] & (that.digits[i] - 1);
402             }
403         } else if (iThat < iVal ) {
404             // resDigits[i] = -val.digits[i] & ~~that.digits[i];
405             resDigits[i] = -val.digits[i] & that.digits[i];
406         } else {
407             // resDigits[i] = -val.digits[i] & ~-that.digits[i];
408             resDigits[i] = -val.digits[i] & (that.digits[i] - 1);
409             }
410 
411         limit = Math.min(val.numberLength, that.numberLength);
412         for (i++; i < limit; i++) {
413             // resDigits[i] = ~val.digits[i] & ~~that.digits[i];
414             resDigits[i] = ~val.digits[i] & that.digits[i];
415         }
416         for ( ; i < that.numberLength; i++) {
417             // resDigits[i] = -1 & ~~that.digits[i];
418             resDigits[i] = that.digits[i];
419         }
420 
421         return new BigInteger(1, resLength, resDigits);
422     }
423 
424     /** @see BigInteger#or(BigInteger) */
or(BigInteger val, BigInteger that)425     static BigInteger or(BigInteger val, BigInteger that) {
426         if (that.equals(BigInteger.MINUS_ONE) || val.equals(BigInteger.MINUS_ONE)) {
427             return BigInteger.MINUS_ONE;
428         }
429         if (that.sign == 0) {
430             return val;
431         }
432         if (val.sign == 0) {
433             return that;
434         }
435 
436         if (val.sign > 0) {
437             if (that.sign > 0) {
438                 if (val.numberLength > that.numberLength) {
439                     return orPositive(val, that);
440                 } else {
441                     return orPositive(that, val);
442                 }
443             } else {
444                 return orDiffSigns(val, that);
445             }
446         } else {
447             if (that.sign > 0) {
448                 return orDiffSigns(that, val);
449             } else if (that.getFirstNonzeroDigit() > val.getFirstNonzeroDigit()) {
450                 return orNegative(that, val);
451             } else {
452                 return orNegative(val, that);
453             }
454         }
455     }
456 
457     /** @return sign = 1, magnitude = longer.magnitude | shorter.magnitude*/
orPositive(BigInteger longer, BigInteger shorter)458     static BigInteger orPositive(BigInteger longer, BigInteger shorter) {
459         // PRE: longer and shorter are positive;
460         // PRE: longer has at least as many digits as shorter
461         int resLength = longer.numberLength;
462         int[] resDigits = new int[resLength];
463 
464         int i;
465         for (i = 0; i < shorter.numberLength; i++) {
466             resDigits[i] = longer.digits[i] | shorter.digits[i];
467         }
468         for ( ; i < resLength; i++) {
469             resDigits[i] = longer.digits[i];
470         }
471 
472         return new BigInteger(1, resLength, resDigits);
473     }
474 
475     /** @return sign = -1, magnitude = -(-val.magnitude | -that.magnitude) */
orNegative(BigInteger val, BigInteger that)476     static BigInteger orNegative(BigInteger val, BigInteger that){
477         // PRE: val and that are negative;
478         // PRE: val has at least as many trailing zeros digits as that
479         int iThat = that.getFirstNonzeroDigit();
480         int iVal = val.getFirstNonzeroDigit();
481         int i;
482 
483         if (iVal >= that.numberLength) {
484             return that;
485         }else if (iThat >= val.numberLength) {
486             return val;
487         }
488 
489         int resLength = Math.min(val.numberLength, that.numberLength);
490         int[] resDigits = new int[resLength];
491 
492         //Looking for the first non-zero digit of the result
493         if (iThat == iVal) {
494             resDigits[iVal] = -(-val.digits[iVal] | -that.digits[iVal]);
495             i = iVal;
496         } else {
497             for (i = iThat; i < iVal; i++) {
498                 resDigits[i] = that.digits[i];
499             }
500             resDigits[i] = that.digits[i] & (val.digits[i] - 1);
501         }
502 
503         for (i++; i < resLength; i++) {
504             resDigits[i] = val.digits[i] & that.digits[i];
505         }
506 
507         return new BigInteger(-1, resLength, resDigits);
508     }
509 
510     /** @return sign = -1, magnitude = -(positive.magnitude | -negative.magnitude) */
orDiffSigns(BigInteger positive, BigInteger negative)511     static BigInteger orDiffSigns(BigInteger positive, BigInteger negative){
512         // Jumping over the least significant zero bits
513         int iNeg = negative.getFirstNonzeroDigit();
514         int iPos = positive.getFirstNonzeroDigit();
515         int i;
516         int limit;
517 
518         // Look if the trailing zeros of the positive will "copy" all
519         // the negative digits
520         if (iPos >= negative.numberLength) {
521             return negative;
522         }
523         int resLength = negative.numberLength;
524         int[] resDigits = new int[resLength];
525 
526         if (iNeg < iPos ) {
527             // We know for sure that this will
528             // be the first non zero digit in the result
529             for (i = iNeg; i < iPos; i++) {
530             resDigits[i] = negative.digits[i];
531             }
532         } else if (iPos < iNeg) {
533             i = iPos;
534             resDigits[i] = -positive.digits[i];
535             limit = Math.min(positive.numberLength, iNeg);
536             for (i++; i < limit; i++ ) {
537                 resDigits[i] = ~positive.digits[i];
538             }
539             if (i != positive.numberLength) {
540                 resDigits[i] = ~(-negative.digits[i] | positive.digits[i]);
541             } else{
542                   for (; i<iNeg; i++) {
543                       resDigits[i] = -1;
544                   }
545                   // resDigits[i] = ~(-negative.digits[i] | 0);
546                   resDigits[i] = negative.digits[i] - 1;
547             }
548             i++;
549         } else {// iNeg == iPos
550             // Applying two complement to negative and to result
551             i = iPos;
552             resDigits[i] = -(-negative.digits[i] | positive.digits[i]);
553             i++;
554         }
555         limit = Math.min(negative.numberLength, positive.numberLength);
556         for (; i < limit; i++) {
557             // Applying two complement to negative and to result
558             // resDigits[i] = ~(~negative.digits[i] | positive.digits[i] );
559             resDigits[i] = negative.digits[i] & ~positive.digits[i];
560         }
561         for ( ; i < negative.numberLength; i++) {
562             resDigits[i] = negative.digits[i];
563         }
564 
565         return new BigInteger(-1, resLength, resDigits);
566     }
567 
568     /** @see BigInteger#xor(BigInteger) */
xor(BigInteger val, BigInteger that)569     static BigInteger xor(BigInteger val, BigInteger that) {
570         if (that.sign == 0) {
571             return val;
572         }
573         if (val.sign == 0) {
574             return that;
575         }
576         if (that.equals(BigInteger.MINUS_ONE)) {
577             return val.not();
578         }
579         if (val.equals(BigInteger.MINUS_ONE)) {
580             return that.not();
581         }
582 
583         if (val.sign > 0) {
584             if (that.sign > 0) {
585                 if (val.numberLength > that.numberLength) {
586                     return xorPositive(val, that);
587                 } else {
588                     return xorPositive(that, val);
589                 }
590             } else {
591                 return xorDiffSigns(val, that);
592             }
593         } else {
594             if (that.sign > 0) {
595                 return xorDiffSigns(that, val);
596             } else if (that.getFirstNonzeroDigit() > val.getFirstNonzeroDigit()) {
597                 return xorNegative(that, val);
598             } else {
599                 return xorNegative(val, that);
600             }
601         }
602     }
603 
604     /** @return sign = 0, magnitude = longer.magnitude | shorter.magnitude */
xorPositive(BigInteger longer, BigInteger shorter)605     static BigInteger xorPositive(BigInteger longer, BigInteger shorter) {
606         // PRE: longer and shorter are positive;
607         // PRE: longer has at least as many digits as shorter
608         int resLength = longer.numberLength;
609         int[] resDigits = new int[resLength];
610         int i = Math.min(longer.getFirstNonzeroDigit(), shorter.getFirstNonzeroDigit());
611         for ( ; i < shorter.numberLength; i++) {
612             resDigits[i] = longer.digits[i] ^ shorter.digits[i];
613         }
614         for ( ; i < longer.numberLength; i++ ){
615             resDigits[i] = longer.digits[i];
616         }
617 
618         return new BigInteger(1, resLength, resDigits);
619     }
620 
621     /** @return sign = 0, magnitude = -val.magnitude ^ -that.magnitude */
xorNegative(BigInteger val, BigInteger that)622     static BigInteger xorNegative(BigInteger val, BigInteger that){
623         // PRE: val and that are negative
624         // PRE: val has at least as many trailing zero digits as that
625         int resLength = Math.max(val.numberLength, that.numberLength);
626         int[] resDigits = new int[resLength];
627         int iVal = val.getFirstNonzeroDigit();
628         int iThat = that.getFirstNonzeroDigit();
629         int i = iThat;
630         int limit;
631 
632 
633         if (iVal == iThat) {
634             resDigits[i] = -val.digits[i] ^ -that.digits[i];
635         } else {
636             resDigits[i] = -that.digits[i];
637             limit = Math.min(that.numberLength, iVal);
638             for (i++; i < limit; i++) {
639                 resDigits[i] = ~that.digits[i];
640             }
641             // Remains digits in that?
642             if (i == that.numberLength) {
643                 //Jumping over the remaining zero to the first non one
644                 for ( ;i < iVal; i++) {
645                     //resDigits[i] = 0 ^ -1;
646                     resDigits[i] = -1;
647                 }
648                 //resDigits[i] = -val.digits[i] ^ -1;
649                 resDigits[i] = val.digits[i] - 1;
650             } else {
651                 resDigits[i] = -val.digits[i] ^ ~that.digits[i];
652             }
653         }
654 
655         limit = Math.min(val.numberLength, that.numberLength);
656         //Perform ^ between that al val until that ends
657         for (i++; i < limit; i++) {
658             //resDigits[i] = ~val.digits[i] ^ ~that.digits[i];
659             resDigits[i] = val.digits[i] ^ that.digits[i];
660         }
661         //Perform ^ between val digits and -1 until val ends
662         for ( ; i < val.numberLength; i++) {
663             //resDigits[i] = ~val.digits[i] ^ -1  ;
664             resDigits[i] = val.digits[i] ;
665         }
666         for ( ; i < that.numberLength; i++) {
667             //resDigits[i] = -1 ^ ~that.digits[i] ;
668             resDigits[i] = that.digits[i];
669         }
670 
671         return new BigInteger(1, resLength, resDigits);
672     }
673 
674     /** @return sign = 1, magnitude = -(positive.magnitude ^ -negative.magnitude)*/
xorDiffSigns(BigInteger positive, BigInteger negative)675     static BigInteger xorDiffSigns(BigInteger positive, BigInteger negative){
676         int resLength = Math.max(negative.numberLength, positive.numberLength);
677         int[] resDigits;
678         int iNeg = negative.getFirstNonzeroDigit();
679         int iPos = positive.getFirstNonzeroDigit();
680         int i;
681         int limit;
682 
683         //The first
684         if (iNeg < iPos) {
685             resDigits = new int[resLength];
686             i = iNeg;
687             //resDigits[i] = -(-negative.digits[i]);
688             resDigits[i] = negative.digits[i];
689             limit = Math.min(negative.numberLength, iPos);
690             //Skip the positive digits while they are zeros
691             for (i++; i < limit; i++) {
692                 //resDigits[i] = ~(~negative.digits[i]);
693                 resDigits[i] = negative.digits[i];
694             }
695             //if the negative has no more elements, must fill the
696             //result with the remaining digits of the positive
697             if (i == negative.numberLength) {
698                 for ( ; i < positive.numberLength; i++) {
699                     //resDigits[i] = ~(positive.digits[i] ^ -1) -> ~(~positive.digits[i])
700                     resDigits[i] = positive.digits[i];
701                 }
702             }
703         } else if (iPos < iNeg) {
704             resDigits = new int[resLength];
705             i = iPos;
706             //Applying two complement to the first non-zero digit of the result
707             resDigits[i] = -positive.digits[i];
708             limit = Math.min(positive.numberLength, iNeg);
709             for (i++; i < limit; i++) {
710                 //Continue applying two complement the result
711                 resDigits[i] = ~positive.digits[i];
712             }
713             //When the first non-zero digit of the negative is reached, must apply
714             //two complement (arithmetic negation) to it, and then operate
715             if (i == iNeg) {
716                 resDigits[i] = ~(positive.digits[i] ^ -negative.digits[i]);
717                 i++;
718             } else {
719                 //if the positive has no more elements must fill the remaining digits with
720                 //the negative ones
721                 for ( ; i < iNeg; i++) {
722                     // resDigits[i] = ~(0 ^ 0)
723                     resDigits[i] = -1;
724                 }
725                 for ( ; i < negative.numberLength; i++) {
726                     //resDigits[i] = ~(~negative.digits[i] ^ 0)
727                     resDigits[i] = negative.digits[i];
728                 }
729             }
730                 } else {
731             //The first non-zero digit of the positive and negative are the same
732             i = iNeg;
733             int digit = positive.digits[i] ^ -negative.digits[i];
734             if (digit == 0) {
735                 limit = Math.min(positive.numberLength, negative.numberLength);
736                 for (i++; i < limit && (digit = positive.digits[i] ^ ~negative.digits[i]) == 0; i++)
737                     ;
738                 if (digit == 0) {
739                     // shorter has only the remaining virtual sign bits
740                     for ( ; i < positive.numberLength && (digit = ~positive.digits[i]) == 0; i++)
741                         ;
742                     for ( ; i < negative.numberLength && (digit = ~negative.digits[i]) == 0; i++)
743                         ;
744                     if (digit == 0) {
745                         resLength = resLength + 1;
746                         resDigits = new int[resLength];
747                         resDigits[resLength - 1] = 1;
748 
749                         return new BigInteger(-1, resLength, resDigits);
750                 }
751             }
752         }
753             resDigits = new int[resLength];
754             resDigits[i] = -digit;
755             i++;
756         }
757 
758         limit = Math.min(negative.numberLength, positive.numberLength);
759         for ( ; i < limit; i++) {
760             resDigits[i] = ~(~negative.digits[i] ^ positive.digits[i]);
761         }
762         for ( ; i < positive.numberLength; i++) {
763             // resDigits[i] = ~(positive.digits[i] ^ -1)
764             resDigits[i] = positive.digits[i];
765         }
766         for ( ; i < negative.numberLength; i++) {
767             // resDigits[i] = ~(0 ^ ~negative.digits[i])
768             resDigits[i] = negative.digits[i];
769         }
770 
771         return new BigInteger(-1, resLength, resDigits);
772     }
773 }
774