（ 其他算法与技巧 ）【 JAVA大数 】

大数 】"/>

（ 其他算法与技巧 ）【 JAVA大数 】

（ 算法树之其他算法与技巧 ）【 JAVA大数 】

在 Java 中，有许多数字处理的类，比如 Integer类，但是Integer类有一定的局限性。

我们都知道 Integer 是 Int 的包装类，int 的最大值为 2^31-1。若希望描述更大的整数数据时，使用Integer 数据类型就无法实现了，所以Java中提供了BigInteger 类。

BigInteger类型的数字范围较Integer，Long类型的数字范围要大得多，它支持任意精度的整数，也就是说在运算中 BigInteger 类型可以准确地表示任何大小的整数值而不会丢失任何信息。

下面，让我们一起来学习一下BigInteger的常用方法：

正文：
读入方法
nextBigInteger()：控制台读入一个BigInteger型数据，类似于int型的nextInt()；
 

	//读入方法：nextBigInteger()@Testpublic void test5() {Scanner scan = new Scanner(System.in);				// 读入int n = scan.nextInt(); 							// 读入一个int;BigInteger m = scan.nextBigInteger();				// 读入一个BigInteger;while(scan.hasNext()){	System.out.print("scan.hasNext()=" + scan.hasNext());}}

构造方法

默认为十进制，也是我们最常用的，同时也支持自定义进制类型（已存在的）；

	//进制转换@Testpublic void testScale() {//在构造将函数时，把radix进制的字符串转化为BigIntegerString str = "1011100111";int radix = 2;BigInteger interNum1 = new BigInteger(str,radix);	//743//我们通常不写，则是默认成10进制转换，如下：BigInteger interNum2 = new BigInteger(str);			//1011100111}

基本运算

返回值为BigInteger类型：add()，subtract()，multiply()，divide()，mod()，remainder()，pow()，abs()，negate()；

	//基本运算:add(),subtract(),multiply(),divide(),mod(),remainder(),pow(),abs(),negate()@Testpublic void testBasic() {BigInteger a = new BigInteger("13");BigInteger b = new BigInteger("4");int n = 3;//1.加BigInteger bigNum1 = a.add(b);			//17//2.减BigInteger bigNum2 = a.subtract(b);		//9//3.乘BigInteger bigNum3 = a.multiply(b);		//52//4.除BigInteger bigNum4 = a.divide(b);		//3//5.取模(需 b > 0，否则出现异常：ArithmeticException("BigInteger: modulus not positive"))BigInteger bigNum5 = a.mod(b);			//1//6.求余BigInteger bigNum6 = a.remainder(b);	//1//7.平方(需 n >= 0，否则出现异常：ArithmeticException("Negative exponent"))BigInteger bigNum7 = a.pow(n);			//2197//8.取绝对值BigInteger bigNum8 = a.abs();			//13//9.取相反数BigInteger bigNum9 = a.negate();		//-13}

比较大小

compareTo()返回一个int型数据：1 大于； 0 等于； -1 小于；
max()，min()：分别返回大的（小的）那个BigInteger数据；

	//比较大小:compareTo(),max(),min()@Testpublic void testCompare() {BigInteger bigNum1 = new BigInteger("52");BigInteger bigNum2 = new BigInteger("27");//1pareTo()：返回一个int型数据（1 大于； 0 等于； -1 小于）int num = bigNum1pareTo(bigNum2);			//1//2.max()：直接返回大的那个数，类型为BigInteger//	原理：return (compareTo(val) > 0 ? this : val);BigInteger compareMax = bigNum1.max(bigNum2);	//52//3.min()：直接返回小的那个数，类型为BigInteger//	原理：return (compareTo(val) < 0 ? this : val);BigInteger compareMin = bigNum1.min(bigNum2);	//27}

常量

ZERO，ONE，TEN 返回值为BigInteger类型：有朋友提到的-1，2，源码注释里面已表明不再输出(Not exported.)；

	//常量(返回BigInteger类型)//有朋友提到的-1和2，源码注释里面已表明不再输出(Not exported.)@Testpublic void testFinalNum() {//0BigInteger zero = BigInteger.ZERO;//1BigInteger one = BigInteger.ONE;//10BigInteger ten = BigInteger.TEN;}

类型转换

将BigInteger数据转换成基本数据类型，还可以转换成radix进制的字符串形式；

	//类型转换(返回类型如下)@Testpublic void testToAnother() {BigInteger bigNum = new BigInteger("52");int radix = 2;//1.转换为bigNum的二进制补码形式byte[] num1 = bigNum.toByteArray();//2.转换为bigNum的十进制字符串形式String num2 = bigNum.toString();		//52//3.转换为bigNum的radix进制字符串形式String num3 = bigNum.toString(radix);	//110100//4.将bigNum转换为intint num4 = bigNum.intValue();//5.将bigNum转换为longlong num5 = bigNum.longValue();//6.将bigNum转换为floatfloat num6 = bigNum.floatValue();//7.将bigNum转换为doubledouble num7 = bigNum.doubleValue();}

二进制运算

返回值为BigInteger类型，此类方法不常用，有备无患；

	//二进制运算(返回类型都为BigInteger，不常用，但有备无患)@Testpublic void testBinaryOperation() {BigInteger a = new BigInteger("13");BigInteger b = new BigInteger("2");int n = 1;//1.与：a&bBigInteger bigNum1 = a.and(b);			//0//2.或：a|bBigInteger bigNum2 = a.or(b);			//15//3.异或：a^bBigInteger bigNum3 = a.xor(b);			//15//4.取反：~aBigInteger bigNum4 = a.not();			//-14//5.左移n位： (a << n)BigInteger bigNum5 = a.shiftLeft(n);	//26//6.右移n位： (a >> n)BigInteger bigNum6 = a.shiftRight(n);	//6}

权限控制

setBit()，testBit()：可用于菜单的权限控制，非常好用，原理如下：

	//权限控制：setBit(),testBit()@Testpublic void testSetAndTest() {//1.封装数据(setBit的值需 >= 0，否则出现异常：ArithmeticException("Negative bit address"))BigInteger permission = new BigInteger("0");BigInteger numBig = permission.setBit(2);numBig = numBig.setBit(5);numBig = numBig.setBit(13);numBig = numBig.setBit(66);System.out.println("原理：" + numBig);	// 原理：73786976294838214692 = 2^2+2^5+2^13+2^66 次方的和；// 看！！即使这么大的数也不会溢出，而int最大值只有2147483647；//2.取值验证（返回Boolean型）boolean flag1 = numBig.testBit(2);		//trueboolean flag2 = numBig.testBit(5);		//trueboolean flag3 = numBig.testBit(13);		//trueboolean flag4 = numBig.testBit(66);		//trueboolean flag5 = numBig.testBit(27);		//false}

源码分析

setBit()：将set进去变量作为二进制数，计算它们的和，并以十进制显示；
testBit()：与setBit()相反，验证this的二进制组成元素中是否包含传入的变量；

	//权限控制源码分析：//1.setBit()原理：计算this与2的n次方的和public BigInteger setBit(int n) {if (n < 0)throw new ArithmeticException("Negative bit address");int intNum = n >>> 5;int[] result = new int[Math.max(intLength(), intNum+2)];for (int i=0; i < result.length; i++)result[result.length-i-1] = getInt(i);result[result.length-intNum-1] |= (1 << (n & 31));return valueOf(result);}//2.testBit()原理：计算this的值中是否包含2的n次方public boolean testBit(int n) {if (n < 0)throw new ArithmeticException("Negative bit address");return (getInt(n >>> 5) & (1 << (n & 31))) != 0;}

小结
BigInteger也是不可变的，在进行每一步运算时，都会产生一个新的对象。都会产生一个新的对象。发生异常算术条件时，会抛出ArithmeticException异常。例如，一个整数除以“0”，会抛出一个这个类的实例；
假设计算一个int数据平方与另一个大小的问题，很可能会内存溢出。除了使用二分法外，利用BigInteger的compareTo方法也是一个好选择，简单易懂，而且不需要算法支持；
本章作为笔记使用，内容比较全面，但常用的只有：构造函数，基本运算以及compareTo()，intValue()，setBit()，testBit()方法；
setBit()和testBit()方法可用于菜单的权限控制，小编在开发中多次尝试，非常好用。很多微博有相关介绍，在这里我不做项目演示了。

例题：I - Intergalactic Bidding  转自：.html

题意：n个人竞价拍卖宝石，宝石价值s块钱，求哪些人出的钱加起来刚好是s

题解：

根据题意，注意当前人出的钱至少是全场人出的最高价钱的两倍（关键条件）

那我们就可以对每个人出的钱排序,从大的开始取，假设当前为x，如果s>=x，

一定要取x，因为如果不取x我们就得取比x小的那些数，但是就算把比x小的

数全加起来都不比x大，所以x必须被取走！

举例：2 5 13 28 50，s=57，发现50小于等于57，取之，s=7,然后28>s，

不取，然后13也不能取，最后把5和2取完，s=0

因为钱数很大，这里用JAVA里的BigInteger类处理。

一开始想着用结构体存人名字和钱，然后重载运算符再排序，

结果发现JAVA不支持重载运算符。。。

然后发现每个人的钱数肯定不同，便祭出了map；

后来又发现还他妈不支持biginteger排序。。。

好吧，大不了我手写个排序咯

5 63
Vader 3
Voldemort 7
BorgQueen 20
Terminator 40
Megatron 101

3
BorgQueen
Terminator
Vader

4 1112
Blorg 10
Glorg 1000
Klorg 1
Zlorg 100

0

代码：

package paticipant;import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();BigInteger s = in.nextBigInteger();Map<BigInteger, String> mp = new HashMap<BigInteger, String>();BigInteger[] a = new BigInteger[1005];for ( int i=0; i<n; i++ ) {String name = in.next();a[i] = in.nextBigInteger();mp.put(a[i], name);}for ( int i=0; i<n; i++ ) {for ( int j=i+1; j<n; j++ ) {if ( a[j]pareTo(a[i])==1 ) {BigInteger t = a[i];a[i] = a[j];a[j] = t;}}}String[] ans = new String[1005];int cnt = 0;for ( int i=0; i<n; i++ ) {if ( spareTo(a[i])>=0 ) {s = s.subtract(a[i]);ans[cnt++] = mp.get(a[i]);}}if ( spareTo(BigInteger.ZERO)==0 ) {System.out.println(cnt);for ( int i=0; i<cnt; i++ ) System.out.println( ans[i] );}else System.out.println("0");in.close();}}