先来掌握一些常用的位运算操作：
等式：-n = ~(n - 1) = ~n + 1（-n等于其各位取反加1）；
获取整数n的二进制中最后一个1：-n&n 或(~n+1)&n或 ~(n - 1)&n；
如：n = 010100，则 -n = 101100, n&(n - 1)=000100；去掉整数n的二进制中最后一个1：n&(n - 1)。如：n = 010100, n -1 = 010011, n&(n - 1) = 010000。
加法 a + b
思考：
a^b可得到对应位没有进位时的和，如果该位进位了，其值为0，该位没有进位，其值为a+b对应位的结果（不考虑低位进位）
a&b可得到各位产生的进位值，如果该位没有进位，其值为0，该位进位了，其值为1
(a&b)<<1正好代表a+b有进位的位进位后的结果
如果使用a^b+(a&b)<<1来表示a+b的值有问题的地方在于不能保证这两个子表达式相加过程不产生进位
所以迭代也好，递归也好，一定要让(a&b)也就是进位的情况不存在，直接可以用a^b表示出不产生进位的加法
注意在多次循环中，a,b的值也要相应变化，当然数据溢出的问题本篇博客就不考虑了
解答如下：
用 ^，&和<<即可实现，，a&b可得到各位产生的进位值。
如：a=010010, b=100111，计算过程如下：
- 每轮首先判断b是否为0，为0则结束，把a的值作为结果返回
- 第一轮：通过(a&b)=000010 得出a+b结果中需要进位的位置
(a&b)<<1 将进位的值全体左移一位后，表示进位部分进位后的值
a^b=110101，表示a+b不进位部分相加的结果
由于进位大于0，把a^b的值赋给a，此时a=110101,(a&b)<<1的值赋给b，此时b=000100；
进入下一轮中，新的a+b=老的a+b的值=循环下去b值为0时a的值（此时代表不产生进位） - 第二轮：a^b=110001，(a&b)<<1=001000（进位）。进位大于0，进入下一轮：a=110001,b=001000；
- 第三轮：a^b=111001，(a&b)<<1=000000（进位）。进位等于0，终止；
结果为：111001。
非递归
int add1(int a, int b)
{
int carry; // 进位
while (b!=0)
{
carry = (a & b) << 1; // a & b取各位的进位，进位作用于对应位的高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);
}
// 简化版
// 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。把减法转化为加法即可。
int sub(int a, int b)
{
return add(a, add(~b, 1));
}
乘法：a*b
基础版：观察如下
1011
* 1010
--------
10110 (1011<<1,相当于乘以0010)
1011000 (1011<<3,相当于乘以1000)
--------
1101110
可以看到，二进制乘法的原理是：从乘数的低位到高位，遇到1并且这个1在乘数的右起第i（i从0开始数）位，那么就把被乘数左移i位得到 temp_i 。直到乘数中的1遍历完后，把根据各位1而得到的被乘数的左移值们 temp_i 相加起来即得乘法结果。那么根据这个原理，可以得到实现代码：这里要点为：用i记录当前遍历的乘数位,当前位为1则被乘数左移i位并加到和中，同时i++处理下一位；为0则乘数右移，i++，处理下一位......直到乘数==0说明乘数中的1遍历完了。此时把和返回即可。
需要注意的是，补码乘法符号位也是参与运算的，具体参见深入理解计算机系统第二章内容（无符号乘法和补码乘法的位级等价性）
// 值得注意的是网上的程序片段中使用的>>代表算术右移，而在考虑到补码
// 符号位为1的可能性的时候必须采用逻辑右移>>>，不然会死循环
int multi(int a,int b){
int i=0;
int res=0;
while(b!=0){//乘数为0则结束
//处理乘数当前位
if((b&1)==1){
res+=(a<<i);
b=b>>>1;
++i;//i记录当前位是第几位
}else{
b=b>>>1;
++i;
}
}
return res;
}
进阶思考：在基础版之上，如果遇到两个大数相乘，采用什么方式呢？
采用带有分治法思想的乘法来计算
image.png
image.png
那么我们看一下java8里BigInteger类如何实现的
/**
* 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;
}
}
在此之上还有更低复杂度的算法
/**
* 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);
}
感觉分析完身体要被掏空。。以后再说吧。。
