} else {            t[target--] = s[src]>>>anticount;            while ( src >= 1 ){                t[target--] = (s[src]<<bitcount) | (s[--src]>>>anticount);            }            t[target--] = s[src]<<bitcount;        }        while( target >= 0 ){            t[target--] = 0;        }        data = t;        nWords += wordcount + 1;        // may have constructed high-order word of 0.        // if so, trim it        while ( nWords > 1 && data[nWords-1] == 0 )            nWords--;    }     /*     * normalize this number by shifting until     * the MSB of the number is at 0x08000000.     * This is in preparation for quoRemIteration, below.     * The idea is that, to make division easier, we want the     * divisor to be "normalized" -- usually this means shifting     * the MSB into the high words sign bit. But because we know that     * the quotient will be 0 < q < 10, we would like to arrange that     * the dividend not span up into another word of precision.     * (This needs to be explained more clearly!)     */    public int    normalizeMe() throws IllegalArgumentException {        int src;        int wordcount = 0;        int bitcount  = 0;        int v = 0;        for ( src= nWords-1 ; src >= 0 && (v=data[src]) == 0 ; src--){            wordcount += 1;        }        if ( src < 0 ){            // oops. Value is zero. Cannot normalize it!            throw new IllegalArgumentException("zero value");        }        /*         * In most cases, we assume that wordcount is zero. This only         * makes sense, as we try not to maintain any high-order         * words full of zeros. In fact, if there are zeros, we will         * simply SHORTEN our number at this point. Watch closely...         */        nWords -= wordcount;        /*         * Compute how far left we have to shift v s.t. its highest-         * order bit is in the right place. Then call lshiftMe to         * do the work.         */        if ( (v & 0xf0000000) != 0 ){            // will have to shift up into the next word.            // too bad.            for( bitcount = 32 ; (v & 0xf0000000) != 0 ; bitcount-- )                v >>>= 1;        } else {            while ( v <= 0x000fffff ){                // hack: byte-at-a-time shifting                v <<= 8;                bitcount += 8;            }            while ( v <= 0x07ffffff ){                v <<= 1;                bitcount += 1;            }        }        if ( bitcount != 0 )            lshiftMe( bitcount );        return bitcount;    }     /*     * Multiply a FDBigInt by an int.     * Result is a new FDBigInt.     */    public FDBigInt    mult( int iv ) {        long v = iv;        int r[];        long p;         // guess adequate size of r.        r = new int[ ( v * ((long)data[nWords-1]&0xffffffffL) > 0xfffffffL ) ? nWords+1 : nWords ];        p = 0L;        for( int i=0; i < nWords; i++ ) {            p += v * ((long)data[i]&0xffffffffL);            r[i] = (int)p;            p >>>= 32;        }        if ( p == 0L){            return new FDBigInt( r, nWords );        } else {            r[nWords] = (int)p;            return new FDBigInt( r, nWords+1 );        }    }     /*     * Multiply a FDBigInt by an int and add another int.     * Result is computed in place.     * Hope it fits!     */    public void    multaddMe( int iv, int addend ) {        long v = iv;        long p;         // unroll 0th iteration, doing addition.        p = v * ((long)data[0]&0xffffffffL) + ((long)addend&0xffffffffL);        data[0] = (int)p;        p >>>= 32;        for( int i=1; i < nWords; i++ ) {            p += v * ((long)data[i]&0xffffffffL);            data[i] = (int)p;            p >>>= 32;        }        if ( p != 0L){            data[nWords] = (int)p; // will fail noisily if illegal!            nWords++;        }    }     /*     * Multiply a FDBigInt by another FDBigInt.     * Result is a new FDBigInt.     */    public FDBigInt    mult( FDBigInt other ){        // crudely guess adequate size for r        int r[] = new int[ nWords + other.nWords ];        int i;        // I think I am promised zeros...         for( i = 0; i < this.nWords; i++ ){            long v = (long)this.data[i] & 0xffffffffL; // UNSIGNED CONVERSION            long p = 0L;            int j;            for( j = 0; j < other.nWords; j++ ){                p += ((long)r[i+j]&0xffffffffL) + v*((long)other.data[j]&0xffffffffL); // UNSIGNED CONVERSIONS ALL 'ROUND.                r[i+j] = (int)p;                p >>>= 32;            }            r[i+j] = (int)p;        }        // compute how much of r we actually needed for all that.        for ( i = r.length-1; i> 0; i--)            if ( r[i] != 0 )                break;        return new FDBigInt( r, i+1 );    }     /*     * Add one FDBigInt to another. Return a FDBigInt     */    public FDBigInt    add( FDBigInt other ){        int i;        int a[], b[];        int n, m;        long c = 0L;        // arrange such that a.nWords >= b.nWords;        // n = a.nWords, m = b.nWords        if ( this.nWords >= other.nWords ){            a = this.data;            n = this.nWords;            b = other.data;            m = other.nWords;        } else {            a = other.data;            n = other.nWords;            b = this.data;            m = this.nWords;        }        int r[] = new int[ n ];        for ( i = 0; i < n; i++ ){            c += (long)a[i] & 0xffffffffL;            if ( i < m ){                c += (long)b[i] & 0xffffffffL;            }            r[i] = (int) c;            c >>= 32; // signed shift.        }        if ( c != 0L ){            // oops -- carry out -- need longer result.            int s[] = new int[ r.length+1 ];            System.arraycopy( r, 0, s, 0, r.length );            s[i++] = (int)c;            return new FDBigInt( s, i );        }        return new FDBigInt( r, i );    }     /*     * Subtract one FDBigInt from another. Return a FDBigInt     * Assert that the result is positive.     */    public FDBigInt    sub( FDBigInt other ){        int r[] = new int[ this.nWords ];        int i;        int n = this.nWords;        int m = other.nWords;        int nzeros = 0;        long c = 0L;        for ( i = 0; i < n; i++ ){            c += (long)this.data[i] & 0xffffffffL;            if ( i < m ){                c -= (long)other.data[i] & 0xffffffffL;            }            if ( ( r[i] = (int) c ) == 0 )                nzeros++;            else                nzeros = 0;            c >>= 32; // signed shift        }        assert c == 0L : c; // borrow out of subtract        assert dataInRangeIsZero(i, m, other); // negative result of subtract        return new FDBigInt( r, n-nzeros );    }     private static boolean dataInRangeIsZero(int i, int m, FDBigInt other) {        while ( i < m )            if (other.data[i++] != 0)                return false;        return true;    }     /*     * Compare FDBigInt with another FDBigInt. Return an integer     * >0: this > other     *  0: this == other     * <0: this < other     */    public int    cmp( FDBigInt other ){        int i;        if ( this.nWords > other.nWords ){            // if any of my high-order words is non-zero,            // then the answer is evident            int j = other.nWords-1;            for ( i = this.nWords-1; i > j ; i-- )                if ( this.data[i] != 0 ) return 1;        }else if ( this.nWords < other.nWords ){            // if any of other's high-order words is non-zero,            // then the answer is evident            int j = this.nWords-1;            for ( i = other.nWords-1; i > j ; i-- )                if ( other.data[i] != 0 ) return -1;        } else{            i = this.nWords-1;        }        for ( ; i > 0 ; i-- )            if ( this.data[i] != other.data[i] )                break;        // careful! want unsigned compare!        // use brute force here.        int a = this.data[i];        int b = other.data[i];        if ( a < 0 ){            // a is really big, unsigned            if ( b < 0 ){                return a-b; // both big, negative            } else {                return 1; // b not big, answer is obvious;            }        } else {            // a is not really big            if ( b < 0 ) {                // but b is really big                return -1;            } else {                return a - b;            }        }    }     /*     * Compute     * q = (int)( this / S )     * this = 10 * ( this mod S )     * Return q.     * This is the iteration step of digit development for output.     * We assume that S has been normalized, as above, and that     * "this" has been lshift'ed accordingly.     * Also assume, of course, that the result, q, can be expressed     * as an integer, 0 <= q < 10.     */    public int    quoRemIteration( FDBigInt S )throws IllegalArgumentException {        // ensure that this and S have the same number of        // digits. If S is properly normalized and q < 10 then        // this must be so.        if ( nWords != S.nWords ){            throw new IllegalArgumentException("disparate values");        }        // estimate q the obvious way. We will usually be        // right. If not, then we're only off by a little and        // will re-add.        int n = nWords-1;        long q = ((long)data[n]&0xffffffffL) / (long)S.data[n];        long diff = 0L;        for ( int i = 0; i <= n ; i++ ){            diff += ((long)data[i]&0xffffffffL) -  q*((long)S.data[i]&0xffffffffL);            data[i] = (int)diff;            diff >>= 32; // N.B. SIGNED shift.        }        if ( diff != 0L ) {            // damn, damn, damn. q is too big.            // add S back in until this turns +. This should            // not be very many times!            long sum = 0L;            while ( sum ==  0L ){                sum = 0L;                for ( int i = 0; i <= n; i++ ){                    sum += ((long)data[i]&0xffffffffL) +  ((long)S.data[i]&0xffffffffL);                    data[i] = (int) sum;                    sum >>= 32; // Signed or unsigned, answer is 0 or 1                }                /*                 * Originally the following line read                 * "if ( sum !=0 && sum != -1 )"                 * but that would be wrong, because of the                 * treatment of the two values as entirely unsigned,                 * it would be impossible for a carry-out to be interpreted                 * as -1 -- it would have to be a single-bit carry-out, or                 * +1.                 */                assert sum == 0 || sum == 1 : sum; // carry out of division correction                q -= 1;            }        }        // finally, we can multiply this by 10.        // it cannot overflow, right, as the high-order word has        // at least 4 high-order zeros!        long p = 0L;        for ( int i = 0; i <= n; i++ ){            p += 10*((long)data[i]&0xffffffffL);            data[i] = (int)p;            p >>= 32; // SIGNED shift.        }        assert p == 0L : p; // Carry out of *10        return (int)q;    }     public long    longValue(){        // if this can be represented as a long, return the value        assert this.nWords > 0 : this.nWords; // longValue confused         if (this.nWords == 1)            return ((long)data[0]&0xffffffffL);         assert dataInRangeIsZero(2, this.nWords, this); // value too big        assert data[1] >= 0;  // value too big        return ((long)(data[1]) << 32) | ((long)data[0]&0xffffffffL);    }     public String    toString() {        StringBuffer r = new StringBuffer(30);        r.append('[');        int i = Math.min( nWords-1, data.length-1) ;        if ( nWords > data.length ){            r.append( "("+data.length+"<"+nWords+"!)" );        }        for( ; i> 0 ; i-- ){            r.append( Integer.toHexString( data[i] ) );            r.append(' ');        }        r.append( Integer.toHexString( data[0] ) );        r.append(']');        return new String( r );    }}

Lines 2501–2878 of 2878. Previous lines