001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: */
017:
018: package java.math;
019:
020: /**
021: * The library implements some logical operations over {@code BigInteger}. The
022: * operations provided are listed below.
023: * <ul type="circle">
024: * <li>not</li>
025: * <li>and</li>
026: * <li>andNot</li>
027: * <li>or</li>
028: * <li>xor</li>
029: * </ul>
030: * @author Intel Middleware Product Division
031: * @author Instituto Tecnologico de Cordoba
032: */
033: class Logical {
034:
035: /** Just to denote that this class can't be instantiated. */
036:
037: private Logical() {
038: }
039:
040: /** @see BigInteger#not() */
041: static BigInteger not(BigInteger val) {
042: if (val.sign == 0) {
043: return BigInteger.MINUS_ONE;
044: }
045: if (val.equals(BigInteger.MINUS_ONE)) {
046: return BigInteger.ZERO;
047: }
048: int resDigits[] = new int[val.numberLength + 1];
049: int i;
050:
051: if (val.sign > 0) {
052: // ~val = -val + 1
053: if (val.digits[val.numberLength - 1] != -1) {
054: for (i = 0; val.digits[i] == -1; i++) {
055: ;
056: }
057: } else {
058: for (i = 0; (i < val.numberLength)
059: && (val.digits[i] == -1); i++) {
060: ;
061: }
062: if (i == val.numberLength) {
063: resDigits[i] = 1;
064: return new BigInteger(-val.sign, i + 1, resDigits);
065: }
066: }
067: // Here a carry 1 was generated
068: } else {// (val.sign < 0)
069: // ~val = -val - 1
070: for (i = 0; val.digits[i] == 0; i++) {
071: resDigits[i] = -1;
072: }
073: // Here a borrow -1 was generated
074: }
075: // Now, the carry/borrow can be absorbed
076: resDigits[i] = val.digits[i] + val.sign;
077: // Copying the remaining unchanged digit
078: for (i++; i < val.numberLength; i++) {
079: resDigits[i] = val.digits[i];
080: }
081: return new BigInteger(-val.sign, i, resDigits);
082: }
083:
084: /** @see BigInteger#and(BigInteger) */
085: static BigInteger and(BigInteger val, BigInteger that) {
086: if (that.sign == 0 || val.sign == 0) {
087: return BigInteger.ZERO;
088: }
089: if (that.equals(BigInteger.MINUS_ONE)) {
090: return val;
091: }
092: if (val.equals(BigInteger.MINUS_ONE)) {
093: return that;
094: }
095:
096: if (val.sign > 0) {
097: if (that.sign > 0) {
098: return andPositive(val, that);
099: } else {
100: return andDiffSigns(val, that);
101: }
102: } else {
103: if (that.sign > 0) {
104: return andDiffSigns(that, val);
105: } else if (val.numberLength > that.numberLength) {
106: return andNegative(val, that);
107: } else {
108: return andNegative(that, val);
109: }
110: }
111: }
112:
113: /** @return sign = 1, magnitude = val.magnitude & that.magnitude*/
114: static BigInteger andPositive(BigInteger val, BigInteger that) {
115: // PRE: both arguments are positive
116: int resLength = Math.min(val.numberLength, that.numberLength);
117: int i = Math.max(val.getFirstNonzeroDigit(), that
118: .getFirstNonzeroDigit());
119:
120: if (i >= resLength) {
121: return BigInteger.ZERO;
122: }
123:
124: int resDigits[] = new int[resLength];
125: for (; i < resLength; i++) {
126: resDigits[i] = val.digits[i] & that.digits[i];
127: }
128:
129: BigInteger result = new BigInteger(1, resLength, resDigits);
130: result.cutOffLeadingZeroes();
131: return result;
132: }
133:
134: /** @return sign = positive.magnitude & magnitude = -negative.magnitude */
135: static BigInteger andDiffSigns(BigInteger positive,
136: BigInteger negative) {
137: // PRE: positive is positive and negative is negative
138: int iPos = positive.getFirstNonzeroDigit();
139: int iNeg = negative.getFirstNonzeroDigit();
140:
141: // Look if the trailing zeros of the negative will "blank" all
142: // the positive digits
143: if (iNeg >= positive.numberLength) {
144: return BigInteger.ZERO;
145: }
146: int resLength = positive.numberLength;
147: int resDigits[] = new int[resLength];
148:
149: // Must start from max(iPos, iNeg)
150: int i = Math.max(iPos, iNeg);
151: if (i == iNeg) {
152: resDigits[i] = -negative.digits[i] & positive.digits[i];
153: i++;
154: }
155: int limit = Math.min(negative.numberLength,
156: positive.numberLength);
157: for (; i < limit; i++) {
158: resDigits[i] = ~negative.digits[i] & positive.digits[i];
159: }
160: // if the negative was shorter must copy the remaining digits
161: // from positive
162: if (i >= negative.numberLength) {
163: for (; i < positive.numberLength; i++) {
164: resDigits[i] = positive.digits[i];
165: }
166: } // else positive ended and must "copy" virtual 0's, do nothing then
167:
168: BigInteger result = new BigInteger(1, resLength, resDigits);
169: result.cutOffLeadingZeroes();
170: return result;
171: }
172:
173: /** @return sign = -1, magnitude = -(-longer.magnitude & -shorter.magnitude)*/
174: static BigInteger andNegative(BigInteger longer, BigInteger shorter) {
175: // PRE: longer and shorter are negative
176: // PRE: longer has at least as many digits as shorter
177: int iLonger = longer.getFirstNonzeroDigit();
178: int iShorter = shorter.getFirstNonzeroDigit();
179:
180: // Does shorter matter?
181: if (iLonger >= shorter.numberLength) {
182: return longer;
183: }
184:
185: int resLength;
186: int resDigits[];
187: int i = Math.max(iShorter, iLonger);
188: int digit;
189: if (iShorter > iLonger) {
190: digit = -shorter.digits[i] & ~longer.digits[i];
191: } else if (iShorter < iLonger) {
192: digit = ~shorter.digits[i] & -longer.digits[i];
193: } else {
194: digit = -shorter.digits[i] & -longer.digits[i];
195: }
196: if (digit == 0) {
197: for (i++; i < shorter.numberLength
198: && (digit = ~(longer.digits[i] | shorter.digits[i])) == 0; i++)
199: ; // digit = ~longer.digits[i] & ~shorter.digits[i]
200: if (digit == 0) {
201: // shorter has only the remaining virtual sign bits
202: for (; i < longer.numberLength
203: && (digit = ~longer.digits[i]) == 0; i++)
204: ;
205: if (digit == 0) {
206: resLength = longer.numberLength + 1;
207: resDigits = new int[resLength];
208: resDigits[resLength - 1] = 1;
209:
210: BigInteger result = new BigInteger(-1, resLength,
211: resDigits);
212: return result;
213: }
214: }
215: }
216: resLength = longer.numberLength;
217: resDigits = new int[resLength];
218: resDigits[i] = -digit;
219: for (i++; i < shorter.numberLength; i++) {
220: // resDigits[i] = ~(~longer.digits[i] & ~shorter.digits[i];)
221: resDigits[i] = longer.digits[i] | shorter.digits[i];
222: }
223: // shorter has only the remaining virtual sign bits
224: for (; i < longer.numberLength; i++) {
225: resDigits[i] = longer.digits[i];
226: }
227:
228: BigInteger result = new BigInteger(-1, resLength, resDigits);
229: return result;
230: }
231:
232: /** @see BigInteger#andNot(BigInteger) */
233: static BigInteger andNot(BigInteger val, BigInteger that) {
234: if (that.sign == 0) {
235: return val;
236: }
237: if (val.sign == 0) {
238: return BigInteger.ZERO;
239: }
240: if (val.equals(BigInteger.MINUS_ONE)) {
241: return that.not();
242: }
243: if (that.equals(BigInteger.MINUS_ONE)) {
244: return BigInteger.ZERO;
245: }
246:
247: //if val == that, return 0
248:
249: if (val.sign > 0) {
250: if (that.sign > 0) {
251: return andNotPositive(val, that);
252: } else {
253: return andNotPositiveNegative(val, that);
254: }
255: } else {
256: if (that.sign > 0) {
257: return andNotNegativePositive(val, that);
258: } else {
259: return andNotNegative(val, that);
260: }
261: }
262: }
263:
264: /** @return sign = 1, magnitude = val.magnitude & ~that.magnitude*/
265: static BigInteger andNotPositive(BigInteger val, BigInteger that) {
266: // PRE: both arguments are positive
267: int resDigits[] = new int[val.numberLength];
268:
269: int limit = Math.min(val.numberLength, that.numberLength);
270: int i;
271: for (i = val.getFirstNonzeroDigit(); i < limit; i++) {
272: resDigits[i] = val.digits[i] & ~that.digits[i];
273: }
274: for (; i < val.numberLength; i++) {
275: resDigits[i] = val.digits[i];
276: }
277:
278: BigInteger result = new BigInteger(1, val.numberLength,
279: resDigits);
280: result.cutOffLeadingZeroes();
281: return result;
282: }
283:
284: /** @return sign = 1, magnitude = positive.magnitude & ~(-negative.magnitude)*/
285: static BigInteger andNotPositiveNegative(BigInteger positive,
286: BigInteger negative) {
287: // PRE: positive > 0 && negative < 0
288: int iNeg = negative.getFirstNonzeroDigit();
289: int iPos = positive.getFirstNonzeroDigit();
290:
291: if (iNeg >= positive.numberLength) {
292: return positive;
293: }
294:
295: int resLength = Math.min(positive.numberLength,
296: negative.numberLength);
297: int resDigits[] = new int[resLength];
298:
299: // Always start from first non zero of positive
300: int i = iPos;
301: for (; i < iNeg; i++) {
302: // resDigits[i] = positive.digits[i] & -1 (~0)
303: resDigits[i] = positive.digits[i];
304: }
305: if (i == iNeg) {
306: resDigits[i] = positive.digits[i]
307: & (negative.digits[i] - 1);
308: i++;
309: }
310: for (; i < resLength; i++) {
311: // resDigits[i] = positive.digits[i] & ~(~negative.digits[i]);
312: resDigits[i] = positive.digits[i] & negative.digits[i];
313: }
314:
315: BigInteger result = new BigInteger(1, resLength, resDigits);
316: result.cutOffLeadingZeroes();
317: return result;
318: }
319:
320: /** @return sign = -1, magnitude = -(-negative.magnitude & ~positive.magnitude)*/
321: static BigInteger andNotNegativePositive(BigInteger negative,
322: BigInteger positive) {
323: // PRE: negative < 0 && positive > 0
324: int resLength;
325: int resDigits[];
326: int limit;
327: int digit;
328:
329: int iNeg = negative.getFirstNonzeroDigit();
330: int iPos = positive.getFirstNonzeroDigit();
331:
332: if (iNeg >= positive.numberLength) {
333: return negative;
334: }
335:
336: resLength = Math.max(negative.numberLength,
337: positive.numberLength);
338: int i = iNeg;
339: if (iPos > iNeg) {
340: resDigits = new int[resLength];
341: limit = Math.min(negative.numberLength, iPos);
342: for (; i < limit; i++) {
343: // 1st case: resDigits [i] = -(-negative.digits[i] & (~0))
344: // otherwise: resDigits[i] = ~(~negative.digits[i] & ~0) ;
345: resDigits[i] = negative.digits[i];
346: }
347: if (i == negative.numberLength) {
348: for (i = iPos; i < positive.numberLength; i++) {
349: // resDigits[i] = ~(~positive.digits[i] & -1);
350: resDigits[i] = positive.digits[i];
351: }
352: }
353: } else {
354: digit = -negative.digits[i] & ~positive.digits[i];
355: if (digit == 0) {
356: limit = Math.min(positive.numberLength,
357: negative.numberLength);
358: for (i++; i < limit
359: && (digit = ~(negative.digits[i] | positive.digits[i])) == 0; i++)
360: ; // digit = ~negative.digits[i] & ~positive.digits[i]
361: if (digit == 0) {
362: // the shorter has only the remaining virtual sign bits
363: for (; i < positive.numberLength
364: && (digit = ~positive.digits[i]) == 0; i++)
365: ; // digit = -1 & ~positive.digits[i]
366: for (; i < negative.numberLength
367: && (digit = ~negative.digits[i]) == 0; i++)
368: ; // digit = ~negative.digits[i] & ~0
369: if (digit == 0) {
370: resLength++;
371: resDigits = new int[resLength];
372: resDigits[resLength - 1] = 1;
373:
374: BigInteger result = new BigInteger(-1,
375: resLength, resDigits);
376: return result;
377: }
378: }
379: }
380: resDigits = new int[resLength];
381: resDigits[i] = -digit;
382: i++;
383: }
384:
385: limit = Math.min(positive.numberLength, negative.numberLength);
386: for (; i < limit; i++) {
387: //resDigits[i] = ~(~negative.digits[i] & ~positive.digits[i]);
388: resDigits[i] = negative.digits[i] | positive.digits[i];
389: }
390: // Actually one of the next two cycles will be executed
391: for (; i < negative.numberLength; i++) {
392: resDigits[i] = negative.digits[i];
393: }
394: for (; i < positive.numberLength; i++) {
395: resDigits[i] = positive.digits[i];
396: }
397:
398: BigInteger result = new BigInteger(-1, resLength, resDigits);
399: return result;
400: }
401:
402: /** @return sign = 1, magnitude = -val.magnitude & ~(-that.magnitude)*/
403: static BigInteger andNotNegative(BigInteger val, BigInteger that) {
404: // PRE: val < 0 && that < 0
405: int iVal = val.getFirstNonzeroDigit();
406: int iThat = that.getFirstNonzeroDigit();
407:
408: if (iVal >= that.numberLength) {
409: return BigInteger.ZERO;
410: }
411:
412: int resLength = that.numberLength;
413: int resDigits[] = new int[resLength];
414: int limit;
415: int i = iVal;
416: if (iVal < iThat) {
417: // resDigits[i] = -val.digits[i] & -1;
418: resDigits[i] = -val.digits[i];
419: limit = Math.min(val.numberLength, iThat);
420: for (i++; i < limit; i++) {
421: // resDigits[i] = ~val.digits[i] & -1;
422: resDigits[i] = ~val.digits[i];
423: }
424: if (i == val.numberLength) {
425: for (; i < iThat; i++) {
426: // resDigits[i] = -1 & -1;
427: resDigits[i] = -1;
428: }
429: // resDigits[i] = -1 & ~-that.digits[i];
430: resDigits[i] = that.digits[i] - 1;
431: } else {
432: // resDigits[i] = ~val.digits[i] & ~-that.digits[i];
433: resDigits[i] = ~val.digits[i] & (that.digits[i] - 1);
434: }
435: } else if (iThat < iVal) {
436: // resDigits[i] = -val.digits[i] & ~~that.digits[i];
437: resDigits[i] = -val.digits[i] & that.digits[i];
438: } else {
439: // resDigits[i] = -val.digits[i] & ~-that.digits[i];
440: resDigits[i] = -val.digits[i] & (that.digits[i] - 1);
441: }
442:
443: limit = Math.min(val.numberLength, that.numberLength);
444: for (i++; i < limit; i++) {
445: // resDigits[i] = ~val.digits[i] & ~~that.digits[i];
446: resDigits[i] = ~val.digits[i] & that.digits[i];
447: }
448: for (; i < that.numberLength; i++) {
449: // resDigits[i] = -1 & ~~that.digits[i];
450: resDigits[i] = that.digits[i];
451: }
452:
453: BigInteger result = new BigInteger(1, resLength, resDigits);
454: result.cutOffLeadingZeroes();
455: return result;
456: }
457:
458: /** @see BigInteger#or(BigInteger) */
459: static BigInteger or(BigInteger val, BigInteger that) {
460: if (that.equals(BigInteger.MINUS_ONE)
461: || val.equals(BigInteger.MINUS_ONE)) {
462: return BigInteger.MINUS_ONE;
463: }
464: if (that.sign == 0) {
465: return val;
466: }
467: if (val.sign == 0) {
468: return that;
469: }
470:
471: if (val.sign > 0) {
472: if (that.sign > 0) {
473: if (val.numberLength > that.numberLength) {
474: return orPositive(val, that);
475: } else {
476: return orPositive(that, val);
477: }
478: } else {
479: return orDiffSigns(val, that);
480: }
481: } else {
482: if (that.sign > 0) {
483: return orDiffSigns(that, val);
484: } else if (that.getFirstNonzeroDigit() > val
485: .getFirstNonzeroDigit()) {
486: return orNegative(that, val);
487: } else {
488: return orNegative(val, that);
489: }
490: }
491: }
492:
493: /** @return sign = 1, magnitude = longer.magnitude | shorter.magnitude*/
494: static BigInteger orPositive(BigInteger longer, BigInteger shorter) {
495: // PRE: longer and shorter are positive;
496: // PRE: longer has at least as many digits as shorter
497: int resLength = longer.numberLength;
498: int resDigits[] = new int[resLength];
499:
500: int i = Math.min(longer.getFirstNonzeroDigit(), shorter
501: .getFirstNonzeroDigit());
502: for (i = 0; i < shorter.numberLength; i++) {
503: resDigits[i] = longer.digits[i] | shorter.digits[i];
504: }
505: for (; i < resLength; i++) {
506: resDigits[i] = longer.digits[i];
507: }
508:
509: BigInteger result = new BigInteger(1, resLength, resDigits);
510: return result;
511: }
512:
513: /** @return sign = -1, magnitude = -(-val.magnitude | -that.magnitude) */
514: static BigInteger orNegative(BigInteger val, BigInteger that) {
515: // PRE: val and that are negative;
516: // PRE: val has at least as many trailing zeros digits as that
517: int iThat = that.getFirstNonzeroDigit();
518: int iVal = val.getFirstNonzeroDigit();
519: int i;
520:
521: if (iVal >= that.numberLength) {
522: return that;
523: } else if (iThat >= val.numberLength) {
524: return val;
525: }
526:
527: int resLength = Math.min(val.numberLength, that.numberLength);
528: int resDigits[] = new int[resLength];
529:
530: //Looking for the first non-zero digit of the result
531: if (iThat == iVal) {
532: resDigits[iVal] = -(-val.digits[iVal] | -that.digits[iVal]);
533: i = iVal;
534: } else {
535: for (i = iThat; i < iVal; i++) {
536: resDigits[i] = that.digits[i];
537: }
538: resDigits[i] = that.digits[i] & (val.digits[i] - 1);
539: }
540:
541: for (i++; i < resLength; i++) {
542: resDigits[i] = val.digits[i] & that.digits[i];
543: }
544:
545: BigInteger result = new BigInteger(-1, resLength, resDigits);
546: result.cutOffLeadingZeroes();
547: return result;
548: }
549:
550: /** @return sign = -1, magnitude = -(positive.magnitude | -negative.magnitude) */
551: static BigInteger orDiffSigns(BigInteger positive,
552: BigInteger negative) {
553: // Jumping over the least significant zero bits
554: int iNeg = negative.getFirstNonzeroDigit();
555: int iPos = positive.getFirstNonzeroDigit();
556: int i;
557: int limit;
558:
559: // Look if the trailing zeros of the positive will "copy" all
560: // the negative digits
561: if (iPos >= negative.numberLength) {
562: return negative;
563: }
564: int resLength = negative.numberLength;
565: int resDigits[] = new int[resLength];
566:
567: if (iNeg < iPos) {
568: // We know for sure that this will
569: // be the first non zero digit in the result
570: for (i = iNeg; i < iPos; i++) {
571: resDigits[i] = negative.digits[i];
572: }
573: } else if (iPos < iNeg) {
574: i = iPos;
575: resDigits[i] = -positive.digits[i];
576: limit = Math.min(positive.numberLength, iNeg);
577: for (i++; i < limit; i++) {
578: resDigits[i] = ~positive.digits[i];
579: }
580: if (i != positive.numberLength) {
581: resDigits[i] = ~(-negative.digits[i] | positive.digits[i]);
582: } else {
583: for (; i < iNeg; i++) {
584: resDigits[i] = -1;
585: }
586: // resDigits[i] = ~(-negative.digits[i] | 0);
587: resDigits[i] = negative.digits[i] - 1;
588: }
589: i++;
590: } else {// iNeg == iPos
591: // Applying two complement to negative and to result
592: i = iPos;
593: resDigits[i] = -(-negative.digits[i] | positive.digits[i]);
594: i++;
595: }
596: limit = Math.min(negative.numberLength, positive.numberLength);
597: for (; i < limit; i++) {
598: // Applying two complement to negative and to result
599: // resDigits[i] = ~(~negative.digits[i] | positive.digits[i] );
600: resDigits[i] = negative.digits[i] & ~positive.digits[i];
601: }
602: for (; i < negative.numberLength; i++) {
603: resDigits[i] = negative.digits[i];
604: }
605:
606: BigInteger result = new BigInteger(-1, resLength, resDigits);
607: result.cutOffLeadingZeroes();
608: return result;
609: }
610:
611: /** @see BigInteger#xor(BigInteger) */
612: static BigInteger xor(BigInteger val, BigInteger that) {
613: if (that.sign == 0) {
614: return val;
615: }
616: if (val.sign == 0) {
617: return that;
618: }
619: if (that.equals(BigInteger.MINUS_ONE)) {
620: return val.not();
621: }
622: if (val.equals(BigInteger.MINUS_ONE)) {
623: return that.not();
624: }
625:
626: if (val.sign > 0) {
627: if (that.sign > 0) {
628: if (val.numberLength > that.numberLength) {
629: return xorPositive(val, that);
630: } else {
631: return xorPositive(that, val);
632: }
633: } else {
634: return xorDiffSigns(val, that);
635: }
636: } else {
637: if (that.sign > 0) {
638: return xorDiffSigns(that, val);
639: } else if (that.getFirstNonzeroDigit() > val
640: .getFirstNonzeroDigit()) {
641: return xorNegative(that, val);
642: } else {
643: return xorNegative(val, that);
644: }
645: }
646: }
647:
648: /** @return sign = 0, magnitude = longer.magnitude | shorter.magnitude */
649: static BigInteger xorPositive(BigInteger longer, BigInteger shorter) {
650: // PRE: longer and shorter are positive;
651: // PRE: longer has at least as many digits as shorter
652: int resLength = longer.numberLength;
653: int resDigits[] = new int[resLength];
654: int i = Math.min(longer.getFirstNonzeroDigit(), shorter
655: .getFirstNonzeroDigit());
656: for (; i < shorter.numberLength; i++) {
657: resDigits[i] = longer.digits[i] ^ shorter.digits[i];
658: }
659: for (; i < longer.numberLength; i++) {
660: resDigits[i] = longer.digits[i];
661: }
662:
663: BigInteger result = new BigInteger(1, resLength, resDigits);
664: result.cutOffLeadingZeroes();
665: return result;
666: }
667:
668: /** @return sign = 0, magnitude = -val.magnitude ^ -that.magnitude */
669: static BigInteger xorNegative(BigInteger val, BigInteger that) {
670: // PRE: val and that are negative
671: // PRE: val has at least as many trailing zero digits as that
672: int resLength = Math.max(val.numberLength, that.numberLength);
673: int resDigits[] = new int[resLength];
674: int iVal = val.getFirstNonzeroDigit();
675: int iThat = that.getFirstNonzeroDigit();
676: int i = iThat;
677: int limit;
678:
679: if (iVal == iThat) {
680: resDigits[i] = -val.digits[i] ^ -that.digits[i];
681: } else {
682: resDigits[i] = -that.digits[i];
683: limit = Math.min(that.numberLength, iVal);
684: for (i++; i < limit; i++) {
685: resDigits[i] = ~that.digits[i];
686: }
687: // Remains digits in that?
688: if (i == that.numberLength) {
689: //Jumping over the remaining zero to the first non one
690: for (; i < iVal; i++) {
691: //resDigits[i] = 0 ^ -1;
692: resDigits[i] = -1;
693: }
694: //resDigits[i] = -val.digits[i] ^ -1;
695: resDigits[i] = val.digits[i] - 1;
696: } else {
697: resDigits[i] = -val.digits[i] ^ ~that.digits[i];
698: }
699: }
700:
701: limit = Math.min(val.numberLength, that.numberLength);
702: //Perform ^ between that al val until that ends
703: for (i++; i < limit; i++) {
704: //resDigits[i] = ~val.digits[i] ^ ~that.digits[i];
705: resDigits[i] = val.digits[i] ^ that.digits[i];
706: }
707: //Perform ^ between val digits and -1 until val ends
708: for (; i < val.numberLength; i++) {
709: //resDigits[i] = ~val.digits[i] ^ -1 ;
710: resDigits[i] = val.digits[i];
711: }
712: for (; i < that.numberLength; i++) {
713: //resDigits[i] = -1 ^ ~that.digits[i] ;
714: resDigits[i] = that.digits[i];
715: }
716:
717: BigInteger result = new BigInteger(1, resLength, resDigits);
718: result.cutOffLeadingZeroes();
719: return result;
720: }
721:
722: /** @return sign = 1, magnitude = -(positive.magnitude ^ -negative.magnitude)*/
723: static BigInteger xorDiffSigns(BigInteger positive,
724: BigInteger negative) {
725: int resLength = Math.max(negative.numberLength,
726: positive.numberLength);
727: int resDigits[];
728: int iNeg = negative.getFirstNonzeroDigit();
729: int iPos = positive.getFirstNonzeroDigit();
730: int i;
731: int limit;
732:
733: //The first
734: if (iNeg < iPos) {
735: resDigits = new int[resLength];
736: i = iNeg;
737: //resDigits[i] = -(-negative.digits[i]);
738: resDigits[i] = negative.digits[i];
739: limit = Math.min(negative.numberLength, iPos);
740: //Skip the positive digits while they are zeros
741: for (i++; i < limit; i++) {
742: //resDigits[i] = ~(~negative.digits[i]);
743: resDigits[i] = negative.digits[i];
744: }
745: //if the negative has no more elements, must fill the
746: //result with the remaining digits of the positive
747: if (i == negative.numberLength) {
748: for (; i < positive.numberLength; i++) {
749: //resDigits[i] = ~(positive.digits[i] ^ -1) -> ~(~positive.digits[i])
750: resDigits[i] = positive.digits[i];
751: }
752: }
753: } else if (iPos < iNeg) {
754: resDigits = new int[resLength];
755: i = iPos;
756: //Applying two complement to the first non-zero digit of the result
757: resDigits[i] = -positive.digits[i];
758: limit = Math.min(positive.numberLength, iNeg);
759: for (i++; i < limit; i++) {
760: //Continue applying two complement the result
761: resDigits[i] = ~positive.digits[i];
762: }
763: //When the first non-zero digit of the negative is reached, must apply
764: //two complement (arithmetic negation) to it, and then operate
765: if (i == iNeg) {
766: resDigits[i] = ~(positive.digits[i] ^ -negative.digits[i]);
767: i++;
768: } else {
769: //if the positive has no more elements must fill the remaining digits with
770: //the negative ones
771: for (; i < iNeg; i++) {
772: // resDigits[i] = ~(0 ^ 0)
773: resDigits[i] = -1;
774: }
775: for (; i < negative.numberLength; i++) {
776: //resDigits[i] = ~(~negative.digits[i] ^ 0)
777: resDigits[i] = negative.digits[i];
778: }
779: }
780: } else {
781: int digit;
782: //The first non-zero digit of the positive and negative are the same
783: i = iNeg;
784: digit = positive.digits[i] ^ -negative.digits[i];
785: if (digit == 0) {
786: limit = Math.min(positive.numberLength,
787: negative.numberLength);
788: for (i++; i < limit
789: && (digit = positive.digits[i]
790: ^ ~negative.digits[i]) == 0; i++)
791: ;
792: if (digit == 0) {
793: // shorter has only the remaining virtual sign bits
794: for (; i < positive.numberLength
795: && (digit = ~positive.digits[i]) == 0; i++)
796: ;
797: for (; i < negative.numberLength
798: && (digit = ~negative.digits[i]) == 0; i++)
799: ;
800: if (digit == 0) {
801: resLength = resLength + 1;
802: resDigits = new int[resLength];
803: resDigits[resLength - 1] = 1;
804:
805: BigInteger result = new BigInteger(-1,
806: resLength, resDigits);
807: return result;
808: }
809: }
810: }
811: resDigits = new int[resLength];
812: resDigits[i] = -digit;
813: i++;
814: }
815:
816: limit = Math.min(negative.numberLength, positive.numberLength);
817: for (; i < limit; i++) {
818: resDigits[i] = ~(~negative.digits[i] ^ positive.digits[i]);
819: }
820: for (; i < positive.numberLength; i++) {
821: // resDigits[i] = ~(positive.digits[i] ^ -1)
822: resDigits[i] = positive.digits[i];
823: }
824: for (; i < negative.numberLength; i++) {
825: // resDigits[i] = ~(0 ^ ~negative.digits[i])
826: resDigits[i] = negative.digits[i];
827: }
828:
829: BigInteger result = new BigInteger(-1, resLength, resDigits);
830: result.cutOffLeadingZeroes();
831: return result;
832: }
833: }
|