harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From telli...@apache.org
Subject svn commit: r454527 - in /incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math: BigDecimal.java BigInteger.java BitLevel.java Logical.java
Date Mon, 09 Oct 2006 21:43:54 GMT
Author: tellison
Date: Mon Oct  9 14:43:53 2006
New Revision: 454527

URL: http://svn.apache.org/viewvc?view=rev&rev=454527
Log:
Apply patch HARMONY-1636 ([classlib][java.math] optimization of two-complement related methods)

Modified:
    incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BigDecimal.java
    incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BigInteger.java
    incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BitLevel.java
    incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Logical.java

Modified: incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BigDecimal.java
URL: http://svn.apache.org/viewvc/incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BigDecimal.java?view=diff&rev=454527&r1=454526&r2=454527
==============================================================================
--- incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BigDecimal.java (original)
+++ incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BigDecimal.java Mon Oct  9 14:43:53 2006
@@ -1938,6 +1938,7 @@
             // math.0B=null unscaled value
             throw new StreamCorruptedException(Messages.getString("math.0B")); //$NON-NLS-1$
         }
+        bitLength = getUnscaledValue().bitLength();
     }
 
     private BigInteger getUnscaledValue() {

Modified: incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BigInteger.java
URL: http://svn.apache.org/viewvc/incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BigInteger.java?view=diff&rev=454527&r1=454526&r2=454527
==============================================================================
--- incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BigInteger.java (original)
+++ incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BigInteger.java Mon Oct  9 14:43:53 2006
@@ -75,6 +75,9 @@
             new BigInteger(1, 6), new BigInteger(1, 7), new BigInteger(1, 8),
             new BigInteger(1, 9), TEN };
 
+    /**/
+    private transient int firstNonzeroDigit = -2;
+    
     /* Serialized Fields */
 
     /** @ar.org.fitc.spec_ref */
@@ -170,7 +173,7 @@
             digits = new int[] { 0 };
         } else {
             sign = signum;
-            putBytesToIntegers(magnitude, false);
+            putBytesPositiveToIntegers(magnitude);
             cutOffLeadingZeroes();
         }
     }
@@ -183,11 +186,10 @@
         }
         if (val[0] < 0) {
             sign = -1;
-            putBytesToIntegers(val, true);
-            BitLevel.setTrueCoded(digits, numberLength);
+            putBytesNegativeToIntegers(val);
         } else {
             sign = 1;
-            putBytesToIntegers(val, false);
+            putBytesPositiveToIntegers(val);
         }
         cutOffLeadingZeroes();
     }
@@ -276,15 +278,13 @@
 
     /** @ar.org.fitc.spec_ref */
     public byte[] toByteArray() {
+        if( this.sign == 0 ){
+            return new byte[]{0};
+        }
         BigInteger temp = this;
         int bitLen = bitLength();
-        int bytesLen = (bitLen == 0) ? 1 : ((bitLen + 1) >> 3)
-                + (((bitLen + 1) & 7) == 0 ? 0 : 1);
-        if (sign < 0) {
-            temp = clone();
-            // Convert from the true coded form to the two's complement one
-            BitLevel.setTrueCoded(temp.digits, numberLength);
-        }
+        int iThis = getFirstNonzeroDigit();
+        int bytesLen = (bitLen >> 3) + 1;
         /* Puts the little-endian int array representing the magnitude
          * of this BigInteger into the big-endian byte array. */
         byte[] bytes = new byte[bytesLen];
@@ -303,6 +303,30 @@
             hB = bytesLen & 3;
             highBytes = (hB == 0) ? 4 : hB;
         }
+        
+        digitIndex = iThis;
+        bytesLen -= iThis << 2;
+        
+        if (sign < 0) {
+            digit = -temp.digits[digitIndex];
+            digitIndex++;
+            if(digitIndex == numberLength){
+                bytesInInteger = highBytes;
+            }
+            for (int i = 0; i < bytesInInteger; i++, digit >>= 8) {
+                bytes[--bytesLen] = (byte) digit;
+            }
+            while( bytesLen > firstByteNumber ){
+                digit = ~temp.digits[digitIndex];
+                digitIndex++;
+                if(digitIndex == numberLength){
+                    bytesInInteger = highBytes;
+                }
+                for (int i = 0; i < bytesInInteger; i++, digit >>= 8) {
+                    bytes[--bytesLen] = (byte) digit;
+                }
+            }
+        } else {
         while (bytesLen > firstByteNumber) {
             digit = temp.digits[digitIndex];
             digitIndex++;
@@ -313,6 +337,7 @@
                 bytes[--bytesLen] = (byte) digit;
             }
         }
+        }
         return bytes;
     }
 
@@ -382,34 +407,34 @@
         int i;
         n = (1 << (n & 31)); // int with 1 set to the needed position
         if (sign < 0) {
-            for (i = 0; (i < intCount) && (digits[i] == 0); i++) {
-                ;
+            int firstNonZeroDigit = getFirstNonzeroDigit();
+            if (  intCount < firstNonZeroDigit  ){
+                return false;
+            }else if( firstNonZeroDigit == intCount ){
+                digit = -digit;
+            }else{
+                digit = ~digit;
             }
-            digit = ((i == intCount) ? -digit : ~digit);
         }
         return ((digit & n) != 0);
     }
 
     /** @ar.org.fitc.spec_ref */
     public BigInteger setBit(int n) {
-        if (n < 0) {
-            // math.15=Negative bit address
-            throw new ArithmeticException(Messages.getString("math.15")); //$NON-NLS-1$
+        if( !testBit( n ) ){
+            return BitLevel.flipBit(this, n);
+        }else{
+            return this;
         }
-        int intCount = n >> 5; // count of integers: count / 32
-        return (((sign < 0) && (intCount >= numberLength)) ? this : BitLevel
-                .changeBit(this, intCount, n & 31, 2));
     }
 
     /** @ar.org.fitc.spec_ref */
     public BigInteger clearBit(int n) {
-        if (n < 0) {
-            // math.15=Negative bit address
-            throw new ArithmeticException(Messages.getString("math.15")); //$NON-NLS-1$
+        if( testBit( n ) ){
+            return BitLevel.flipBit(this, n);
+        }else{
+            return this;
         }
-        int intCount = n >> 5;
-        return (((sign == 0) || ((sign > 0) && (intCount >= numberLength))) ? this
-                : BitLevel.changeBit(this, intCount, n & 31, 3));
     }
 
     /** @ar.org.fitc.spec_ref */
@@ -418,7 +443,7 @@
             // math.15=Negative bit address
             throw new ArithmeticException(Messages.getString("math.15")); //$NON-NLS-1$
         }
-        return BitLevel.changeBit(this, n >> 5, n & 31, 1);
+        return BitLevel.flipBit(this, n);
     }
 
     /** @ar.org.fitc.spec_ref */
@@ -426,11 +451,8 @@
         if (sign == 0) {
             return -1;
         }
-        int i;
         // (sign != 0)  implies that exists some non zero digit 
-        for (i = 0; digits[i] == 0; i++) {
-            ;
-        }
+        int i = getFirstNonzeroDigit();
         return ((i << 5) + Integer.numberOfTrailingZeros(digits[i]));
     }
 
@@ -461,7 +483,7 @@
 
     /** @ar.org.fitc.spec_ref */
     public BigInteger andNot(BigInteger val) {
-        return Logical.and(this, Logical.not(val));
+        return Logical.andNot(this, val);
     }
 
     /** @ar.org.fitc.spec_ref */
@@ -800,19 +822,14 @@
     }
 
     /**
-     * Puts a big-endian byte array into a little-endian int array 
-     * representing non-negative "digits" of a big integer number.
+     * Puts a big-endian byte array into a little-endian int array.
      */
-    private void putBytesToIntegers(byte[] byteValues, boolean isNegative) {
+    private void putBytesPositiveToIntegers(byte[] byteValues) {
         int bytesLen = byteValues.length;
         int highBytes = bytesLen & 3;
         numberLength = (bytesLen >> 2) + ((highBytes == 0) ? 0 : 1);
         digits = new int[numberLength];
         int i = 0;
-        // Set the highest element of an int array negative if needed
-        if (isNegative) {
-            digits[numberLength - 1] = -1;
-        }
         // Put bytes to the int array starting from the end of the byte array
         while (bytesLen > highBytes) {
             digits[i++] = (byteValues[--bytesLen] & 0xFF)
@@ -827,6 +844,69 @@
     }
 
     /**
+     * Puts a big-endian byte array into a little-endian applying two complement.
+     */
+    private void putBytesNegativeToIntegers(byte[] byteValues) {
+        int bytesLen = byteValues.length;
+        int highBytes = bytesLen & 3;
+        numberLength = (bytesLen >> 2) + ((highBytes == 0) ? 0 : 1);
+        digits = new int[numberLength];
+        int i = 0;
+        //Setting the sign
+        digits [numberLength -1] = -1;
+        // Put bytes to the int array starting from the end of the byte array
+        while (bytesLen > highBytes) {
+            digits[i] = (byteValues[--bytesLen] & 0xFF)
+                    | (byteValues[--bytesLen] & 0xFF) << 8
+                    | (byteValues[--bytesLen] & 0xFF) << 16
+                    | (byteValues[--bytesLen] & 0xFF) << 24;
+            if ( digits[i] != 0 ) {
+                digits[i] = -digits[i];
+                firstNonzeroDigit = i;
+                i++;
+                while (bytesLen > highBytes) {
+                    digits[i] = (byteValues[--bytesLen] & 0xFF)
+                            | (byteValues[--bytesLen] & 0xFF) << 8
+                            | (byteValues[--bytesLen] & 0xFF) << 16
+                            | (byteValues[--bytesLen] & 0xFF) << 24;
+                    digits[i] = ~digits[i];
+                    i++;
+                }
+                break;
+            }
+            i++;
+        }
+        if( highBytes != 0 ){
+            // Put the first bytes in the highest element of the int array
+            if ( firstNonzeroDigit != -2  ){
+                for (int j = 0; j < bytesLen; j++) {
+                    digits[i] = (digits[i] << 8) | (byteValues[j] & 0xFF);
+                }
+                digits[i] = ~digits[i];
+            }else{
+                for (int j = 0; j < bytesLen; j++) {
+                    digits[i] = (digits[i] << 8) | (byteValues[j] & 0xFF);
+                }
+                digits[i] = -digits[i];
+            }
+        }
+    }
+    
+    int getFirstNonzeroDigit(){
+        if( firstNonzeroDigit == -2 ){
+            int i;
+            if( this.sign == 0  ){
+                i = -1;
+            } else{
+                for(i=0; digits[i]==0; i++)
+                    ;
+            }
+            firstNonzeroDigit = i;
+        }
+        return firstNonzeroDigit;
+    }
+    
+    /**
      * Returns a clone of {@code this}.
      * @return a copy of {@code this}, so that {@code equals(clone()) == true}.
      */
@@ -842,7 +922,7 @@
             ClassNotFoundException {
         in.defaultReadObject();
         sign = signum;
-        putBytesToIntegers(magnitude, false);
+        putBytesPositiveToIntegers(magnitude);
         cutOffLeadingZeroes();
     }
 

Modified: incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BitLevel.java
URL: http://svn.apache.org/viewvc/incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BitLevel.java?view=diff&rev=454527&r1=454526&r2=454527
==============================================================================
--- incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BitLevel.java (original)
+++ incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BitLevel.java Mon Oct  9 14:43:53 2006
@@ -40,27 +40,6 @@
     /** Just to denote that this class can't be instantied. */
     private BitLevel() {}
 
-    /**
-     * Converts bits represented by an int array from two's complementary code
-     * to true one and vice versa. Performs ~value + 1.
-     */
-    static int setTrueCoded(int arr[], final int length) {
-        int i;
-        // Until the first set bit, the bits are equal (i.e. 0)
-        for (i = 0; (i < length) && (arr[i] == 0); i++) {
-            ;
-        }
-        if (i == length) {
-            return 1;
-        }
-        // The digit that cointains the first set bit is (arithmetic) negated
-        arr[i] = -arr[i];
-        // From this position, the bits are (boolean) negated
-        for (i++; i < length; i++) {
-            arr[i] = ~arr[i];
-        }
-        return 0;
-    }
 
     /** @see BigInteger#bitLength() */
     static int bitLength(BigInteger val) {
@@ -69,12 +48,9 @@
         }
         int bLength = (val.numberLength << 5);
         int highDigit = val.digits[val.numberLength - 1];
-        int i;
 
         if (val.sign < 0) {
-            for (i = 0; val.digits[i] == 0; i++) {
-                ;
-            }
+            int i = val.getFirstNonzeroDigit();
             // We reduce the problem to the positive case.
             if (i == val.numberLength - 1) {
                 highDigit--;
@@ -88,16 +64,17 @@
     /** @see BigInteger#bitCount() */
     static int bitCount(BigInteger val) {
         int bCount = 0;
-        int i;
 
-        if (val.sign >= 0) {
-            for (i = 0; i < val.numberLength; i++) {
+        if (val.sign == 0) {
+            return 0;
+        }
+        
+        int i = val.getFirstNonzeroDigit();;
+        if (val.sign > 0) {
+            for ( ; i < val.numberLength; i++) {
                 bCount += Integer.bitCount(val.digits[i]);
             }
         } else {// (sign < 0)
-            for (i = 0; val.digits[i] == 0; i++) {
-                ;
-            }
             // this digit absorbs the carry
             bCount += Integer.bitCount(-val.digits[i]);
             for (i++; i < val.numberLength; i++) {
@@ -119,50 +96,6 @@
     }
 
     /**
-     * Changes a bit in the BigInteger depending on the operation.
-     * 
-     * @param intCount the number of an element in the array to change bit in
-     * @param bitNumber the bit's number in the intCount element
-     * @param operation's code: 1 for flipBit(), 2 for setBit(), 3 for
-     *        clearBit()
-     */
-    static BigInteger changeBit(BigInteger n, final int intCount,
-            int bitNumber, final int operation) {
-        int resSign = (n.sign == 0) ? 1 : n.sign;
-        int resLength;
-        resLength = Math.max(intCount, n.numberLength);
-        // increase length for a possible carry in the second
-        // BitLevel.setTrueCoded();
-        resLength++;
-        int resDigits[] = new int[resLength];
-        for (int i = n.numberLength; i < resLength; i++) {
-            resDigits[i] = 0;
-        }
-        System.arraycopy(n.digits, 0, resDigits, 0, n.numberLength);
-        if (n.sign < 0) {
-            BitLevel.setTrueCoded(resDigits, resLength);
-        }
-        bitNumber = 1 << bitNumber;
-        switch (operation) {
-            case 1: // flip bit
-                resDigits[intCount] ^= bitNumber;
-                break;
-            case 2: // set bit
-                resDigits[intCount] |= bitNumber;
-                break;
-            case 3: // clear bit
-                resDigits[intCount] &= ~bitNumber;
-                break;
-        }
-        if (n.sign < 0) {
-            BitLevel.setTrueCoded(resDigits, resLength);
-        }
-        BigInteger result = new BigInteger(resSign, resLength, resDigits);
-        result.cutOffLeadingZeroes();
-        return result;
-    }
-
-    /**
      * Check if there are 1s in the lowest bits of this BigInteger
      * 
      * @param numberOfBits the number of the lowest bits to check
@@ -193,16 +126,6 @@
     }
 
     /**
-     * Performs {@code val <<= count}.
-     */
-    static void inplaceShiftLeft(BigInteger val, int count) {
-        int intCount = count >> 5; // count of integers
-        val.numberLength -= intCount;
-        shiftLeft(val.digits, val.digits, intCount, count & 31);
-        val.cutOffLeadingZeroes();
-    }
-
-    /**
      * Shifts left an array of integers. Total shift distance in bits is
      * intCount * 32 + count
      * 
@@ -299,4 +222,53 @@
         }
     }
 
+    /**
+     * Performs a flipBit on the BigInteger, returning a BigInteger with the the
+     * specified bit flipped.
+     * @param intCount: the index of the element of the digits array where the operation will be performed
+     * @param bitNumber: the bit's position in the intCount element
+     */
+    static BigInteger flipBit(BigInteger val, int n){
+        int resSign = (val.sign == 0) ? 1 : val.sign;
+        int intCount = n >> 5;
+        int bitN = n & 31;
+        int resLength = Math.max(intCount + 1, val.numberLength) + 1;
+        int resDigits[] = new int[resLength];
+        int i;
+        
+        int bitNumber = 1 << bitN;
+        System.arraycopy(val.digits, 0, resDigits, 0, val.numberLength);
+        
+        if (val.sign < 0) {
+            if (intCount >= val.numberLength) {
+                resDigits[intCount] = bitNumber;
+            } else {
+                //val.sign<0 y intCount < val.numberLength
+                int firstNonZeroDigit = val.getFirstNonzeroDigit();
+                if (intCount > firstNonZeroDigit) {
+                    resDigits[intCount] ^= bitNumber;
+                } else if (intCount < firstNonZeroDigit) {
+                    resDigits[intCount] = -bitNumber;
+                    for (i=intCount + 1; i < firstNonZeroDigit; i++) {
+                        resDigits[i]=-1;
+                    }
+                    resDigits[i] = resDigits[i]--;
+                } else {
+                    i = intCount;
+                    resDigits[i] = -((-resDigits[intCount]) ^ bitNumber);
+                    if (resDigits[i] == 0) {
+                        for (i++; resDigits[i] == -1 ; i++) {
+                            resDigits[i] = 0;
+                        }
+                        resDigits[i]++;
+                    }
+                }
+            }
+        } else {//case where val is positive
+            resDigits[intCount] ^= bitNumber;
+        }
+        BigInteger result = new BigInteger(resSign, resLength, resDigits);
+        result.cutOffLeadingZeroes();
+        return result;
+    }
 }

Modified: incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Logical.java
URL: http://svn.apache.org/viewvc/incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Logical.java?view=diff&rev=454527&r1=454526&r2=454527
==============================================================================
--- incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Logical.java (original)
+++ incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Logical.java Mon Oct  9 14:43:53 2006
@@ -23,6 +23,7 @@
  * <ul type="circle">
  * <li>not</li>
  * <li>and</li>
+ * <li>andNot</li>
  * <li>or</li>
  * <li>xor</li>
  * </ul>
@@ -32,54 +33,18 @@
 class Logical {
 
     /** Just to denote that this class can't be instantied. */
+    
     private Logical() {}
 
-    /**
-     * Implements the element by element bitwise operations on two integer
-     * arrays. Arrays can be processed partially starting from 0 element.
-     * 
-     * @param dest the result array
-     * @param a the first source array
-     * @param aLen the number of elements of 'a' to be processed
-     * @param b the second source array
-     * @param bLen the number of elements of 'b' to be processed
-     */
-    static void bitOperation(int dest[], int a[], int aLen, int b[], int bLen,
-            int operation) {
-        int i = 0;
-
-        switch (operation) {
-            case 1: // and
-                for (; i < bLen; i++) {
-                    dest[i] = a[i] & b[i];
-                }
-                break;
-            case 2: // not
-                for (; i < bLen; i++) {
-                    dest[i] = ~b[i];
-                }
-                break;
-            case 3: // or
-                for (; i < bLen; i++) {
-                    dest[i] = a[i] | b[i];
-                }
-                break;
-            case 4: // xor
-                for (; i < bLen; i++) {
-                    dest[i] = a[i] ^ b[i];
-                }
-                break;
-        }
-        while (i < aLen) {
-            dest[i] = a[i++];
-        }
-    }
 
     /** @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;
 
@@ -108,7 +73,7 @@
         }
         // Now, the carry/borrow can be absorbed
         resDigits[i] = val.digits[i] + val.sign;
-        // Coping the remaining unchanged digit
+        // Copying the remaining unchanged digit
         for (i++; i < val.numberLength; i++) {
             resDigits[i] = val.digits[i];
         }
@@ -117,209 +82,490 @@
 
     /** @see BigInteger#and(BigInteger) */
     static BigInteger and(BigInteger val, BigInteger that) {
-        // This let us to throw an eventual NullPointerException if (that ==
-        // null)
-        if (that.sign == 0) {
+        if (that.sign == 0 || val.sign == 0) {
             return BigInteger.ZERO;
         }
-        if (val.sign == 0) {
+        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 resSign = (val.sign & that.sign);
+        
+        int resDigits[] = new int[resLength];
+        for ( ; i < resLength; i++) {
+            resDigits[i] = val.digits[i] & that.digits[i];
+        }
+        
+        BigInteger result = new BigInteger(1, resLength, resDigits);
+        result.cutOffLeadingZeroes();
+        return result;
+    }
+
+    /** @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
+        
+        BigInteger result = new BigInteger(1, resLength, resDigits);
+        result.cutOffLeadingZeroes();
+        return result;
+    }
+    
+    /** @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 valNeg[] = null;
-        int thatNeg[] = null;
+        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;
 
-        if (val.sign < 0) {
-            valNeg = new int[val.numberLength];
-            System.arraycopy(val.digits, 0, valNeg, 0, val.numberLength);
-        }
-        if (that.sign < 0) {
-            thatNeg = new int[that.numberLength];
-            System.arraycopy(that.digits, 0, thatNeg, 0, that.numberLength);
-        }
-        // some cases when either val or that is positive
-        if ((val.sign > 0) || (that.sign > 0)) {
-            if ((val.sign > 0) && (that.sign > 0)) {
-                // both are positive;
-                // the number of digits to AND is the length of the shorter
-                // array
-                int andLen = Math.min(val.numberLength, that.numberLength);
-                resLength = andLen;
+                    BigInteger result = new BigInteger(-1, resLength, resDigits);
+                    return result;
+                }
+            }
+        }
+        resLength = longer.numberLength;
                 resDigits = new int[resLength];
-                bitOperation(resDigits, val.digits, andLen, that.digits,
-                        andLen, 1);
-            } else {
-                if (val.numberLength > that.numberLength) {
-                    // val is longer than that
+        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];
+        }
+        
+        BigInteger result = new BigInteger(-1, resLength, resDigits);
+        return result;
+    }
+    
+    /** @see BigInteger#andNot(BigInteger) */
+    static BigInteger andNot(BigInteger val, BigInteger that) {
+        if (val.sign == 0) {
+            return BigInteger.ZERO;
+        }
+        if (that.sign == 0 ) {
+            return val;
+        }
+        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) {
-                        // val is positive and that is negative;
-                        // all digits should be and'ed
-                        resLength = val.numberLength;
-                        resDigits = new int[resLength];
-                        BitLevel.setTrueCoded(thatNeg, that.numberLength);
-                        bitOperation(resDigits, val.digits, val.numberLength,
-                                thatNeg, that.numberLength, 1);
-                    } else {
-                        // val is negative and that is positive
-                        // the number of digits to AND is the length of the
-                        // 'that' array
-                        resLength = that.numberLength;
-                        resDigits = new int[resLength];
-                        BitLevel.setTrueCoded(valNeg, val.numberLength);
-                        bitOperation(resDigits, valNeg, that.numberLength,
-                                that.digits, that.numberLength, 1);
+            if (that.sign > 0) {
+                return andNotPositive(val, that);
+            } else {
+                return andNotPositiveNegative(val, that);
                     }
                 } else {
-                    // val is shorter than that
-                    if (val.sign > 0) {
-                        // val is positive and that is negative;
-                        // the number of digits to AND is the length of the
-                        // 'val' array
-                        resLength = val.numberLength; // + 1?
+            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];
+        }
+        
+        BigInteger result = new BigInteger(1, val.numberLength, resDigits);
+        result.cutOffLeadingZeroes();
+        return result;
+    }
+    
+    /** @return sign = 1, magniutde = 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];
+        }
+        
+        BigInteger result = new BigInteger(1, resLength, resDigits);
+        result.cutOffLeadingZeroes();
+        return result;
+    }
+    
+    /** @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];
-                        BitLevel.setTrueCoded(thatNeg, that.numberLength);
-                        bitOperation(resDigits, thatNeg, val.numberLength,
-                                val.digits, val.numberLength, 1);
-                    } else {
-                        // val is negative and that is positive
-                        // the number of digits to AND is the length of the
-                        // 'that' array
-                        resLength = that.numberLength;
+                        resDigits[resLength - 1] = 1;
+                        
+                        BigInteger result = new BigInteger(-1, resLength, resDigits);
+                        return result;
+                    }
+                }
+            }
                         resDigits = new int[resLength];
-                        BitLevel.setTrueCoded(valNeg, val.numberLength);
-                        bitOperation(resDigits, that.digits, that.numberLength,
-                                valNeg, val.numberLength, 1);
+            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];
+        }
+        
+        BigInteger result = new BigInteger(-1, resLength, resDigits);
+        return result;
             }
+    
+    /** @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 {
-            // cases when both numbers are negative or
-            // either val or that is positive but both are of the same length
-            if (val.sign < 0) {
-                BitLevel.setTrueCoded(valNeg, val.numberLength);
-            }
-            if (that.sign < 0) {
-                BitLevel.setTrueCoded(thatNeg, that.numberLength);
-            }
-            // The resulting length should have one extra element
-            // for possible carry = 1 returned from BitLevel.setTrueCoded for a
-            // negative number
-            resLength = 1 + Math.max(val.numberLength, that.numberLength);
-            resDigits = new int[resLength];
-            if (val.numberLength >= that.numberLength) {
-                bitOperation(resDigits, (valNeg == null) ? val.digits : valNeg,
-                        val.numberLength, (thatNeg == null) ? that.digits
-                                : thatNeg, that.numberLength, 1);
-            } else {
-                bitOperation(resDigits, (thatNeg == null) ? that.digits
-                        : thatNeg, that.numberLength,
-                        (valNeg == null) ? val.digits : valNeg,
-                        val.numberLength, 1);
+                // 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];
         }
-        if (resSign < 0) {
-            resDigits[resLength - 1] = BitLevel.setTrueCoded(resDigits,
-                    resLength);
-        }
-        BigInteger result = new BigInteger(resSign, resLength, resDigits);
+        
+        BigInteger result = new BigInteger(1, resLength, resDigits);
         result.cutOffLeadingZeroes();
         return result;
     }
 
     /** @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;
         }
-        int resSign = (val.sign | that.sign);
-        int resLength;
-        int resDigits[];
-        int valNeg[] = null;
-        int thatNeg[] = null;
 
-        // some cases when either val or that is negative
-        if ((val.sign < 0) || (that.sign < 0)) {
-            if (val.sign < 0) {
-                valNeg = new int[val.numberLength];
-                System.arraycopy(val.digits, 0, valNeg, 0, val.numberLength);
-            }
-            if (that.sign < 0) {
-                thatNeg = new int[that.numberLength];
-                System.arraycopy(that.digits, 0, thatNeg, 0, that.numberLength);
-            }
-            if ((val.sign < 0) && (that.sign < 0)) {
-                // both are negative
-                int orLen = Math.min(val.numberLength, that.numberLength);
-                resLength = orLen + 1;
-                resDigits = new int[resLength];
-                BitLevel.setTrueCoded(valNeg, orLen);
-                BitLevel.setTrueCoded(thatNeg, orLen);
-                bitOperation(resDigits, valNeg, orLen, thatNeg, orLen, 3);
-                resDigits[resLength - 1] = -1;
-            } else {
-                if (val.numberLength > that.numberLength) {
-                    // val is longer than that
                     if (val.sign > 0) {
-                        // val is positive and that is negative
-                        resLength = that.numberLength + 1;
-                        resDigits = new int[resLength];
-                        BitLevel.setTrueCoded(thatNeg, that.numberLength);
-                        bitOperation(resDigits, val.digits, that.numberLength,
-                                thatNeg, that.numberLength, 3);
-                        resDigits[resLength - 1] = -1;
+            if (that.sign > 0) {
+                if (val.numberLength > that.numberLength) {
+                    return orPositive(val, that);
                     } else {
-                        // val is negative and that is positive
-                        resLength = val.numberLength;
-                        resDigits = new int[resLength];
-                        BitLevel.setTrueCoded(valNeg, val.numberLength);
-                        bitOperation(resDigits, valNeg, val.numberLength,
-                                that.digits, that.numberLength, 3);
+                    return orPositive(that, val);
                     }
                 } else {
-                    // that is longer than val
-                    if (val.sign > 0) {
-                        // val is positive and that is negative
-                        resLength = that.numberLength; // + 1?
-                        resDigits = new int[resLength];
-                        BitLevel.setTrueCoded(thatNeg, that.numberLength);
-                        bitOperation(resDigits, thatNeg, that.numberLength,
-                                val.digits, val.numberLength, 3);
+                return orDiffSigns(val, that);
+            }
                     } else {
-                        // that is positive and val is negative
-                        resLength = val.numberLength + 1;
-                        resDigits = new int[resLength];
-                        BitLevel.setTrueCoded(valNeg, val.numberLength);
-                        bitOperation(resDigits, that.digits, val.numberLength,
-                                valNeg, val.numberLength, 3);
-                        resDigits[resLength - 1] = -1;
+            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 = Math.min(longer.getFirstNonzeroDigit(), shorter.getFirstNonzeroDigit());
+        for (i = 0; i < shorter.numberLength; i++) {
+            resDigits[i] = longer.digits[i] | shorter.digits[i];
+        }
+        for ( ; i < resLength; i++) {
+            resDigits[i] = longer.digits[i];
+        }
+        
+        BigInteger result = new BigInteger(1, resLength, resDigits);
+        return result;
+    }
+    
+    /** @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 {
-            // cases when both numbers are positive and
-            // either val or that is negative but both are of the same length
-            resLength = Math.max(val.numberLength, that.numberLength);
-            resDigits = new int[resLength];
-            if (val.numberLength >= that.numberLength) {
-                bitOperation(resDigits, (valNeg == null) ? val.digits : valNeg,
-                        val.numberLength, (thatNeg == null) ? that.digits
-                                : thatNeg, that.numberLength, 3);
-            } else {
-                bitOperation(resDigits, (thatNeg == null) ? that.digits
-                        : thatNeg, that.numberLength,
-                        (valNeg == null) ? val.digits : valNeg,
-                        val.numberLength, 3);
+            for (i = iThat; i < iVal; i++) {
+                resDigits[i] = that.digits[i];
             }
+            resDigits[i] = that.digits[i] & (val.digits[i] - 1);
         }
-        if (resSign < 0) {
-            BitLevel.setTrueCoded(resDigits, resLength);
+        
+        for (i++; i < resLength; i++) {
+            resDigits[i] = val.digits[i] & that.digits[i];
         }
-        BigInteger result = new BigInteger(resSign, resLength, resDigits);
+        
+        BigInteger result = new BigInteger(-1, resLength, resDigits);
+        result.cutOffLeadingZeroes();
+        return result;
+    }
+    
+    /** @return sign = -1, magnitude = -(positive.magnitude | -negative.magnitude) */
+    static BigInteger orDiffSigns(BigInteger positive, BigInteger negative){
+        // Jumping over the least significative zero bits
+        int iNeg = negative.getFirstNonzeroDigit();
+        int iPos = positive.getFirstNonzeroDigit();
+        int i;
+        
+        // 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
+            // resDigits[first non zero] = - (-negative.digits[i])
+            i = iNeg;
+            resDigits[i] = negative.digits[i];
+        } else if (iPos < iNeg) {
+            i = iPos;
+            resDigits[i] = -positive.digits[i];
+        } else {// iNeg == iPos
+            // Applying two complement to negative and to result
+            i = iPos;
+            resDigits[i] = -(-negative.digits[i] | positive.digits[i]);
+        }
+        int limit = Math.min(negative.numberLength, positive.numberLength);
+        for (i++ ; 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];
+        }
+        
+        BigInteger result = new BigInteger(-1, resLength, resDigits);
         result.cutOffLeadingZeroes();
         return result;
     }
@@ -332,47 +578,208 @@
         if (val.sign == 0) {
             return that;
         }
-        int resSign = (val.sign == that.sign) ? 1 : -1;
+        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];
+        }
+        
+        BigInteger result = new BigInteger(1, resLength, resDigits);
+        result.cutOffLeadingZeroes();
+        return result;
+    }
+    
+    /** @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 valNeg[] = null;
-        int thatNeg[] = null;
-        if (val.sign < 0) {
-            valNeg = new int[val.numberLength];
-            System.arraycopy(val.digits, 0, valNeg, 0, val.numberLength);
-            BitLevel.setTrueCoded(valNeg, val.numberLength);
-        }
-        if (that.sign < 0) {
-            thatNeg = new int[that.numberLength];
-            System.arraycopy(that.digits, 0, thatNeg, 0, that.numberLength);
-            BitLevel.setTrueCoded(thatNeg, that.numberLength);
-        }
-        // First make XOR for N elements where N is the length of a shorter
-        // array.
-        int opLen = Math.min(val.numberLength, that.numberLength);
-        bitOperation(resDigits, (valNeg == null) ? val.digits : valNeg, opLen,
-                (thatNeg == null) ? that.digits : thatNeg, opLen, 4);
-        // Then define top elements.
-        if (val.numberLength != that.numberLength) {
+        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];
+        }
+        
+        BigInteger result = new BigInteger(1, resLength, resDigits);
+        result.cutOffLeadingZeroes();
+        return result;
+    }
+    
+    /** @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;
-            for (i = opLen; i < resLength; i++) {
-                if (val.sign == that.sign) {
-                    // the numbers have the same signs
-                    resDigits[i] = ((val.numberLength > that.numberLength)
-                    ? (valNeg == null) ? val.digits[i] : ~valNeg[i]
-                            : (thatNeg == null) ? that.digits[i] : ~thatNeg[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.digts[i] ^ 0)
+                    resDigits[i] = negative.digits[i];
+                }
+            }
                 } else {
-                    // the numbers have different signs
-                    resDigits[i] = ((val.numberLength >= that.numberLength)
-                    ? (val.sign < 0) ? valNeg[i] : ~val.digits[i]
-                            : (val.sign < 0) ? ~that.digits[i] : thatNeg[i]);
+            int digit;
+            //The first non-zero digit of the positive and negative are the same
+            i = iNeg;
+            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;
+                        
+                        BigInteger result = new BigInteger(-1, resLength, resDigits);
+                        return result;
                 }
             }
         }
-        if (resSign < 0) {
-            BitLevel.setTrueCoded(resDigits, resLength);
+            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++) { 
+            // resDidigts[i] = ~(0 ^ ~negative.digits[i])
+            resDigits[i] = negative.digits[i];
         }
-        BigInteger result = new BigInteger(resSign, resLength, resDigits);
+        
+        BigInteger result = new BigInteger(-1, resLength, resDigits);
         result.cutOffLeadingZeroes();
         return result;
     }



Mime
View raw message