java/math/Logical.java

/*
 *  Licensed to the Apache Software Foundation (ASF) under one or more
 *  contributor license agreements.  See the NOTICE file distributed with
 *  this work for additional information regarding copyright ownership.
 *  The ASF licenses this file to You under the Apache License, Version 2.0
 *  (the "License"); you may not use this file except in compliance with
 *  the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */

package java.math;

/**
 * The library implements some logical operations over {@code BigInteger}. The
 * operations provided are listed below.
 * <ul type="circle">
 * <li>not</li>
 * <li>and</li>
 * <li>andNot</li>
 * <li>or</li>
 * <li>xor</li>
 * </ul>
 */
class Logical {

    /** Just to denote that this class can't be instantiated. */

    private Logical() {}


    /** @see BigInteger#not() */
    static BigInteger not(BigInteger val) {
        if (val.sign == 0) {
            return BigInteger.MINUS_ONE;
        }
        if (val.equals(BigInteger.MINUS_ONE)) {
            return BigInteger.ZERO;
        }
        int[] resDigits = new int[val.numberLength + 1];
        int i;

        if (val.sign > 0) {
            // ~val = -val + 1
            if (val.digits[val.numberLength - 1] != -1) {
                for (i = 0; val.digits[i] == -1; i++) {
                    ;
                }
            } else {
                for (i = 0; (i < val.numberLength) && (val.digits[i] == -1); i++) {
                    ;
                }
                if (i == val.numberLength) {
                    resDigits[i] = 1;
                    return new BigInteger(-val.sign, i + 1, resDigits);
                }
            }
            // Here a carry 1 was generated
        } else {// (val.sign < 0)
            // ~val = -val - 1
            for (i = 0; val.digits[i] == 0; i++) {
                resDigits[i] = -1;
            }
            // Here a borrow -1 was generated
        }
        // Now, the carry/borrow can be absorbed
        resDigits[i] = val.digits[i] + val.sign;
        // Copying the remaining unchanged digit
        for (i++; i < val.numberLength; i++) {
            resDigits[i] = val.digits[i];
        }
        return new BigInteger(-val.sign, i, resDigits);
    }

    /** @see BigInteger#and(BigInteger) */
    static BigInteger and(BigInteger val, BigInteger that) {
        if (that.sign == 0 || val.sign == 0) {
            return BigInteger.ZERO;
        }
        if (that.equals(BigInteger.MINUS_ONE)){
            return val;
        }
        if (val.equals(BigInteger.MINUS_ONE)) {
            return that;
        }

        if (val.sign > 0) {
            if (that.sign > 0) {
                return andPositive(val, that);
            } else {
                return andDiffSigns(val, that);
            }
        } else {
            if (that.sign > 0) {
                return andDiffSigns(that, val);
            } else if (val.numberLength > that.numberLength) {
                return andNegative(val, that);
            } else {
                return andNegative(that, val);
            }
        }
    }

    /** @return sign = 1, magnitude = val.magnitude & that.magnitude*/
    static BigInteger andPositive(BigInteger val, BigInteger that) {
        // PRE: both arguments are positive
        int resLength = Math.min(val.numberLength, that.numberLength);
        int i = Math.max(val.getFirstNonzeroDigit(), that.getFirstNonzeroDigit());

        if (i >= resLength) {
            return BigInteger.ZERO;
        }

        int[] resDigits = new int[resLength];
        for ( ; i < resLength; i++) {
            resDigits[i] = val.digits[i] & that.digits[i];
        }

        return new BigInteger(1, resLength, resDigits);
    }

    /** @return sign = positive.magnitude & magnitude = -negative.magnitude */
    static BigInteger andDiffSigns(BigInteger positive, BigInteger negative) {
        // PRE: positive is positive and negative is negative
        int iPos = positive.getFirstNonzeroDigit();
        int iNeg = negative.getFirstNonzeroDigit();

        // Look if the trailing zeros of the negative will "blank" all
        // the positive digits
        if (iNeg >= positive.numberLength) {
            return BigInteger.ZERO;
        }
        int resLength = positive.numberLength;
        int[] resDigits = new int[resLength];

        // Must start from max(iPos, iNeg)
        int i = Math.max(iPos, iNeg);
        if (i == iNeg) {
            resDigits[i] = -negative.digits[i] & positive.digits[i];
            i++;
        }
        int limit = Math.min(negative.numberLength, positive.numberLength);
        for ( ; i < limit; i++) {
            resDigits[i] = ~negative.digits[i] & positive.digits[i];
        }
        // if the negative was shorter must copy the remaining digits
        // from positive
        if (i >= negative.numberLength) {
            for ( ; i < positive.numberLength; i++) {
                resDigits[i] = positive.digits[i];
            }
        } // else positive ended and must "copy" virtual 0's, do nothing then

        return new BigInteger(1, resLength, resDigits);
    }

    /** @return sign = -1, magnitude = -(-longer.magnitude & -shorter.magnitude)*/
    static BigInteger andNegative(BigInteger longer, BigInteger shorter) {
        // PRE: longer and shorter are negative
        // PRE: longer has at least as many digits as shorter
        int iLonger = longer.getFirstNonzeroDigit();
        int iShorter = shorter.getFirstNonzeroDigit();

        // Does shorter matter?
        if (iLonger >= shorter.numberLength) {
            return longer;
        }

        int resLength;
        int[] resDigits;
        int i = Math.max(iShorter, iLonger);
        int digit;
        if (iShorter > iLonger) {
            digit = -shorter.digits[i] & ~longer.digits[i];
        } else if (iShorter < iLonger) {
            digit = ~shorter.digits[i] & -longer.digits[i];
        } else {
            digit = -shorter.digits[i] & -longer.digits[i];
        }
        if (digit == 0) {
            for (i++; i < shorter.numberLength && (digit = ~(longer.digits[i] | shorter.digits[i])) == 0; i++)
                ;  // digit = ~longer.digits[i] & ~shorter.digits[i]
            if (digit == 0) {
                // shorter has only the remaining virtual sign bits
                for ( ; i < longer.numberLength && (digit = ~longer.digits[i]) == 0; i++)
                    ;
                if (digit == 0) {
                    resLength = longer.numberLength + 1;
                    resDigits = new int[resLength];
                    resDigits[resLength - 1] = 1;

                    return new BigInteger(-1, resLength, resDigits);
                }
            }
        }
        resLength = longer.numberLength;
                resDigits = new int[resLength];
        resDigits[i] = -digit;
        for (i++; i < shorter.numberLength; i++){
            // resDigits[i] = ~(~longer.digits[i] & ~shorter.digits[i];)
            resDigits[i] = longer.digits[i] | shorter.digits[i];
        }
        // shorter has only the remaining virtual sign bits
        for ( ; i < longer.numberLength; i++){
            resDigits[i] = longer.digits[i];
        }

        return new BigInteger(-1, resLength, resDigits);
    }

    /** @see BigInteger#andNot(BigInteger) */
    static BigInteger andNot(BigInteger val, BigInteger that) {
        if (that.sign == 0 ) {
            return val;
        }
        if (val.sign == 0) {
            return BigInteger.ZERO;
        }
        if (val.equals(BigInteger.MINUS_ONE)) {
            return that.not();
        }
        if (that.equals(BigInteger.MINUS_ONE)){
            return BigInteger.ZERO;
        }

        //if val == that, return 0

       if (val.sign > 0) {
            if (that.sign > 0) {
                return andNotPositive(val, that);
            } else {
                return andNotPositiveNegative(val, that);
                    }
                } else {
            if (that.sign > 0) {
                return andNotNegativePositive(val, that);
            } else  {
                return andNotNegative(val, that);
            }
        }
    }

    /** @return sign = 1, magnitude = val.magnitude & ~that.magnitude*/
    static BigInteger andNotPositive(BigInteger val, BigInteger that) {
        // PRE: both arguments are positive
        int[] resDigits = new int[val.numberLength];

        int limit = Math.min(val.numberLength, that.numberLength);
        int i;
        for (i = val.getFirstNonzeroDigit(); i < limit; i++) {
            resDigits[i] = val.digits[i] & ~that.digits[i];
        }
        for ( ; i < val.numberLength; i++) {
            resDigits[i] = val.digits[i];
        }

        return new BigInteger(1, val.numberLength, resDigits);
    }

    /** @return sign = 1, magnitude = positive.magnitude & ~(-negative.magnitude)*/
    static BigInteger andNotPositiveNegative(BigInteger positive, BigInteger negative) {
        // PRE: positive > 0 && negative < 0
        int iNeg = negative.getFirstNonzeroDigit();
        int iPos = positive.getFirstNonzeroDigit();

        if (iNeg >= positive.numberLength) {
            return positive;
        }

        int resLength = Math.min(positive.numberLength, negative.numberLength);
        int[] resDigits = new int[resLength];

        // Always start from first non zero of positive
        int i = iPos;
        for ( ; i < iNeg; i++) {
            // resDigits[i] = positive.digits[i] & -1 (~0)
            resDigits[i] = positive.digits[i];
        }
        if (i == iNeg) {
            resDigits[i] = positive.digits[i] & (negative.digits[i] - 1);
            i++;
        }
        for ( ; i < resLength; i++) {
            // resDigits[i] = positive.digits[i] & ~(~negative.digits[i]);
            resDigits[i] = positive.digits[i] & negative.digits[i];
        }

        return new BigInteger(1, resLength, resDigits);
    }

    /** @return sign = -1, magnitude = -(-negative.magnitude & ~positive.magnitude)*/
    static BigInteger andNotNegativePositive(BigInteger negative, BigInteger positive) {
        // PRE: negative < 0 && positive > 0
        int resLength;
        int[] resDigits;
        int limit;
        int digit;

        int iNeg = negative.getFirstNonzeroDigit();
        int iPos = positive.getFirstNonzeroDigit();

        if (iNeg >= positive.numberLength) {
            return negative;
        }

        resLength = Math.max(negative.numberLength, positive.numberLength);
        int i = iNeg;
        if (iPos > iNeg) {
            resDigits = new int[resLength];
            limit = Math.min(negative.numberLength, iPos);
            for ( ; i < limit; i++) {
                // 1st case:  resDigits [i] = -(-negative.digits[i] & (~0))
                // otherwise: resDigits[i] = ~(~negative.digits[i] & ~0)  ;
                resDigits[i] = negative.digits[i];
            }
            if (i == negative.numberLength) {
                for (i = iPos; i < positive.numberLength; i++) {
                    // resDigits[i] = ~(~positive.digits[i] & -1);
                    resDigits[i] = positive.digits[i];
                }
            }
        } else {
            digit = -negative.digits[i] & ~positive.digits[i];
            if (digit == 0) {
                limit = Math.min(positive.numberLength, negative.numberLength);
                for (i++; i < limit && (digit = ~(negative.digits[i] | positive.digits[i])) == 0; i++)
                    ; // digit = ~negative.digits[i] & ~positive.digits[i]
                if (digit == 0) {
                    // the shorter has only the remaining virtual sign bits
                    for ( ; i < positive.numberLength && (digit = ~positive.digits[i]) == 0; i++)
                        ; // digit = -1 & ~positive.digits[i]
                    for ( ; i < negative.numberLength && (digit = ~negative.digits[i]) == 0; i++)
                        ; // digit = ~negative.digits[i] & ~0
                    if (digit == 0) {
                        resLength++;
                        resDigits = new int[resLength];
                        resDigits[resLength - 1] = 1;

                        return new BigInteger(-1, resLength, resDigits);
                    }
                }
            }
                        resDigits = new int[resLength];
            resDigits[i] = -digit;
            i++;
                    }

        limit = Math.min(positive.numberLength, negative.numberLength);
        for ( ; i < limit; i++) {
            //resDigits[i] = ~(~negative.digits[i] & ~positive.digits[i]);
            resDigits[i] = negative.digits[i] | positive.digits[i];
        }
        // Actually one of the next two cycles will be executed
        for ( ; i < negative.numberLength; i++) {
            resDigits[i] = negative.digits[i];
                }
        for ( ; i < positive.numberLength; i++) {
            resDigits[i] = positive.digits[i];
        }

        return new BigInteger(-1, resLength, resDigits);
    }

    /** @return sign = 1, magnitude = -val.magnitude & ~(-that.magnitude)*/
    static BigInteger andNotNegative(BigInteger val, BigInteger that) {
        // PRE: val < 0 && that < 0
        int iVal = val.getFirstNonzeroDigit();
        int iThat = that.getFirstNonzeroDigit();

        if (iVal >= that.numberLength) {
            return BigInteger.ZERO;
        }

        int resLength = that.numberLength;
        int[] resDigits = new int[resLength];
        int limit;
        int i = iVal;
        if (iVal < iThat) {
            // resDigits[i] = -val.digits[i] & -1;
            resDigits[i] = -val.digits[i];
            limit = Math.min(val.numberLength, iThat);
            for (i++; i < limit; i++) {
                // resDigits[i] = ~val.digits[i] & -1;
                resDigits[i] = ~val.digits[i];
            }
            if (i == val.numberLength) {
                for ( ; i < iThat; i++) {
                    // resDigits[i] = -1 & -1;
                    resDigits[i] = -1;
                }
                // resDigits[i] = -1 & ~-that.digits[i];
                resDigits[i] = that.digits[i] - 1;
        } else {
                // resDigits[i] = ~val.digits[i] & ~-that.digits[i];
                resDigits[i] = ~val.digits[i] & (that.digits[i] - 1);
            }
        } else if (iThat < iVal ) {
            // resDigits[i] = -val.digits[i] & ~~that.digits[i];
            resDigits[i] = -val.digits[i] & that.digits[i];
        } else {
            // resDigits[i] = -val.digits[i] & ~-that.digits[i];
            resDigits[i] = -val.digits[i] & (that.digits[i] - 1);
            }

        limit = Math.min(val.numberLength, that.numberLength);
        for (i++; i < limit; i++) {
            // resDigits[i] = ~val.digits[i] & ~~that.digits[i];
            resDigits[i] = ~val.digits[i] & that.digits[i];
        }
        for ( ; i < that.numberLength; i++) {
            // resDigits[i] = -1 & ~~that.digits[i];
            resDigits[i] = that.digits[i];
        }

        return new BigInteger(1, resLength, resDigits);
    }

    /** @see BigInteger#or(BigInteger) */
    static BigInteger or(BigInteger val, BigInteger that) {
        if (that.equals(BigInteger.MINUS_ONE) || val.equals(BigInteger.MINUS_ONE)) {
            return BigInteger.MINUS_ONE;
        }
        if (that.sign == 0) {
            return val;
        }
        if (val.sign == 0) {
            return that;
        }

        if (val.sign > 0) {
            if (that.sign > 0) {
                if (val.numberLength > that.numberLength) {
                    return orPositive(val, that);
                } else {
                    return orPositive(that, val);
                }
            } else {
                return orDiffSigns(val, that);
            }
        } else {
            if (that.sign > 0) {
                return orDiffSigns(that, val);
            } else if (that.getFirstNonzeroDigit() > val.getFirstNonzeroDigit()) {
                return orNegative(that, val);
            } else {
                return orNegative(val, that);
            }
        }
    }

    /** @return sign = 1, magnitude = longer.magnitude | shorter.magnitude*/
    static BigInteger orPositive(BigInteger longer, BigInteger shorter) {
        // PRE: longer and shorter are positive;
        // PRE: longer has at least as many digits as shorter
        int resLength = longer.numberLength;
        int[] resDigits = new int[resLength];

        int i;
        for (i = 0; i < shorter.numberLength; i++) {
            resDigits[i] = longer.digits[i] | shorter.digits[i];
        }
        for ( ; i < resLength; i++) {
            resDigits[i] = longer.digits[i];
        }

        return new BigInteger(1, resLength, resDigits);
    }

    /** @return sign = -1, magnitude = -(-val.magnitude | -that.magnitude) */
    static BigInteger orNegative(BigInteger val, BigInteger that){
        // PRE: val and that are negative;
        // PRE: val has at least as many trailing zeros digits as that
        int iThat = that.getFirstNonzeroDigit();
        int iVal = val.getFirstNonzeroDigit();
        int i;

        if (iVal >= that.numberLength) {
            return that;
        }else if (iThat >= val.numberLength) {
            return val;
        }

        int resLength = Math.min(val.numberLength, that.numberLength);
        int[] resDigits = new int[resLength];

        //Looking for the first non-zero digit of the result
        if (iThat == iVal) {
            resDigits[iVal] = -(-val.digits[iVal] | -that.digits[iVal]);
            i = iVal;
        } else {
            for (i = iThat; i < iVal; i++) {
                resDigits[i] = that.digits[i];
            }
            resDigits[i] = that.digits[i] & (val.digits[i] - 1);
        }

        for (i++; i < resLength; i++) {
            resDigits[i] = val.digits[i] & that.digits[i];
        }

        return new BigInteger(-1, resLength, resDigits);
    }

    /** @return sign = -1, magnitude = -(positive.magnitude | -negative.magnitude) */
    static BigInteger orDiffSigns(BigInteger positive, BigInteger negative){
        // Jumping over the least significant zero bits
        int iNeg = negative.getFirstNonzeroDigit();
        int iPos = positive.getFirstNonzeroDigit();
        int i;
        int limit;

        // Look if the trailing zeros of the positive will "copy" all
        // the negative digits
        if (iPos >= negative.numberLength) {
            return negative;
        }
        int resLength = negative.numberLength;
        int[] resDigits = new int[resLength];

        if (iNeg < iPos ) {
            // We know for sure that this will
            // be the first non zero digit in the result
            for (i = iNeg; i < iPos; i++) {
            resDigits[i] = negative.digits[i];
            }
        } else if (iPos < iNeg) {
            i = iPos;
            resDigits[i] = -positive.digits[i];
            limit = Math.min(positive.numberLength, iNeg);
            for (i++; i < limit; i++ ) {
                resDigits[i] = ~positive.digits[i];
            }
            if (i != positive.numberLength) {
                resDigits[i] = ~(-negative.digits[i] | positive.digits[i]);
            } else{
                  for (; i<iNeg; i++) {
                      resDigits[i] = -1;
                  }
                  // resDigits[i] = ~(-negative.digits[i] | 0);
                  resDigits[i] = negative.digits[i] - 1;
            }
            i++;
        } else {// iNeg == iPos
            // Applying two complement to negative and to result
            i = iPos;
            resDigits[i] = -(-negative.digits[i] | positive.digits[i]);
            i++;
        }
        limit = Math.min(negative.numberLength, positive.numberLength);
        for (; i < limit; i++) {
            // Applying two complement to negative and to result
            // resDigits[i] = ~(~negative.digits[i] | positive.digits[i] );
            resDigits[i] = negative.digits[i] & ~positive.digits[i];
        }
        for ( ; i < negative.numberLength; i++) {
            resDigits[i] = negative.digits[i];
        }

        return new BigInteger(-1, resLength, resDigits);
    }

    /** @see BigInteger#xor(BigInteger) */
    static BigInteger xor(BigInteger val, BigInteger that) {
        if (that.sign == 0) {
            return val;
        }
        if (val.sign == 0) {
            return that;
        }
        if (that.equals(BigInteger.MINUS_ONE)) {
            return val.not();
        }
        if (val.equals(BigInteger.MINUS_ONE)) {
            return that.not();
        }

        if (val.sign > 0) {
            if (that.sign > 0) {
                if (val.numberLength > that.numberLength) {
                    return xorPositive(val, that);
                } else {
                    return xorPositive(that, val);
                }
            } else {
                return xorDiffSigns(val, that);
            }
        } else {
            if (that.sign > 0) {
                return xorDiffSigns(that, val);
            } else if (that.getFirstNonzeroDigit() > val.getFirstNonzeroDigit()) {
                return xorNegative(that, val);
            } else {
                return xorNegative(val, that);
            }
        }
    }

    /** @return sign = 0, magnitude = longer.magnitude | shorter.magnitude */
    static BigInteger xorPositive(BigInteger longer, BigInteger shorter) {
        // PRE: longer and shorter are positive;
        // PRE: longer has at least as many digits as shorter
        int resLength = longer.numberLength;
        int[] resDigits = new int[resLength];
        int i = Math.min(longer.getFirstNonzeroDigit(), shorter.getFirstNonzeroDigit());
        for ( ; i < shorter.numberLength; i++) {
            resDigits[i] = longer.digits[i] ^ shorter.digits[i];
        }
        for ( ; i < longer.numberLength; i++ ){
            resDigits[i] = longer.digits[i];
        }

        return new BigInteger(1, resLength, resDigits);
    }

    /** @return sign = 0, magnitude = -val.magnitude ^ -that.magnitude */
    static BigInteger xorNegative(BigInteger val, BigInteger that){
        // PRE: val and that are negative
        // PRE: val has at least as many trailing zero digits as that
        int resLength = Math.max(val.numberLength, that.numberLength);
        int[] resDigits = new int[resLength];
        int iVal = val.getFirstNonzeroDigit();
        int iThat = that.getFirstNonzeroDigit();
        int i = iThat;
        int limit;


        if (iVal == iThat) {
            resDigits[i] = -val.digits[i] ^ -that.digits[i];
        } else {
            resDigits[i] = -that.digits[i];
            limit = Math.min(that.numberLength, iVal);
            for (i++; i < limit; i++) {
                resDigits[i] = ~that.digits[i];
            }
            // Remains digits in that?
            if (i == that.numberLength) {
                //Jumping over the remaining zero to the first non one
                for ( ;i < iVal; i++) {
                    //resDigits[i] = 0 ^ -1;
                    resDigits[i] = -1;
                }
                //resDigits[i] = -val.digits[i] ^ -1;
                resDigits[i] = val.digits[i] - 1;
            } else {
                resDigits[i] = -val.digits[i] ^ ~that.digits[i];
            }
        }

        limit = Math.min(val.numberLength, that.numberLength);
        //Perform ^ between that al val until that ends
        for (i++; i < limit; i++) {
            //resDigits[i] = ~val.digits[i] ^ ~that.digits[i];
            resDigits[i] = val.digits[i] ^ that.digits[i];
        }
        //Perform ^ between val digits and -1 until val ends
        for ( ; i < val.numberLength; i++) {
            //resDigits[i] = ~val.digits[i] ^ -1  ;
            resDigits[i] = val.digits[i] ;
        }
        for ( ; i < that.numberLength; i++) {
            //resDigits[i] = -1 ^ ~that.digits[i] ;
            resDigits[i] = that.digits[i];
        }

        return new BigInteger(1, resLength, resDigits);
    }

    /** @return sign = 1, magnitude = -(positive.magnitude ^ -negative.magnitude)*/
    static BigInteger xorDiffSigns(BigInteger positive, BigInteger negative){
        int resLength = Math.max(negative.numberLength, positive.numberLength);
        int[] resDigits;
        int iNeg = negative.getFirstNonzeroDigit();
        int iPos = positive.getFirstNonzeroDigit();
        int i;
        int limit;

        //The first
        if (iNeg < iPos) {
            resDigits = new int[resLength];
            i = iNeg;
            //resDigits[i] = -(-negative.digits[i]);
            resDigits[i] = negative.digits[i];
            limit = Math.min(negative.numberLength, iPos);
            //Skip the positive digits while they are zeros
            for (i++; i < limit; i++) {
                //resDigits[i] = ~(~negative.digits[i]);
                resDigits[i] = negative.digits[i];
            }
            //if the negative has no more elements, must fill the
            //result with the remaining digits of the positive
            if (i == negative.numberLength) {
                for ( ; i < positive.numberLength; i++) {
                    //resDigits[i] = ~(positive.digits[i] ^ -1) -> ~(~positive.digits[i])
                    resDigits[i] = positive.digits[i];
                }
            }
        } else if (iPos < iNeg) {
            resDigits = new int[resLength];
            i = iPos;
            //Applying two complement to the first non-zero digit of the result
            resDigits[i] = -positive.digits[i];
            limit = Math.min(positive.numberLength, iNeg);
            for (i++; i < limit; i++) {
                //Continue applying two complement the result
                resDigits[i] = ~positive.digits[i];
            }
            //When the first non-zero digit of the negative is reached, must apply
            //two complement (arithmetic negation) to it, and then operate
            if (i == iNeg) {
                resDigits[i] = ~(positive.digits[i] ^ -negative.digits[i]);
                i++;
            } else {
                //if the positive has no more elements must fill the remaining digits with
                //the negative ones
                for ( ; i < iNeg; i++) {
                    // resDigits[i] = ~(0 ^ 0)
                    resDigits[i] = -1;
                }
                for ( ; i < negative.numberLength; i++) {
                    //resDigits[i] = ~(~negative.digits[i] ^ 0)
                    resDigits[i] = negative.digits[i];
                }
            }
                } else {
            //The first non-zero digit of the positive and negative are the same
            i = iNeg;
            int digit = positive.digits[i] ^ -negative.digits[i];
            if (digit == 0) {
                limit = Math.min(positive.numberLength, negative.numberLength);
                for (i++; i < limit && (digit = positive.digits[i] ^ ~negative.digits[i]) == 0; i++)
                    ;
                if (digit == 0) {
                    // shorter has only the remaining virtual sign bits
                    for ( ; i < positive.numberLength && (digit = ~positive.digits[i]) == 0; i++)
                        ;
                    for ( ; i < negative.numberLength && (digit = ~negative.digits[i]) == 0; i++)
                        ;
                    if (digit == 0) {
                        resLength = resLength + 1;
                        resDigits = new int[resLength];
                        resDigits[resLength - 1] = 1;

                        return new BigInteger(-1, resLength, resDigits);
                }
            }
        }
            resDigits = new int[resLength];
            resDigits[i] = -digit;
            i++;
        }

        limit = Math.min(negative.numberLength, positive.numberLength);
        for ( ; i < limit; i++) {
            resDigits[i] = ~(~negative.digits[i] ^ positive.digits[i]);
        }
        for ( ; i < positive.numberLength; i++) {
            // resDigits[i] = ~(positive.digits[i] ^ -1)
            resDigits[i] = positive.digits[i];
        }
        for ( ; i < negative.numberLength; i++) {
            // resDigits[i] = ~(0 ^ ~negative.digits[i])
            resDigits[i] = negative.digits[i];
        }

        return new BigInteger(-1, resLength, resDigits);
    }
}