libcore/math/src/main/java/java/math/BitLevel.java

   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  * Static library that provides all the <b>bit level</b> operations for
  22  * {@link BigInteger}. The operations are:
  23  * <ul type="circle">
  24  * <li>Left Shifting</li>
  25  * <li>Right Shifting</li>
  26  * <li>Bit clearing</li>
  27  * <li>Bit setting</li>
  28  * <li>Bit counting</li>
  29  * <li>Bit testing</li>
  30  * <li>Getting of the lowest bit set</li>
  31  * </ul>
  32  * All operations are provided in immutable way, and some in both mutable and
  33  * immutable.
  34  */
  35 class BitLevel {
  36
  37     /** Just to denote that this class can't be instantiated. */
  38     private BitLevel() {}
  39
  40     /** @see BigInteger#bitLength() */
  41     static int bitLength(BigInteger val) {
  42         // BEGIN android-added
  43         val.establishOldRepresentation("BitLevel.bitLength");
  44         // END android-added
  45         if (val.sign == 0) {
  46             return 0;
  47         }
  48         int bLength = (val.numberLength << 5);
  49         int highDigit = val.digits[val.numberLength - 1];
  50
  51         if (val.sign < 0) {
  52             int i = val.getFirstNonzeroDigit();
  53             // We reduce the problem to the positive case.
  54             if (i == val.numberLength - 1) {
  55                 highDigit--;
  56             }
  57         }
  58         // Subtracting all sign bits
  59         bLength -= Integer.numberOfLeadingZeros(highDigit);
  60         return bLength;
  61     }
  62
  63     /** @see BigInteger#bitCount() */
  64     static int bitCount(BigInteger val) {
  65         // BEGIN android-added
  66         val.establishOldRepresentation("BitLevel.bitCount");
  67         // END android-added
  68         int bCount = 0;
  69
  70         if (val.sign == 0) {
  71             return 0;
  72         }
  73
  74         int i = val.getFirstNonzeroDigit();;
  75         if (val.sign > 0) {
  76             for ( ; i < val.numberLength; i++) {
  77                 bCount += Integer.bitCount(val.digits[i]);
  78             }
  79         } else {// (sign < 0)
  80             // this digit absorbs the carry
  81             bCount += Integer.bitCount(-val.digits[i]);
  82             for (i++; i < val.numberLength; i++) {
  83                 bCount += Integer.bitCount(~val.digits[i]);
  84             }
  85             // We take the complement sum:
  86             bCount = (val.numberLength << 5) - bCount;
  87         }
  88         return bCount;
  89     }
  90
  91     /**
  92      * Performs a fast bit testing for positive numbers. The bit to to be tested
  93      * must be in the range {@code [0, val.bitLength()-1]}
  94      */
  95     static boolean testBit(BigInteger val, int n) {
  96         // BEGIN android-added
  97         val.establishOldRepresentation("BitLevel.testBit");
  98         // END android-added
  99         // PRE: 0 <= n < val.bitLength()
 100         return ((val.digits[n >> 5] & (1 << (n & 31))) != 0);
 101     }
 102
 103     /**
 104      * Check if there are 1s in the lowest bits of this BigInteger
 105      *
 106      * @param numberOfBits the number of the lowest bits to check
 107      * @return false if all bits are 0s, true otherwise
 108      */
 109     static boolean nonZeroDroppedBits(int numberOfBits, int digits[]) {
 110         int intCount = numberOfBits >> 5;
 111         int bitCount = numberOfBits & 31;
 112         int i;
 113
 114         for (i = 0; (i < intCount) && (digits[i] == 0); i++) {
 115             ;
 116         }
 117         return ((i != intCount) || (digits[i] << (32 - bitCount) != 0));
 118     }
 119
 120     // BEGIN android-removed
 121     //  /** @see BigInteger#shiftLeft(int) */
 122     //  static BigInteger shiftLeft(BigInteger source, int count) {
 123     //      int intCount = count >> 5;
 124     //      count &= 31; // %= 32
 125     //      int resLength = source.numberLength + intCount
 126     //              + ( ( count == 0 ) ? 0 : 1 );
 127     //      int resDigits[] = new int[resLength];
 128     //
 129     //      shiftLeft(resDigits, source.digits, intCount, count);
 130     //         BigInteger result = new BigInteger(source.sign, resLength, resDigits);
 131     //         result.cutOffLeadingZeroes();
 132     //     return result;
 133     // }
 134     //
 135     // /**
 136     //  * Performs {@code val <<= count}.
 137     //  */
 138     // // val should have enough place (and one digit more)
 139     // static void inplaceShiftLeft(BigInteger val, int count) {
 140     //     int intCount = count >> 5; // count of integers
 141     //     val.numberLength += intCount
 142     //             + ( Integer
 143     //             .numberOfLeadingZeros(val.digits[val.numberLength - 1])
 144     //             - ( count & 31 ) >= 0 ? 0 : 1 );
 145     //     shiftLeft(val.digits, val.digits, intCount, count & 31);
 146     //     val.cutOffLeadingZeroes();
 147     //     val.unCache();
 148     // }
 149     //
 150     // /**
 151     //  * Abstractly shifts left an array of integers in little endian (i.e. shift
 152     //  * it right). Total shift distance in bits is intCount * 32 + count
 153     //  *
 154     //  * @param result the destination array
 155     //  * @param source the source array
 156     //  * @param intCount the shift distance in integers
 157     //  * @param count an additional shift distance in bits
 158     //  */
 159     // static void shiftLeft(int result[], int source[], int intCount, int count) {
 160     //     if (count == 0) {
 161     //         System.arraycopy(source, 0, result, intCount, result.length
 162     //                 - intCount);
 163     //     } else {
 164     //         int rightShiftCount = 32 - count;
 165     //
 166     //         result[result.length - 1] = 0;
 167     //         for (int i = result.length - 1; i > intCount; i--) {
 168     //             result[i] |= source[i - intCount - 1] >>> rightShiftCount;
 169     //             result[i - 1] = source[i - intCount - 1] << count;
 170     //         }
 171     //     }
 172     //
 173     //     for (int i = 0; i < intCount; i++) {
 174     //         result[i] = 0;
 175     //     }
 176     // }
 177     // END android-removed
 178
 179     static void shiftLeftOneBit(int result[], int source[], int srcLen) {
 180         int carry = 0;
 181         for(int i = 0; i < srcLen; i++) {
 182             int val = source[i];
 183             result[i] = (val << 1) | carry;
 184             carry = val >>> 31;
 185         }
 186         if(carry != 0) {
 187             result[srcLen] = carry;
 188         }
 189     }
 190
 191     static BigInteger shiftLeftOneBit(BigInteger source) {
 192         int srcLen = source.numberLength;
 193         int resLen = srcLen + 1;
 194         int resDigits[] = new int[resLen];
 195         shiftLeftOneBit(resDigits, source.digits, srcLen);
 196         BigInteger result = new BigInteger(source.sign, resLen, resDigits);
 197         result.cutOffLeadingZeroes();
 198         return result;
 199     }
 200
 201     /** @see BigInteger#shiftRight(int) */
 202     static BigInteger shiftRight(BigInteger source, int count) {
 203         // BEGIN android-added
 204         source.establishOldRepresentation("BitLevel.shiftRight");
 205         // END android-added
 206         int intCount = count >> 5; // count of integers
 207         count &= 31; // count of remaining bits
 208         if (intCount >= source.numberLength) {
 209             return ((source.sign < 0) ? BigInteger.MINUS_ONE : BigInteger.ZERO);
 210         }
 211         int i;
 212         int resLength = source.numberLength - intCount;
 213         int resDigits[] = new int[resLength + 1];
 214
 215         shiftRight(resDigits, resLength, source.digits, intCount, count);
 216         if (source.sign < 0) {
 217             // Checking if the dropped bits are zeros (the remainder equals to
 218             // 0)
 219             for (i = 0; (i < intCount) && (source.digits[i] == 0); i++) {
 220                 ;
 221             }
 222             // If the remainder is not zero, add 1 to the result
 223             if ((i < intCount)
 224                     || ((count > 0) && ((source.digits[i] << (32 - count)) != 0))) {
 225                 for (i = 0; (i < resLength) && (resDigits[i] == -1); i++) {
 226                     resDigits[i] = 0;
 227                 }
 228                 if (i == resLength) {
 229                     resLength++;
 230                 }
 231                 resDigits[i]++;
 232             }
 233         }
 234         BigInteger result = new BigInteger(source.sign, resLength, resDigits);
 235         result.cutOffLeadingZeroes();
 236         return result;
 237     }
 238
 239     /**
 240      * Performs {@code val >>= count} where {@code val} is a positive number.
 241      */
 242     static void inplaceShiftRight(BigInteger val, int count) {
 243         // BEGIN android-added
 244         val.establishOldRepresentation("BitLevel.inplaceShiftRight");
 245         // END android-added
 246         int sign = val.signum();
 247         if (count == 0 || val.signum() == 0)
 248             return;
 249         int intCount = count >> 5; // count of integers
 250         val.numberLength -= intCount;
 251         if (!shiftRight(val.digits, val.numberLength, val.digits, intCount,
 252                 count & 31)
 253                 && sign < 0) {
 254             // remainder not zero: add one to the result
 255             int i;
 256             for (i = 0; ( i < val.numberLength ) && ( val.digits[i] == -1 ); i++) {
 257                 val.digits[i] = 0;
 258             }
 259             if (i == val.numberLength) {
 260                 val.numberLength++;
 261             }
 262             val.digits[i]++;
 263         }
 264         val.cutOffLeadingZeroes();
 265         val.unCache();
 266     }
 267
 268     /**
 269      * Shifts right an array of integers. Total shift distance in bits is
 270      * intCount * 32 + count.
 271      *
 272      * @param result
 273      *            the destination array
 274      * @param resultLen
 275      *            the destination array's length
 276      * @param source
 277      *            the source array
 278      * @param intCount
 279      *            the number of elements to be shifted
 280      * @param count
 281      *            the number of bits to be shifted
 282      * @return dropped bit's are all zero (i.e. remaider is zero)
 283      */
 284     static boolean shiftRight(int result[], int resultLen, int source[],
 285             int intCount, int count) {
 286         int i;
 287         boolean allZero = true;
 288         for (i = 0; i < intCount; i++)
 289             allZero &= source[i] == 0;
 290         if (count == 0) {
 291             System.arraycopy(source, intCount, result, 0, resultLen);
 292             i = resultLen;
 293         } else {
 294             int leftShiftCount = 32 - count;
 295
 296             allZero &= ( source[i] << leftShiftCount ) == 0;
 297             for (i = 0; i < resultLen - 1; i++) {
 298                 result[i] = ( source[i + intCount] >>> count )
 299                 | ( source[i + intCount + 1] << leftShiftCount );
 300             }
 301             result[i] = ( source[i + intCount] >>> count );
 302             i++;
 303         }
 304
 305         return allZero;
 306     }
 307
 308
 309     /**
 310      * Performs a flipBit on the BigInteger, returning a BigInteger with the the
 311      * specified bit flipped.
 312      * @param intCount: the index of the element of the digits array where the operation will be performed
 313      * @param bitNumber: the bit's position in the intCount element
 314      */
 315     static BigInteger flipBit(BigInteger val, int n){
 316         // BEGIN android-added
 317         val.establishOldRepresentation("BitLevel.flipBit");
 318         // END android-added
 319         int resSign = (val.sign == 0) ? 1 : val.sign;
 320         int intCount = n >> 5;
 321         int bitN = n & 31;
 322         int resLength = Math.max(intCount + 1, val.numberLength) + 1;
 323         int resDigits[] = new int[resLength];
 324         int i;
 325
 326         int bitNumber = 1 << bitN;
 327         System.arraycopy(val.digits, 0, resDigits, 0, val.numberLength);
 328
 329         if (val.sign < 0) {
 330             if (intCount >= val.numberLength) {
 331                 resDigits[intCount] = bitNumber;
 332             } else {
 333                 //val.sign<0 y intCount < val.numberLength
 334                 int firstNonZeroDigit = val.getFirstNonzeroDigit();
 335                 if (intCount > firstNonZeroDigit) {
 336                     resDigits[intCount] ^= bitNumber;
 337                 } else if (intCount < firstNonZeroDigit) {
 338                     resDigits[intCount] = -bitNumber;
 339                     for (i=intCount + 1; i < firstNonZeroDigit; i++) {
 340                         resDigits[i]=-1;
 341                     }
 342                     resDigits[i] = resDigits[i]--;
 343                 } else {
 344                     i = intCount;
 345                     resDigits[i] = -((-resDigits[intCount]) ^ bitNumber);
 346                     if (resDigits[i] == 0) {
 347                         for (i++; resDigits[i] == -1 ; i++) {
 348                             resDigits[i] = 0;
 349                         }
 350                         resDigits[i]++;
 351                     }
 352                 }
 353             }
 354         } else {//case where val is positive
 355             resDigits[intCount] ^= bitNumber;
 356         }
 357         BigInteger result = new BigInteger(resSign, resLength, resDigits);
 358         result.cutOffLeadingZeroes();
 359         return result;
 360     }
 361 }