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 35 private Logical() {} 36 37 38 /** @see BigInteger#not() */ 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) */ 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*/ 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 */ 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)*/ 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) */ 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*/ 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)*/ 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)*/ 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)*/ 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) */ 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*/ 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) */ 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) */ 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) */ 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 */ 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 */ 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)*/ 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
