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 // BEGIN android-added 193 source.establishOldRepresentation("BitLevel.shiftLeftOneBit"); 194 // END android-added 195 int srcLen = source.numberLength; 196 int resLen = srcLen + 1; 197 int resDigits[] = new int[resLen]; 198 shiftLeftOneBit(resDigits, source.digits, srcLen); 199 BigInteger result = new BigInteger(source.sign, resLen, resDigits); 200 result.cutOffLeadingZeroes(); 201 return result; 202 } 203 204 /** @see BigInteger#shiftRight(int) */ 205 static BigInteger shiftRight(BigInteger source, int count) { 206 // BEGIN android-added 207 source.establishOldRepresentation("BitLevel.shiftRight"); 208 // END android-added 209 int intCount = count >> 5; // count of integers 210 count &= 31; // count of remaining bits 211 if (intCount >= source.numberLength) { 212 return ((source.sign < 0) ? BigInteger.MINUS_ONE : BigInteger.ZERO); 213 } 214 int i; 215 int resLength = source.numberLength - intCount; 216 int resDigits[] = new int[resLength + 1]; 217 218 shiftRight(resDigits, resLength, source.digits, intCount, count); 219 if (source.sign < 0) { 220 // Checking if the dropped bits are zeros (the remainder equals to 221 // 0) 222 for (i = 0; (i < intCount) && (source.digits[i] == 0); i++) { 223 ; 224 } 225 // If the remainder is not zero, add 1 to the result 226 if ((i < intCount) 227 || ((count > 0) && ((source.digits[i] << (32 - count)) != 0))) { 228 for (i = 0; (i < resLength) && (resDigits[i] == -1); i++) { 229 resDigits[i] = 0; 230 } 231 if (i == resLength) { 232 resLength++; 233 } 234 resDigits[i]++; 235 } 236 } 237 BigInteger result = new BigInteger(source.sign, resLength, resDigits); 238 result.cutOffLeadingZeroes(); 239 return result; 240 } 241 242 /** 243 * Performs {@code val >>= count} where {@code val} is a positive number. 244 */ 245 static void inplaceShiftRight(BigInteger val, int count) { 246 // BEGIN android-added 247 val.establishOldRepresentation("BitLevel.inplaceShiftRight"); 248 // END android-added 249 int sign = val.signum(); 250 if (count == 0 || val.signum() == 0) 251 return; 252 int intCount = count >> 5; // count of integers 253 val.numberLength -= intCount; 254 if (!shiftRight(val.digits, val.numberLength, val.digits, intCount, 255 count & 31) 256 && sign < 0) { 257 // remainder not zero: add one to the result 258 int i; 259 for (i = 0; ( i < val.numberLength ) && ( val.digits[i] == -1 ); i++) { 260 val.digits[i] = 0; 261 } 262 if (i == val.numberLength) { 263 val.numberLength++; 264 } 265 val.digits[i]++; 266 } 267 val.cutOffLeadingZeroes(); 268 val.unCache(); 269 } 270 271 /** 272 * Shifts right an array of integers. Total shift distance in bits is 273 * intCount * 32 + count. 274 * 275 * @param result 276 * the destination array 277 * @param resultLen 278 * the destination array's length 279 * @param source 280 * the source array 281 * @param intCount 282 * the number of elements to be shifted 283 * @param count 284 * the number of bits to be shifted 285 * @return dropped bit's are all zero (i.e. remaider is zero) 286 */ 287 static boolean shiftRight(int result[], int resultLen, int source[], 288 int intCount, int count) { 289 int i; 290 boolean allZero = true; 291 for (i = 0; i < intCount; i++) 292 allZero &= source[i] == 0; 293 if (count == 0) { 294 System.arraycopy(source, intCount, result, 0, resultLen); 295 i = resultLen; 296 } else { 297 int leftShiftCount = 32 - count; 298 299 allZero &= ( source[i] << leftShiftCount ) == 0; 300 for (i = 0; i < resultLen - 1; i++) { 301 result[i] = ( source[i + intCount] >>> count ) 302 | ( source[i + intCount + 1] << leftShiftCount ); 303 } 304 result[i] = ( source[i + intCount] >>> count ); 305 i++; 306 } 307 308 return allZero; 309 } 310 311 312 /** 313 * Performs a flipBit on the BigInteger, returning a BigInteger with the the 314 * specified bit flipped. 315 * @param intCount: the index of the element of the digits array where the operation will be performed 316 * @param bitNumber: the bit's position in the intCount element 317 */ 318 static BigInteger flipBit(BigInteger val, int n){ 319 // BEGIN android-added 320 val.establishOldRepresentation("BitLevel.flipBit"); 321 // END android-added 322 int resSign = (val.sign == 0) ? 1 : val.sign; 323 int intCount = n >> 5; 324 int bitN = n & 31; 325 int resLength = Math.max(intCount + 1, val.numberLength) + 1; 326 int resDigits[] = new int[resLength]; 327 int i; 328 329 int bitNumber = 1 << bitN; 330 System.arraycopy(val.digits, 0, resDigits, 0, val.numberLength); 331 332 if (val.sign < 0) { 333 if (intCount >= val.numberLength) { 334 resDigits[intCount] = bitNumber; 335 } else { 336 //val.sign<0 y intCount < val.numberLength 337 int firstNonZeroDigit = val.getFirstNonzeroDigit(); 338 if (intCount > firstNonZeroDigit) { 339 resDigits[intCount] ^= bitNumber; 340 } else if (intCount < firstNonZeroDigit) { 341 resDigits[intCount] = -bitNumber; 342 for (i=intCount + 1; i < firstNonZeroDigit; i++) { 343 resDigits[i]=-1; 344 } 345 resDigits[i] = resDigits[i]--; 346 } else { 347 i = intCount; 348 resDigits[i] = -((-resDigits[intCount]) ^ bitNumber); 349 if (resDigits[i] == 0) { 350 for (i++; resDigits[i] == -1 ; i++) { 351 resDigits[i] = 0; 352 } 353 resDigits[i]++; 354 } 355 } 356 } 357 } else {//case where val is positive 358 resDigits[intCount] ^= bitNumber; 359 } 360 BigInteger result = new BigInteger(resSign, resLength, resDigits); 361 result.cutOffLeadingZeroes(); 362 return result; 363 } 364 } 365
