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 val.prepareJavaRepresentation(); 43 if (val.sign == 0) { 44 return 0; 45 } 46 int bLength = (val.numberLength << 5); 47 int highDigit = val.digits[val.numberLength - 1]; 48 49 if (val.sign < 0) { 50 int i = val.getFirstNonzeroDigit(); 51 // We reduce the problem to the positive case. 52 if (i == val.numberLength - 1) { 53 highDigit--; 54 } 55 } 56 // Subtracting all sign bits 57 bLength -= Integer.numberOfLeadingZeros(highDigit); 58 return bLength; 59 } 60 61 /** @see BigInteger#bitCount() */ 62 static int bitCount(BigInteger val) { 63 val.prepareJavaRepresentation(); 64 int bCount = 0; 65 66 if (val.sign == 0) { 67 return 0; 68 } 69 70 int i = val.getFirstNonzeroDigit(); 71 if (val.sign > 0) { 72 for ( ; i < val.numberLength; i++) { 73 bCount += Integer.bitCount(val.digits[i]); 74 } 75 } else {// (sign < 0) 76 // this digit absorbs the carry 77 bCount += Integer.bitCount(-val.digits[i]); 78 for (i++; i < val.numberLength; i++) { 79 bCount += Integer.bitCount(~val.digits[i]); 80 } 81 // We take the complement sum: 82 bCount = (val.numberLength << 5) - bCount; 83 } 84 return bCount; 85 } 86 87 /** 88 * Performs a fast bit testing for positive numbers. The bit to to be tested 89 * must be in the range {@code [0, val.bitLength()-1]} 90 */ 91 static boolean testBit(BigInteger val, int n) { 92 val.prepareJavaRepresentation(); 93 // PRE: 0 <= n < val.bitLength() 94 return ((val.digits[n >> 5] & (1 << (n & 31))) != 0); 95 } 96 97 /** 98 * Check if there are 1s in the lowest bits of this BigInteger 99 * 100 * @param numberOfBits the number of the lowest bits to check 101 * @return false if all bits are 0s, true otherwise 102 */ 103 static boolean nonZeroDroppedBits(int numberOfBits, int[] digits) { 104 int intCount = numberOfBits >> 5; 105 int bitCount = numberOfBits & 31; 106 int i; 107 108 for (i = 0; (i < intCount) && (digits[i] == 0); i++) { 109 ; 110 } 111 return ((i != intCount) || (digits[i] << (32 - bitCount) != 0)); 112 } 113 114 static void shiftLeftOneBit(int[] result, int[] source, int srcLen) { 115 int carry = 0; 116 for (int i = 0; i < srcLen; i++) { 117 int val = source[i]; 118 result[i] = (val << 1) | carry; 119 carry = val >>> 31; 120 } 121 if(carry != 0) { 122 result[srcLen] = carry; 123 } 124 } 125 126 static BigInteger shiftLeftOneBit(BigInteger source) { 127 source.prepareJavaRepresentation(); 128 int srcLen = source.numberLength; 129 int resLen = srcLen + 1; 130 int[] resDigits = new int[resLen]; 131 shiftLeftOneBit(resDigits, source.digits, srcLen); 132 return new BigInteger(source.sign, resLen, resDigits); 133 } 134 135 /** @see BigInteger#shiftRight(int) */ 136 static BigInteger shiftRight(BigInteger source, int count) { 137 source.prepareJavaRepresentation(); 138 int intCount = count >> 5; // count of integers 139 count &= 31; // count of remaining bits 140 if (intCount >= source.numberLength) { 141 return ((source.sign < 0) ? BigInteger.MINUS_ONE : BigInteger.ZERO); 142 } 143 int i; 144 int resLength = source.numberLength - intCount; 145 int[] resDigits = new int[resLength + 1]; 146 147 shiftRight(resDigits, resLength, source.digits, intCount, count); 148 if (source.sign < 0) { 149 // Checking if the dropped bits are zeros (the remainder equals to 150 // 0) 151 for (i = 0; (i < intCount) && (source.digits[i] == 0); i++) { 152 ; 153 } 154 // If the remainder is not zero, add 1 to the result 155 if ((i < intCount) 156 || ((count > 0) && ((source.digits[i] << (32 - count)) != 0))) { 157 for (i = 0; (i < resLength) && (resDigits[i] == -1); i++) { 158 resDigits[i] = 0; 159 } 160 if (i == resLength) { 161 resLength++; 162 } 163 resDigits[i]++; 164 } 165 } 166 return new BigInteger(source.sign, resLength, resDigits); 167 } 168 169 /** 170 * Shifts right an array of integers. Total shift distance in bits is 171 * intCount * 32 + count. 172 * 173 * @param result 174 * the destination array 175 * @param resultLen 176 * the destination array's length 177 * @param source 178 * the source array 179 * @param intCount 180 * the number of elements to be shifted 181 * @param count 182 * the number of bits to be shifted 183 * @return dropped bit's are all zero (i.e. remaider is zero) 184 */ 185 static boolean shiftRight(int[] result, int resultLen, int[] source, int intCount, int count) { 186 int i; 187 boolean allZero = true; 188 for (i = 0; i < intCount; i++) 189 allZero &= source[i] == 0; 190 if (count == 0) { 191 System.arraycopy(source, intCount, result, 0, resultLen); 192 i = resultLen; 193 } else { 194 int leftShiftCount = 32 - count; 195 196 allZero &= ( source[i] << leftShiftCount ) == 0; 197 for (i = 0; i < resultLen - 1; i++) { 198 result[i] = ( source[i + intCount] >>> count ) 199 | ( source[i + intCount + 1] << leftShiftCount ); 200 } 201 result[i] = ( source[i + intCount] >>> count ); 202 i++; 203 } 204 205 return allZero; 206 } 207 208 209 /** 210 * Performs a flipBit on the BigInteger, returning a BigInteger with the the 211 * specified bit flipped. 212 */ 213 static BigInteger flipBit(BigInteger val, int n){ 214 val.prepareJavaRepresentation(); 215 int resSign = (val.sign == 0) ? 1 : val.sign; 216 int intCount = n >> 5; 217 int bitN = n & 31; 218 int resLength = Math.max(intCount + 1, val.numberLength) + 1; 219 int[] resDigits = new int[resLength]; 220 int i; 221 222 int bitNumber = 1 << bitN; 223 System.arraycopy(val.digits, 0, resDigits, 0, val.numberLength); 224 225 if (val.sign < 0) { 226 if (intCount >= val.numberLength) { 227 resDigits[intCount] = bitNumber; 228 } else { 229 //val.sign<0 y intCount < val.numberLength 230 int firstNonZeroDigit = val.getFirstNonzeroDigit(); 231 if (intCount > firstNonZeroDigit) { 232 resDigits[intCount] ^= bitNumber; 233 } else if (intCount < firstNonZeroDigit) { 234 resDigits[intCount] = -bitNumber; 235 for (i=intCount + 1; i < firstNonZeroDigit; i++) { 236 resDigits[i]=-1; 237 } 238 resDigits[i] = resDigits[i]--; 239 } else { 240 i = intCount; 241 resDigits[i] = -((-resDigits[intCount]) ^ bitNumber); 242 if (resDigits[i] == 0) { 243 for (i++; resDigits[i] == -1 ; i++) { 244 resDigits[i] = 0; 245 } 246 resDigits[i]++; 247 } 248 } 249 } 250 } else {//case where val is positive 251 resDigits[intCount] ^= bitNumber; 252 } 253 return new BigInteger(resSign, resLength, resDigits); 254 } 255 } 256
