001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: */
017:
018: package java.math;
019:
020: /**
021: * Static library that provides all the <b>bit level</b> operations for
022: * {@link BigInteger}. The operations are:
023: * <ul type="circle">
024: * <li>Left Shifting</li>
025: * <li>Right Shifting</li>
026: * <li>Bit clearing</li>
027: * <li>Bit setting</li>
028: * <li>Bit counting</li>
029: * <li>Bit testing</li>
030: * <li>Getting of the lowest bit set</li>
031: * </ul>
032: * All operations are provided in immutable way, and some in both mutable and
033: * immutable.
034: *
035: * @author Intel Middleware Product Division
036: * @author Instituto Tecnologico de Cordoba
037: */
038: class BitLevel {
039:
040: /** Just to denote that this class can't be instantiated. */
041: private BitLevel() {
042: }
043:
044: /** @see BigInteger#bitLength() */
045: static int bitLength(BigInteger val) {
046: if (val.sign == 0) {
047: return 0;
048: }
049: int bLength = (val.numberLength << 5);
050: int highDigit = val.digits[val.numberLength - 1];
051:
052: if (val.sign < 0) {
053: int i = val.getFirstNonzeroDigit();
054: // We reduce the problem to the positive case.
055: if (i == val.numberLength - 1) {
056: highDigit--;
057: }
058: }
059: // Subtracting all sign bits
060: bLength -= Integer.numberOfLeadingZeros(highDigit);
061: return bLength;
062: }
063:
064: /** @see BigInteger#bitCount() */
065: static int bitCount(BigInteger val) {
066: int bCount = 0;
067:
068: if (val.sign == 0) {
069: return 0;
070: }
071:
072: int i = val.getFirstNonzeroDigit();
073: ;
074: if (val.sign > 0) {
075: for (; i < val.numberLength; i++) {
076: bCount += Integer.bitCount(val.digits[i]);
077: }
078: } else {// (sign < 0)
079: // this digit absorbs the carry
080: bCount += Integer.bitCount(-val.digits[i]);
081: for (i++; i < val.numberLength; i++) {
082: bCount += Integer.bitCount(~val.digits[i]);
083: }
084: // We take the complement sum:
085: bCount = (val.numberLength << 5) - bCount;
086: }
087: return bCount;
088: }
089:
090: /**
091: * Performs a fast bit testing for positive numbers. The bit to to be tested
092: * must be in the range {@code [0, val.bitLength()-1]}
093: */
094: static boolean testBit(BigInteger val, int n) {
095: // PRE: 0 <= n < val.bitLength()
096: return ((val.digits[n >> 5] & (1 << (n & 31))) != 0);
097: }
098:
099: /**
100: * Check if there are 1s in the lowest bits of this BigInteger
101: *
102: * @param numberOfBits the number of the lowest bits to check
103: * @return false if all bits are 0s, true otherwise
104: */
105: static boolean nonZeroDroppedBits(int numberOfBits, int digits[]) {
106: int intCount = numberOfBits >> 5;
107: int bitCount = numberOfBits & 31;
108: int i;
109:
110: for (i = 0; (i < intCount) && (digits[i] == 0); i++) {
111: ;
112: }
113: return ((i != intCount) || (digits[i] << (32 - bitCount) != 0));
114: }
115:
116: /** @see BigInteger#shiftLeft(int) */
117: static BigInteger shiftLeft(BigInteger source, int count) {
118: int intCount = count >> 5;
119: count &= 31; // %= 32
120: int resLength = source.numberLength + intCount
121: + ((count == 0) ? 0 : 1);
122: int resDigits[] = new int[resLength];
123:
124: shiftLeft(resDigits, source.digits, intCount, count);
125: BigInteger result = new BigInteger(source.sign, resLength,
126: resDigits);
127: result.cutOffLeadingZeroes();
128: return result;
129: }
130:
131: /**
132: * Performs {@code val <<= count}.
133: */
134: // val should have enough place (and one digit more)
135: static void inplaceShiftLeft(BigInteger val, int count) {
136: int intCount = count >> 5; // count of integers
137: val.numberLength += intCount
138: + (Integer
139: .numberOfLeadingZeros(val.digits[val.numberLength - 1])
140: - (count & 31) >= 0 ? 0 : 1);
141: shiftLeft(val.digits, val.digits, intCount, count & 31);
142: val.cutOffLeadingZeroes();
143: val.unCache();
144: }
145:
146: /**
147: * Abstractly shifts left an array of integers in little endian (i.e. shift
148: * it right). Total shift distance in bits is intCount * 32 + count
149: *
150: * @param result the destination array
151: * @param source the source array
152: * @param intCount the shift distance in integers
153: * @param count an additional shift distance in bits
154: */
155: static void shiftLeft(int result[], int source[], int intCount,
156: int count) {
157: if (count == 0) {
158: System.arraycopy(source, 0, result, intCount, result.length
159: - intCount);
160: } else {
161: int rightShiftCount = 32 - count;
162:
163: result[result.length - 1] = 0;
164: for (int i = result.length - 1; i > intCount; i--) {
165: result[i] |= source[i - intCount - 1] >>> rightShiftCount;
166: result[i - 1] = source[i - intCount - 1] << count;
167: }
168: }
169:
170: for (int i = 0; i < intCount; i++) {
171: result[i] = 0;
172: }
173: }
174:
175: /** @see BigInteger#shiftRight(int) */
176: static BigInteger shiftRight(BigInteger source, int count) {
177: int intCount = count >> 5; // count of integers
178: count &= 31; // count of remaining bits
179: if (intCount >= source.numberLength) {
180: return ((source.sign < 0) ? BigInteger.MINUS_ONE
181: : BigInteger.ZERO);
182: }
183: int i;
184: int resLength = source.numberLength - intCount;
185: int resDigits[] = new int[resLength + 1];
186:
187: shiftRight(resDigits, resLength, source.digits, intCount, count);
188: if (source.sign < 0) {
189: // Checking if the dropped bits are zeros (the remainder equals to
190: // 0)
191: for (i = 0; (i < intCount) && (source.digits[i] == 0); i++) {
192: ;
193: }
194: // If the remainder is not zero, add 1 to the result
195: if ((i < intCount)
196: || ((count > 0) && ((source.digits[i] << (32 - count)) != 0))) {
197: for (i = 0; (i < resLength) && (resDigits[i] == -1); i++) {
198: resDigits[i] = 0;
199: }
200: if (i == resLength) {
201: resLength++;
202: }
203: resDigits[i]++;
204: }
205: }
206: BigInteger result = new BigInteger(source.sign, resLength,
207: resDigits);
208: result.cutOffLeadingZeroes();
209: return result;
210: }
211:
212: /**
213: * Performs {@code val >>= count} where {@code val} is a positive number.
214: */
215: static void inplaceShiftRight(BigInteger val, int count) {
216: int sign = val.signum();
217: if (count == 0 || val.signum() == 0)
218: return;
219: int intCount = count >> 5; // count of integers
220: val.numberLength -= intCount;
221: if (!shiftRight(val.digits, val.numberLength, val.digits,
222: intCount, count & 31)
223: && sign < 0) {
224: // remainder not zero: add one to the result
225: int i;
226: for (i = 0; (i < val.numberLength) && (val.digits[i] == -1); i++) {
227: val.digits[i] = 0;
228: }
229: if (i == val.numberLength) {
230: val.numberLength++;
231: }
232: val.digits[i]++;
233: }
234: val.cutOffLeadingZeroes();
235: val.unCache();
236: }
237:
238: /**
239: * Shifts right an array of integers. Total shift distance in bits is
240: * intCount * 32 + count.
241: *
242: * @param result
243: * the destination array
244: * @param resultLen
245: * the destination array's length
246: * @param source
247: * the source array
248: * @param intCount
249: * the number of elements to be shifted
250: * @param count
251: * the number of bits to be shifted
252: * @return dropped bit's are all zero (i.e. remaider is zero)
253: */
254: static boolean shiftRight(int result[], int resultLen,
255: int source[], int intCount, int count) {
256: int i;
257: boolean allZero = true;
258: for (i = 0; i < intCount; i++)
259: allZero &= source[i] == 0;
260: if (count == 0) {
261: System.arraycopy(source, intCount, result, 0, resultLen);
262: i = resultLen;
263: } else {
264: int leftShiftCount = 32 - count;
265:
266: allZero &= (source[i] << leftShiftCount) == 0;
267: for (i = 0; i < resultLen - 1; i++) {
268: result[i] = (source[i + intCount] >>> count)
269: | (source[i + intCount + 1] << leftShiftCount);
270: }
271: result[i] = (source[i + intCount] >>> count);
272: i++;
273: }
274:
275: return allZero;
276: }
277:
278: /**
279: * Performs a flipBit on the BigInteger, returning a BigInteger with the the
280: * specified bit flipped.
281: * @param intCount: the index of the element of the digits array where the operation will be performed
282: * @param bitNumber: the bit's position in the intCount element
283: */
284: static BigInteger flipBit(BigInteger val, int n) {
285: int resSign = (val.sign == 0) ? 1 : val.sign;
286: int intCount = n >> 5;
287: int bitN = n & 31;
288: int resLength = Math.max(intCount + 1, val.numberLength) + 1;
289: int resDigits[] = new int[resLength];
290: int i;
291:
292: int bitNumber = 1 << bitN;
293: System.arraycopy(val.digits, 0, resDigits, 0, val.numberLength);
294:
295: if (val.sign < 0) {
296: if (intCount >= val.numberLength) {
297: resDigits[intCount] = bitNumber;
298: } else {
299: //val.sign<0 y intCount < val.numberLength
300: int firstNonZeroDigit = val.getFirstNonzeroDigit();
301: if (intCount > firstNonZeroDigit) {
302: resDigits[intCount] ^= bitNumber;
303: } else if (intCount < firstNonZeroDigit) {
304: resDigits[intCount] = -bitNumber;
305: for (i = intCount + 1; i < firstNonZeroDigit; i++) {
306: resDigits[i] = -1;
307: }
308: resDigits[i] = resDigits[i]--;
309: } else {
310: i = intCount;
311: resDigits[i] = -((-resDigits[intCount]) ^ bitNumber);
312: if (resDigits[i] == 0) {
313: for (i++; resDigits[i] == -1; i++) {
314: resDigits[i] = 0;
315: }
316: resDigits[i]++;
317: }
318: }
319: }
320: } else {//case where val is positive
321: resDigits[intCount] ^= bitNumber;
322: }
323: BigInteger result = new BigInteger(resSign, resLength,
324: resDigits);
325: result.cutOffLeadingZeroes();
326: return result;
327: }
328: }
|