快速幂和快速乘

快速幂運算

import java.util.*;

public class Main {
	public static void main(String[] args) {
		// 用快速幂運算計算2的30次方花費的時間
		long time = System.currentTimeMillis();
		System.out.println(fast_pow(2, 30));
		System.out.println(System.currentTimeMillis() - time);
		System.out.println();

		// 用math的幂運算2的30次方花費的時間
		time = System.currentTimeMillis();
		System.out.println(Math.pow(2, 30));
		System.out.println(System.currentTimeMillis() - time);
	}

	// 計算x的n次方的快速幂運算
	// 将n轉化為2進制表示，若末位為1，則将res乘以相應的值
	// 若n為22，則二進制為10110，需要計算出x的2，4，16次方，當n右移到相應位置時，直接将res乘以相應的x即可。
	static long fast_pow(int x, int n) {
		long res = 1;
		while (n > 0) {
			// n為奇數
			if ((n & 1) == 1) {
				res *= x;
			}
			// n右移一位
			n >>= 1;
			// x變為x的平方
			x *= x;
		}
		return res;
	}
}

           

快速乘運算

import java.util.*;

public class Main {
	public static void main(String[] args) {
		System.out.println(fast_mul(2, 3));
	}

	// 比如5*3相當于5*二進制的11，相當于5*二進制的10+5*二進制的1，如下代碼即利用了該思路
	static long fast_mul(long a, long b) {
		long res = 0;
		while (b != 0) {
			if ((b & 1) == 1) {
				res += a;
			}
			a *= 2;
			b >>= 1;
		}
		return res;
	}
}