先來(lái)掌握一些常用的位運(yùn)算操作：
等式：-n = ~(n - 1) = ~n + 1（-n等于其各位取反加1）；
獲取整數(shù)n的二進(jìn)制中最后一個(gè)1：-n&n 或(~n+1)&n或 ~(n - 1)&n；
如：n = 010100，則 -n = 101100, n&(n - 1)=000100；去掉整數(shù)n的二進(jìn)制中最后一個(gè)1：n&(n - 1)。如：n = 010100, n -1 = 010011, n&(n - 1) = 010000。
加法 a + b
思考：
a^b可得到對(duì)應(yīng)位沒(méi)有進(jìn)位時(shí)的和，如果該位進(jìn)位了，其值為0，該位沒(méi)有進(jìn)位，其值為a+b對(duì)應(yīng)位的結(jié)果（不考慮低位進(jìn)位）
a&b可得到各位產(chǎn)生的進(jìn)位值，如果該位沒(méi)有進(jìn)位，其值為0，該位進(jìn)位了，其值為1
(a&b)<<1正好代表a+b有進(jìn)位的位進(jìn)位后的結(jié)果
如果使用a^b+(a&b)<<1來(lái)表示a+b的值有問(wèn)題的地方在于不能保證這兩個(gè)子表達(dá)式相加過(guò)程不產(chǎn)生進(jìn)位
所以迭代也好，遞歸也好，一定要讓(a&b)也就是進(jìn)位的情況不存在，直接可以用a^b表示出不產(chǎn)生進(jìn)位的加法
注意在多次循環(huán)中，a,b的值也要相應(yīng)變化，當(dāng)然數(shù)據(jù)溢出的問(wèn)題本篇博客就不考慮了
解答如下：
用 ^，&和<<即可實(shí)現(xiàn)，，a&b可得到各位產(chǎn)生的進(jìn)位值。
如：a=010010, b=100111，計(jì)算過(guò)程如下：
- 每輪首先判斷b是否為0，為0則結(jié)束，把a(bǔ)的值作為結(jié)果返回
- 第一輪：通過(guò)(a&b)=000010 得出a+b結(jié)果中需要進(jìn)位的位置
(a&b)<<1 將進(jìn)位的值全體左移一位后，表示進(jìn)位部分進(jìn)位后的值
a^b=110101，表示a+b不進(jìn)位部分相加的結(jié)果
由于進(jìn)位大于0，把a(bǔ)^b的值賦給a，此時(shí)a=110101,(a&b)<<1的值賦給b，此時(shí)b=000100；
進(jìn)入下一輪中，新的a+b=老的a+b的值=循環(huán)下去b值為0時(shí)a的值（此時(shí)代表不產(chǎn)生進(jìn)位） - 第二輪：a^b=110001，(a&b)<<1=001000（進(jìn)位）。進(jìn)位大于0，進(jìn)入下一輪：a=110001,b=001000；
- 第三輪：a^b=111001，(a&b)<<1=000000（進(jìn)位）。進(jìn)位等于0，終止；
結(jié)果為：111001。
非遞歸
int add1(int a, int b)
{
int carry; // 進(jìn)位
while (b!=0)
{
carry = (a & b) << 1; // a & b取各位的進(jìn)位，進(jìn)位作用于對(duì)應(yīng)位的高1位
a = a ^ b;
b = carry;
}
return a;
}
遞歸
int add2(int a, int b)
{
if (0 == b) return a;
else
{
int carry = (a & b) << 1;
a = a ^ b;
return add2(a, carry);
}
// 簡(jiǎn)化版
// return b ? add2(a^b,(a&b)<<1) : a;
}
減法：a-b
由a-b=a+(-b)，~（b-1）=-b可得a-b=a+（-b）=a+((b-1))=a+b + 1。把減法轉(zhuǎn)化為加法即可。
int sub(int a, int b)
{
return add(a, add(~b, 1));
}
乘法：a*b
基礎(chǔ)版：觀察如下
1011
* 1010
--------
10110 (1011<<1,相當(dāng)于乘以0010)
1011000 (1011<<3,相當(dāng)于乘以1000)
--------
1101110
可以看到，二進(jìn)制乘法的原理是：從乘數(shù)的低位到高位，遇到1并且這個(gè)1在乘數(shù)的右起第i（i從0開(kāi)始數(shù)）位，那么就把被乘數(shù)左移i位得到 temp_i 。直到乘數(shù)中的1遍歷完后，把根據(jù)各位1而得到的被乘數(shù)的左移值們 temp_i 相加起來(lái)即得乘法結(jié)果。那么根據(jù)這個(gè)原理，可以得到實(shí)現(xiàn)代碼：這里要點(diǎn)為：用i記錄當(dāng)前遍歷的乘數(shù)位,當(dāng)前位為1則被乘數(shù)左移i位并加到和中，同時(shí)i++處理下一位；為0則乘數(shù)右移，i++，處理下一位......直到乘數(shù)==0說(shuō)明乘數(shù)中的1遍歷完了。此時(shí)把和返回即可。
需要注意的是，補(bǔ)碼乘法符號(hào)位也是參與運(yùn)算的，具體參見(jiàn)深入理解計(jì)算機(jī)系統(tǒng)第二章內(nèi)容（無(wú)符號(hào)乘法和補(bǔ)碼乘法的位級(jí)等價(jià)性）
// 值得注意的是網(wǎng)上的程序片段中使用的>>代表算術(shù)右移，而在考慮到補(bǔ)碼
// 符號(hào)位為1的可能性的時(shí)候必須采用邏輯右移>>>，不然會(huì)死循環(huán)
int multi(int a,int b){
int i=0;
int res=0;
while(b!=0){//乘數(shù)為0則結(jié)束
//處理乘數(shù)當(dāng)前位
if((b&1)==1){
res+=(a<<i);
b=b>>>1;
++i;//i記錄當(dāng)前位是第幾位
}else{
b=b>>>1;
++i;
}
}
return res;
}
進(jìn)階思考：在基礎(chǔ)版之上，如果遇到兩個(gè)大數(shù)相乘，采用什么方式呢？
采用帶有分治法思想的乘法來(lái)計(jì)算
image.png
image.png
那么我們看一下java8里BigInteger類如何實(shí)現(xiàn)的
/**
* Returns a BigInteger whose value is {@code (this * val)}.
*
* @implNote An implementation may offer better algorithmic
* performance when {@code val == this}.
*
* @param val value to be multiplied by this BigInteger.
* @return {@code this * val}
*/
public BigInteger multiply(BigInteger val) {
if (val.signum == 0 || signum == 0)
return ZERO;
int xlen = mag.length;
if (val == this && xlen > MULTIPLY_SQUARE_THRESHOLD) {
return square();
}
int ylen = val.mag.length;
if ((xlen < KARATSUBA_THRESHOLD) || (ylen < KARATSUBA_THRESHOLD)) {
int resultSign = signum == val.signum ? 1 : -1;
if (val.mag.length == 1) {
return multiplyByInt(mag,val.mag[0], resultSign);
}
if (mag.length == 1) {
return multiplyByInt(val.mag,mag[0], resultSign);
}
int[] result = multiplyToLen(mag, xlen,
val.mag, ylen, null);
result = trustedStripLeadingZeroInts(result);
return new BigInteger(result, resultSign);
} else {
if ((xlen < TOOM_COOK_THRESHOLD) && (ylen < TOOM_COOK_THRESHOLD)) {
return multiplyKaratsuba(this, val);
} else {
return multiplyToomCook3(this, val);
}
}
}
/**
* Multiplies two BigIntegers using the Karatsuba multiplication
* algorithm. This is a recursive divide-and-conquer algorithm which is
* more efficient for large numbers than what is commonly called the
* "grade-school" algorithm used in multiplyToLen. If the numbers to be
* multiplied have length n, the "grade-school" algorithm has an
* asymptotic complexity of O(n^2). In contrast, the Karatsuba algorithm
* has complexity of O(n^(log2(3))), or O(n^1.585). It achieves this
* increased performance by doing 3 multiplies instead of 4 when
* evaluating the product. As it has some overhead, should be used when
* both numbers are larger than a certain threshold (found
* experimentally).
*
* See: http://en.wikipedia.org/wiki/Karatsuba_algorithm
*/
private static BigInteger multiplyKaratsuba(BigInteger x, BigInteger y) {
int xlen = x.mag.length;
int ylen = y.mag.length;
// The number of ints in each half of the number.
int half = (Math.max(xlen, ylen)+1) / 2;
// xl and yl are the lower halves of x and y respectively,
// xh and yh are the upper halves.
BigInteger xl = x.getLower(half);
BigInteger xh = x.getUpper(half);
BigInteger yl = y.getLower(half);
BigInteger yh = y.getUpper(half);
BigInteger p1 = xh.multiply(yh); // p1 = xh*yh
BigInteger p2 = xl.multiply(yl); // p2 = xl*yl
// p3=(xh+xl)*(yh+yl)
BigInteger p3 = xh.add(xl).multiply(yh.add(yl));
// result = p1 * 2^(32*2*half) + (p3 - p1 - p2) * 2^(32*half) + p2
BigInteger result = p1.shiftLeft(32*half).add(p3.subtract(p1).subtract(p2)).shiftLeft(32*half).add(p2);
if (x.signum != y.signum) {
return result.negate();
} else {
return result;
}
}
在此之上還有更低復(fù)雜度的算法
/**
* Multiplies two BigIntegers using a 3-way Toom-Cook multiplication
* algorithm. This is a recursive divide-and-conquer algorithm which is
* more efficient for large numbers than what is commonly called the
* "grade-school" algorithm used in multiplyToLen. If the numbers to be
* multiplied have length n, the "grade-school" algorithm has an
* asymptotic complexity of O(n^2). In contrast, 3-way Toom-Cook has a
* complexity of about O(n^1.465). It achieves this increased asymptotic
* performance by breaking each number into three parts and by doing 5
* multiplies instead of 9 when evaluating the product. Due to overhead
* (additions, shifts, and one division) in the Toom-Cook algorithm, it
* should only be used when both numbers are larger than a certain
* threshold (found experimentally). This threshold is generally larger
* than that for Karatsuba multiplication, so this algorithm is generally
* only used when numbers become significantly larger.
*
* The algorithm used is the "optimal" 3-way Toom-Cook algorithm outlined
* by Marco Bodrato.
*
* See: http://bodrato.it/toom-cook/
* http://bodrato.it/papers/#WAIFI2007
*
* "Towards Optimal Toom-Cook Multiplication for Univariate and
* Multivariate Polynomials in Characteristic 2 and 0." by Marco BODRATO;
* In C.Carlet and B.Sunar, Eds., "WAIFI'07 proceedings", p. 116-133,
* LNCS #4547. Springer, Madrid, Spain, June 21-22, 2007.
*
*/
private static BigInteger multiplyToomCook3(BigInteger a, BigInteger b) {
int alen = a.mag.length;
int blen = b.mag.length;
int largest = Math.max(alen, blen);
// k is the size (in ints) of the lower-order slices.
int k = (largest+2)/3; // Equal to ceil(largest/3)
// r is the size (in ints) of the highest-order slice.
int r = largest - 2*k;
// Obtain slices of the numbers. a2 and b2 are the most significant
// bits of the numbers a and b, and a0 and b0 the least significant.
BigInteger a0, a1, a2, b0, b1, b2;
a2 = a.getToomSlice(k, r, 0, largest);
a1 = a.getToomSlice(k, r, 1, largest);
a0 = a.getToomSlice(k, r, 2, largest);
b2 = b.getToomSlice(k, r, 0, largest);
b1 = b.getToomSlice(k, r, 1, largest);
b0 = b.getToomSlice(k, r, 2, largest);
BigInteger v0, v1, v2, vm1, vinf, t1, t2, tm1, da1, db1;
v0 = a0.multiply(b0);
da1 = a2.add(a0);
db1 = b2.add(b0);
vm1 = da1.subtract(a1).multiply(db1.subtract(b1));
da1 = da1.add(a1);
db1 = db1.add(b1);
v1 = da1.multiply(db1);
v2 = da1.add(a2).shiftLeft(1).subtract(a0).multiply(
db1.add(b2).shiftLeft(1).subtract(b0));
vinf = a2.multiply(b2);
// The algorithm requires two divisions by 2 and one by 3.
// All divisions are known to be exact, that is, they do not produce
// remainders, and all results are positive. The divisions by 2 are
// implemented as right shifts which are relatively efficient, leaving
// only an exact division by 3, which is done by a specialized
// linear-time algorithm.
t2 = v2.subtract(vm1).exactDivideBy3();
tm1 = v1.subtract(vm1).shiftRight(1);
t1 = v1.subtract(v0);
t2 = t2.subtract(t1).shiftRight(1);
t1 = t1.subtract(tm1).subtract(vinf);
t2 = t2.subtract(vinf.shiftLeft(1));
tm1 = tm1.subtract(t2);
// Number of bits to shift left.
int ss = k*32;
BigInteger result = vinf.shiftLeft(ss).add(t2).shiftLeft(ss).add(t1).shiftLeft(ss).add(tm1).shiftLeft(ss).add(v0);
if (a.signum != b.signum) {
return result.negate();
} else {
return result;
}
}
/**
* Returns a slice of a BigInteger for use in Toom-Cook multiplication.
*
* @param lowerSize The size of the lower-order bit slices.
* @param upperSize The size of the higher-order bit slices.
* @param slice The index of which slice is requested, which must be a
* number from 0 to size-1. Slice 0 is the highest-order bits, and slice
* size-1 are the lowest-order bits. Slice 0 may be of different size than
* the other slices.
* @param fullsize The size of the larger integer array, used to align
* slices to the appropriate position when multiplying different-sized
* numbers.
*/
private BigInteger getToomSlice(int lowerSize, int upperSize, int slice,
int fullsize) {
int start, end, sliceSize, len, offset;
len = mag.length;
offset = fullsize - len;
if (slice == 0) {
start = 0 - offset;
end = upperSize - 1 - offset;
} else {
start = upperSize + (slice-1)*lowerSize - offset;
end = start + lowerSize - 1;
}
if (start < 0) {
start = 0;
}
if (end < 0) {
return ZERO;
}
sliceSize = (end-start) + 1;
if (sliceSize <= 0) {
return ZERO;
}
// While performing Toom-Cook, all slices are positive and
// the sign is adjusted when the final number is composed.
if (start == 0 && sliceSize >= len) {
return this.abs();
}
int intSlice[] = new int[sliceSize];
System.arraycopy(mag, start, intSlice, 0, sliceSize);
return new BigInteger(trustedStripLeadingZeroInts(intSlice), 1);
}
感覺(jué)分析完身體要被掏空。。以后再說(shuō)吧。。
