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. */
BitLevel()38     private BitLevel() {}
39 
40     /** @see BigInteger#bitLength() */
bitLength(BigInteger val)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() */
bitCount(BigInteger val)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      */
testBit(BigInteger val, int n)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      */
nonZeroDroppedBits(int numberOfBits, int[] digits)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 
shiftLeftOneBit(int[] result, int[] source, int srcLen)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 
shiftLeftOneBit(BigInteger source)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) */
shiftRight(BigInteger source, int count)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      */
shiftRight(int[] result, int resultLen, int[] source, int intCount, int count)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      */
flipBit(BigInteger val, int n)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