超大整数计算
ava中long类型可以表示 -9,223,372,036,854,775,808（即-2^64）到9,223,372,036,854,775,807（即2^64-1）范围内的整数。有的时候我们希望能够处理在此范围之外的整数。为此，我们设计了一个BigInteger类。它可以支持大整数的加、减、乘操作。请根据提供的代码框架，完成整个程序。
> 注：
> 1) 请仔细阅读代码中的注释，并在标有// YOU FILL THIS IN 的位置添加你的代码。你可以添加自己的方法、变量，但是请不要修改已有的代码。
public class BigInteger {
// The sign of this integer - true for a positive number, and false
// otherwise
private boolean sign = true;
// digits[0] is the most significant digit of the integer, and
// the last element of this array is the least significant digit.
// For example, if we have a BigInteger of value 34, then
// digits[0] = 3 and digits[1] = 4.
private byte[] digits;
public BigInteger() {
this.digits = new byte[1];
this.digits[0] = 0;
}
public BigInteger(byte[] digits) {
this.digits = digits;
}
/**
* Initializes a <code>BigInteger</code> according to a string. The form of
* <code>numberStr</code> is a string consisting of all digits ranging from
* 0 to 9, following an OPTIONAL minus symbol (i.e., "-"). For example,
* "1234567891234567" and "-17788399934334388347734" are both valid.
*
* @param numberStr
* a number expressed as a string
*/
public BigInteger(String numberStr) {
// YOU FILL THIS IN
// Note: You should parse the string and initialize the "digits" array
// properly.
// You may also need to set the "sign" variable to a correct value.
}
/**
* Performs addition.
*
* @param another
* another <code>BigInteger</code> object
* @return this+another
*/
public BigInteger add(BigInteger another) {
// YOU FILL THIS IN
}
/**
* Performs addition.
*
* @param num
* an integer
* @return this+num
*/
public BigInteger add(int num) {
// YOU FILL THIS IN
}
/**
* Performs subtraction.
*
* @param another
* another <code>BigInteger</code> object
* @return this-another
*/
public BigInteger subtract(BigInteger another) {
// YOU FILL THIS IN
}
/**
* Performs subtraction.
*
* @param num
* an integer
* @return this-num
*/
public BigInteger subtract(int num) {
// YOU FILL THIS IN
}
/**
* Performs multiplication.
*
* @param another
* another <code>BigInteger</code> object
* @return this*another
*/
public BigInteger multiply(BigInteger another) {
// YOU FILL THIS IN
}
/**
* Performs multiplication.
*
* @param num
* an integer
* @return this*num
*/
public BigInteger multiply(int num) {
// YOU FILL THIS IN
}
public String toString() {
StringBuffer buf = new StringBuffer();
if (!sign) {
buf.append("-");
}
for (byte d : digits) {
buf.append(d);
}
return buf.toString();
}
public static void main(String[] args) {
BigInteger i1 = new BigInteger("999999999999999999");
BigInteger i2 = i1.add(1);
System.out.println(i2); // the output should be 1000000000000000000
BigInteger i3 = i2.multiply(i1);
System.out.println(i3); // expected: 999999999999999999000000000000000000
System.out.println(i3.subtract(-3)); // expected: 999999999999999999000000000000000003
}
}
急！！！
搜索更多相关的解决方案:
false
----------------解决方案--------------------------------------------------------
和楼主一起学习，这个是不是用到那个数的拆分啊？我数学有点要命
----------------解决方案--------------------------------------------------------
我不知道BigInteger类行不行，好像和你的类似。不过javaAPI里有这样的类。。。。个人感觉实现起来有点困难。。。
----------------解决方案--------------------------------------------------------
这是我用vc++写的 你自己看看吧改一下就可以啦
----------------解决方案--------------------------------------------------------
做了一个方案，有什么不到之处，还望指出。。。
程序代码：
public class Integer_BIG implements Cloneable {
// The sign of this integer - true for a positive number, and false for the negitive number
// otherwise
private boolean sign = true;
// digits[0] is the most significant digit of the integer, and
// the last element of this array is the least significant digit.
// For example, if we have a BigInteger of value 34, then
// digits[0] = 3 and digits[1] = 4.
//digit是从低位到高位的十进制数字数组
private byte[] digits;
private int digits_count;
/**
* Initializes a <code>BigInteger</code> according to a string. The form of
* <code>numberStr</code> is a string consisting of all digits ranging from
* 0 to 9, following an OPTIONAL minus symbol (i.e., "-"). For example,
* "1234567891234567" and "-17788399934334388347734" are both valid.
*
* @param numberStr
* a number expressed as a string
*/
public Integer_BIG(String numberStr){
// YOU FILL THIS IN
// Note: You should parse the string and initialize the "digits" array
// properly.
// You may also need to set the "sign" variable to a correct value.
int position = 0;
if(numberStr.startsWith("-")){
this.sign = false;
position = 1;
}
String tmp = numberStr.substring(position);
digits = new byte[tmp.length()];//初始化数组
this.digits_count = digits.length;
for(int count =0;count <tmp.length();count++){
byte res = (byte)(tmp.charAt(count)-48);
try{
if(res>=10){
throw new Exception("transformation failure..");
}else{
digits[digits.length-count-1]=res;
}
}catch(Exception e){
e.printStackTrace();
}
}
}
public Integer_BIG() {
this.digits = new byte[1];
this.digits[0] = 0;
}
public Integer_BIG(byte[] digits) {
this.digits = digits;
this.digits_count = digits.length;
}
public Integer_BIG(int num){
this(Integer.toString(num,10));
}
/**
* Performs addition.
*分解成求符号和数值两部分;
*实现过程原理和代数相同：
*同号相加，符号与任意一个数相同
*异号相当于减法，符号与绝对值大的相同；
* @param another
* another <code>BigInteger</code> object
* @return this+another
* @throws Exception
*/
public Integer_BIG add(Integer_BIG another){
// YOU FILL THIS IN
Integer_BIG result = null;
try{
result = (Integer_BIG)this.clone();
}catch(CloneNotSupportedException e){
e.printStackTrace();
}
if(!(this.sign ^ another.sign)){
result = this.abs()._add_(another.abs());
result.sign = this.sign;
}else{
Integer_BIG max =this._compare(another) >= 0? this:another;
Integer_BIG min =this._compare(another) >= 0? another:this;
result = _substrate_(max.abs(),min.abs());
result.sign = this.abs()._compare(another.abs()) >= 0? this.sign:another.sign;
}
return result;
}
/**
* Performs subtraction.
*分解成求符号和数值两部分;
* @param another
* another <code>BigInteger</code> object
* @return this-another
*/
public Integer_BIG subtract(Integer_BIG another){
// YOU FILL THIS IN
Integer_BIG result= null;
try{
result=(Integer_BIG)this.clone();
}catch(CloneNotSupportedException e){
e.printStackTrace();
}
if(this.sign ^ another.sign){
result = this.abs()._add_(another.abs());
result.sign = this.sign;
}else{
Integer_BIG max =this._compare(another) >= 0? this:another;
Integer_BIG min = this._compare(another) >= 0? another:this;
result = _substrate_(max,min);
result.sign = this.abs()._compare(another.abs()) >= 0? this.sign:another.sign;
}
return result;
}
/**
* Performs multiplication.
*将一个数的乘法看成从低位到高位以一个0~9的数相乘，然后乘以它的权值，在相加求和
* @param another
* another <code>BigInteger</code> object
* @return this*another
*/
public Integer_BIG multiply(Integer_BIG another) {
// YOU FILL THIS IN
Integer_BIG result = null;
result = new Integer_BIG(0);
for(int i = 0;i<another.digits_count;i++){
Integer_BIG tmp = this._multiply(another.digits[i]);
tmp = _move_bit(tmp,i);
result=result.add(tmp);
}
if(this.sign ^ another.sign){
result.sign = false;
}else{
result.sign = true;
}
return result;
}
public String toString() {
StringBuffer buf = new StringBuffer();
if (!sign) {
buf.append("-");
}
int icount = this.digits.length-1;
boolean headzero = true;
while(icount >=0){
if(this.digits[icount] != 0 && headzero){
headzero = false;
}
if(!headzero){
buf.append(this.digits[icount]);
}
icount -- ;
}
return buf.toString();
}
/**
* 取绝对值
*/
private Integer_BIG abs(){
Integer_BIG result = null;
try{
result = (Integer_BIG) this.clone();
}catch(CloneNotSupportedException e){
e.printStackTrace();
}
result.sign = true;
return result;
}
/**
*从低到高相加
*加法分解
* @param another
*/
private Integer_BIG _add_(Integer_BIG another){
Integer_BIG maxLong = this.digits_count>= another.digits_count? this:another;
Integer_BIG minLong = this.digits_count >= another.digits_count? another:this;
byte result[] = new byte[maxLong.digits_count+1];
byte tmp [] = new byte[maxLong.digits_count];
for(int icount = 0;icount< tmp.length;icount++){
result[icount] = 0;
tmp[icount] = 0;
}
byte add_in_bit = 0;
System.arraycopy(minLong.digits, 0, tmp,0, minLong.digits_count);
for(int icount = 0;icount< tmp.length;icount++){
byte re = (byte)(maxLong.digits[icount]+tmp[icount]+add_in_bit);
add_in_bit = (byte) (re /10);
result[icount] = (byte) (re % 10);
}
result[result.length-1] = add_in_bit;
return new Integer_BIG(result);
}
/**
* 大-小
* 减法的分解
* 从低位到高位
* @param another
*/
private Integer_BIG _substrate_( Integer_BIG max,Integer_BIG min){
Integer_BIG maxLong = max.digits_count>= min.digits_count? max:min;
//Integer_BIG minLong = max.digits_count >= min.digits_count? min:max;
byte result[] = new byte[maxLong.digits_count];
byte tmp [] = new byte[maxLong.digits_count];
for(int icount = 0;icount< tmp.length;icount++){
result[icount] = 0;
tmp[icount] = 0;
}
byte add_in_bit = 0;
System.arraycopy(min.digits, 0, tmp,0, min.digits_count);
for(int icount = 0;icount< tmp.length;icount++){
byte re = (byte)(max.digits[icount]-tmp[icount]-add_in_bit);
if(re < 0){
result[icount] = (byte)(10+re);
add_in_bit = 1;
}else{
result[icount] = re;
add_in_bit = 0;
}
}
return new Integer_BIG(result);
}
/**
* 比较数字大小
*/
private int _compare(Integer_BIG another){
int return_int = 1;
if(this.digits_count != another.digits_count){
return_int = this.digits_count>another.digits_count?1:-1;
}else{
int icount = this.digits_count-1;
while(icount >= 0){
if(this.digits[icount] > another.digits[icount]){
return_int = 1;
break;
}
if(this.digits[icount] < another.digits[icount]){
return_int = -1;
break;
}
if(this.digits[icount] == another.digits[icount]){
icount--;
}
}
}
return return_int;
}
/**
* 数字移位，相当于乘以10
* @param another
* @param count
* @return
*/
private Integer_BIG _move_bit(Integer_BIG another,int count){
byte[] tmp = new byte[another.digits_count+count];
for(int i =0 ;i < tmp.length;i++){
tmp[i] = 0;
}
System.arraycopy(another.digits, 0, tmp, count, another.digits_count);
another.digits = tmp;
another.digits_count +=count;
return another;
}
/**
* 乘法的分解运算
* @param num
* @return
*/
private Integer_BIG _multiply(int num){
byte add_in_bit = 0;
byte[] resultArray = new byte[this.digits_count+1];
for(int i = 0;i < resultArray.length;i++){
resultArray[i] = 0;
}
for(int icount = 0;icount< this.digits_count;icount++){
byte tmp = (byte)(this.digits[icount]* num +add_in_bit);
resultArray[icount] = (byte) (tmp % 10);
add_in_bit = (byte)(tmp / 10);
}
resultArray[resultArray.length-1] = add_in_bit;
return new Integer_BIG(resultArray);
}
/**
* 实现类的复制
*/
public Object clone() throws CloneNotSupportedException{
Integer_BIG result = null;
try {
result =(Integer_BIG)this.getClass().newInstance();
} catch (InstantiationException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IllegalAccessException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
result.digits = new byte[this.digits_count];
System.arraycopy(this.digits, 0, result.digits, 0, this.digits_count);
result.digits_count=this.digits_count ;
result.sign = this.sign;
return result;
}
public static void main(String args[]){
Integer_BIG big1 = new Integer_BIG("-90");
System.out.println(big1.toString());
Integer_BIG big2 = new Integer_BIG("100");
System.out.println(big2.toString());
Integer_BIG result= null;
result = big1.add(big2);
System.out.println(result.toString());
result = big1.subtract(big2);
System.out.println(result.toString());
result = big1.multiply(big2);
System.out.print(result.toString());
}
}
// The sign of this integer - true for a positive number, and false for the negitive number
// otherwise
private boolean sign = true;
// digits[0] is the most significant digit of the integer, and
// the last element of this array is the least significant digit.
// For example, if we have a BigInteger of value 34, then
// digits[0] = 3 and digits[1] = 4.
//digit是从低位到高位的十进制数字数组
private byte[] digits;
private int digits_count;
/**
* Initializes a <code>BigInteger</code> according to a string. The form of
* <code>numberStr</code> is a string consisting of all digits ranging from
* 0 to 9, following an OPTIONAL minus symbol (i.e., "-"). For example,
* "1234567891234567" and "-17788399934334388347734" are both valid.
*
* @param numberStr
* a number expressed as a string
*/
public Integer_BIG(String numberStr){
// YOU FILL THIS IN
// Note: You should parse the string and initialize the "digits" array
// properly.
// You may also need to set the "sign" variable to a correct value.
int position = 0;
if(numberStr.startsWith("-")){
this.sign = false;
position = 1;
}
String tmp = numberStr.substring(position);
digits = new byte[tmp.length()];//初始化数组
this.digits_count = digits.length;
for(int count =0;count <tmp.length();count++){
byte res = (byte)(tmp.charAt(count)-48);
try{
if(res>=10){
throw new Exception("transformation failure..");
}else{
digits[digits.length-count-1]=res;
}
}catch(Exception e){
e.printStackTrace();
}
}
}
public Integer_BIG() {
this.digits = new byte[1];
this.digits[0] = 0;
}
public Integer_BIG(byte[] digits) {
this.digits = digits;
this.digits_count = digits.length;
}
public Integer_BIG(int num){
this(Integer.toString(num,10));
}
/**
* Performs addition.
*分解成求符号和数值两部分;
*实现过程原理和代数相同：
*同号相加，符号与任意一个数相同
*异号相当于减法，符号与绝对值大的相同；
* @param another
* another <code>BigInteger</code> object
* @return this+another
* @throws Exception
*/
public Integer_BIG add(Integer_BIG another){
// YOU FILL THIS IN
Integer_BIG result = null;
try{
result = (Integer_BIG)this.clone();
}catch(CloneNotSupportedException e){
e.printStackTrace();
}
if(!(this.sign ^ another.sign)){
result = this.abs()._add_(another.abs());
result.sign = this.sign;
}else{
Integer_BIG max =this._compare(another) >= 0? this:another;
Integer_BIG min =this._compare(another) >= 0? another:this;
result = _substrate_(max.abs(),min.abs());
result.sign = this.abs()._compare(another.abs()) >= 0? this.sign:another.sign;
}
return result;
}
/**
* Performs subtraction.
*分解成求符号和数值两部分;
* @param another
* another <code>BigInteger</code> object
* @return this-another
*/
public Integer_BIG subtract(Integer_BIG another){
// YOU FILL THIS IN
Integer_BIG result= null;
try{
result=(Integer_BIG)this.clone();
}catch(CloneNotSupportedException e){
e.printStackTrace();
}
if(this.sign ^ another.sign){
result = this.abs()._add_(another.abs());
result.sign = this.sign;
}else{
Integer_BIG max =this._compare(another) >= 0? this:another;
Integer_BIG min = this._compare(another) >= 0? another:this;
result = _substrate_(max,min);
result.sign = this.abs()._compare(another.abs()) >= 0? this.sign:another.sign;
}
return result;
}
/**
* Performs multiplication.
*将一个数的乘法看成从低位到高位以一个0~9的数相乘，然后乘以它的权值，在相加求和
* @param another
* another <code>BigInteger</code> object
* @return this*another
*/
public Integer_BIG multiply(Integer_BIG another) {
// YOU FILL THIS IN
Integer_BIG result = null;
result = new Integer_BIG(0);
for(int i = 0;i<another.digits_count;i++){
Integer_BIG tmp = this._multiply(another.digits[i]);
tmp = _move_bit(tmp,i);
result=result.add(tmp);
}
if(this.sign ^ another.sign){
result.sign = false;
}else{
result.sign = true;
}
return result;
}
public String toString() {
StringBuffer buf = new StringBuffer();
if (!sign) {
buf.append("-");
}
int icount = this.digits.length-1;
boolean headzero = true;
while(icount >=0){
if(this.digits[icount] != 0 && headzero){
headzero = false;
}
if(!headzero){
buf.append(this.digits[icount]);
}
icount -- ;
}
return buf.toString();
}
/**
* 取绝对值
*/
private Integer_BIG abs(){
Integer_BIG result = null;
try{
result = (Integer_BIG) this.clone();
}catch(CloneNotSupportedException e){
e.printStackTrace();
}
result.sign = true;
return result;
}
/**
*从低到高相加
*加法分解
* @param another
*/
private Integer_BIG _add_(Integer_BIG another){
Integer_BIG maxLong = this.digits_count>= another.digits_count? this:another;
Integer_BIG minLong = this.digits_count >= another.digits_count? another:this;
byte result[] = new byte[maxLong.digits_count+1];
byte tmp [] = new byte[maxLong.digits_count];
for(int icount = 0;icount< tmp.length;icount++){
result[icount] = 0;
tmp[icount] = 0;
}
byte add_in_bit = 0;
System.arraycopy(minLong.digits, 0, tmp,0, minLong.digits_count);
for(int icount = 0;icount< tmp.length;icount++){
byte re = (byte)(maxLong.digits[icount]+tmp[icount]+add_in_bit);
add_in_bit = (byte) (re /10);
result[icount] = (byte) (re % 10);
}
result[result.length-1] = add_in_bit;
return new Integer_BIG(result);
}
/**
* 大-小
* 减法的分解
* 从低位到高位
* @param another
*/
private Integer_BIG _substrate_( Integer_BIG max,Integer_BIG min){
Integer_BIG maxLong = max.digits_count>= min.digits_count? max:min;
//Integer_BIG minLong = max.digits_count >= min.digits_count? min:max;
byte result[] = new byte[maxLong.digits_count];
byte tmp [] = new byte[maxLong.digits_count];
for(int icount = 0;icount< tmp.length;icount++){
result[icount] = 0;
tmp[icount] = 0;
}
byte add_in_bit = 0;
System.arraycopy(min.digits, 0, tmp,0, min.digits_count);
for(int icount = 0;icount< tmp.length;icount++){
byte re = (byte)(max.digits[icount]-tmp[icount]-add_in_bit);
if(re < 0){
result[icount] = (byte)(10+re);
add_in_bit = 1;
}else{
result[icount] = re;
add_in_bit = 0;
}
}
return new Integer_BIG(result);
}
/**
* 比较数字大小
*/
private int _compare(Integer_BIG another){
int return_int = 1;
if(this.digits_count != another.digits_count){
return_int = this.digits_count>another.digits_count?1:-1;
}else{
int icount = this.digits_count-1;
while(icount >= 0){
if(this.digits[icount] > another.digits[icount]){
return_int = 1;
break;
}
if(this.digits[icount] < another.digits[icount]){
return_int = -1;
break;
}
if(this.digits[icount] == another.digits[icount]){
icount--;
}
}
}
return return_int;
}
/**
* 数字移位，相当于乘以10
* @param another
* @param count
* @return
*/
private Integer_BIG _move_bit(Integer_BIG another,int count){
byte[] tmp = new byte[another.digits_count+count];
for(int i =0 ;i < tmp.length;i++){
tmp[i] = 0;
}
System.arraycopy(another.digits, 0, tmp, count, another.digits_count);
another.digits = tmp;
another.digits_count +=count;
return another;
}
/**
* 乘法的分解运算
* @param num
* @return
*/
private Integer_BIG _multiply(int num){
byte add_in_bit = 0;
byte[] resultArray = new byte[this.digits_count+1];
for(int i = 0;i < resultArray.length;i++){
resultArray[i] = 0;
}
for(int icount = 0;icount< this.digits_count;icount++){
byte tmp = (byte)(this.digits[icount]* num +add_in_bit);
resultArray[icount] = (byte) (tmp % 10);
add_in_bit = (byte)(tmp / 10);
}
resultArray[resultArray.length-1] = add_in_bit;
return new Integer_BIG(resultArray);
}
/**
* 实现类的复制
*/
public Object clone() throws CloneNotSupportedException{
Integer_BIG result = null;
try {
result =(Integer_BIG)this.getClass().newInstance();
} catch (InstantiationException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IllegalAccessException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
result.digits = new byte[this.digits_count];
System.arraycopy(this.digits, 0, result.digits, 0, this.digits_count);
result.digits_count=this.digits_count ;
result.sign = this.sign;
return result;
}
public static void main(String args[]){
Integer_BIG big1 = new Integer_BIG("-90");
System.out.println(big1.toString());
Integer_BIG big2 = new Integer_BIG("100");
System.out.println(big2.toString());
Integer_BIG result= null;
result = big1.add(big2);
System.out.println(result.toString());
result = big1.subtract(big2);
System.out.println(result.toString());
result = big1.multiply(big2);
System.out.print(result.toString());
}
}
----------------解决方案--------------------------------------------------------