大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
- import java.math.BigInteger;
- /**
- * 超大整数加减乘除:
- * 题目要求:如果系统要使用超大整数(超过long的范围),请你设计一个数据结构来存储这种超大型数字以及设计一种算法来实现超大整数的加法运算
- * @author Jason Huang
- *
- */
- public class LargeInteger {
- // 第一位存储符号,第二位开始,从低位到高位存储数据,每个byte存储十进制数字两位,即该存储结构为100进制
- private byte[] data = null;
- private LargeInteger(byte[] data) {
- if (data == null) {
- throw new NumberFormatException();
- }
- this.data = copy(data, –1);
- }
- public LargeInteger(LargeInteger num) {
- this(num.data);
- }
- public LargeInteger(String exp) {
- // 转换成char array
- char[] chars = exp.toCharArray();
- // 获取第一个字母
- char chr = chars[0];
- // 获取左边第一个有效数字的位置
- int left = (chr == ‘-‘ || chr == ‘+’) ? 1 : 0;
- // 获取byte array的长度
- int length = (chars.length – left + 3) / 2;
- // 建立byte array
- data = new byte[length];
- // 存储正负符号
- data[0] = (byte) (chr == ‘-‘ ? 0x1 : 0x0);
- int index = 1;
- // 从低位到高位处理数字
- for (int i = chars.length – 1; i >= left;) {
- // 个位数
- int num1 = chars[i–] – ‘0’;
- // 十位数
- int num10 = i >= left ? chars[i–] – ‘0’ : 0;
- // 含有非法字符时抛出错误
- if (num1 < 0 || num1 > 9 || num10 < 0 || num10 > 9) {
- throw new NumberFormatException();
- }
- data[index++] = (byte) (num10 * 10 + num1);
- }
- }
- private static byte[] copy(byte[] bytes, int append) {
- if (bytes == null) {
- throw new NumberFormatException();
- }
- if (bytes.length <= 1) {
- return new byte[2];
- }
- //System.out.println(“copy1: ” + toString(bytes));
- int length = bytes.length;
- int right = length – 1;
- if (append >= 0) {
- length += append;
- } else {
- for (; right >= 2; right–) {
- if (bytes[right] > 0x0) {
- break;
- }
- }
- length = right + 1;
- }
- byte[] other = new byte[length];
- for (int i = 0; i <= right; i++) {
- other[i] = bytes[i];
- }
- if (isZero(other)) {
- other[0] = 0x0;
- }
- //System.out.println(“copy2: ” + toString(other));
- return other;
- }
- private static byte[] subarray(byte[] bytes, int beginIndex, int length) {
- if (bytes == null || bytes.length <= 1) {
- throw new NumberFormatException();
- }
- //System.out.println(“subarray: ” + toString(bytes));
- //System.out.println(“beginIndex: ” + beginIndex);
- //System.out.println(“length: ” + length);
- if (beginIndex < 0 || length < 1) {
- //System.out.println(“beginIndex: ” + beginIndex);
- //System.out.println(“length: ” + length);
- //System.out.println(“bytes.length: ” + bytes.length);
- throw new IndexOutOfBoundsException();
- }
- byte[] other = new byte[length];
- other[0] = bytes[0];
- for (int i = 1; i < length && i + beginIndex < bytes.length; i++) {
- //System.out.println(“i: ” + i);
- //System.out.println(“beginIndex: ” + beginIndex);
- //System.out.println(“length: ” + length);
- //System.out.println(“bytes.length: ” + bytes.length);
- other[i] = bytes[i + beginIndex];
- }
- //System.out.println(“other: ” + toString(other));
- return other;
- }
- private static byte[] shift(byte[] bytes, int n) {
- if (bytes == null || bytes.length <= 1) {
- throw new NumberFormatException();
- }
- byte[] other = new byte[bytes.length + n];
- other[0] = bytes[0];
- for (int i = 1; i < bytes.length; i++) {
- other[i + n] = bytes[i];
- }
- return other;
- }
- private static byte[] copy(int[] nums) {
- if (nums == null) {
- throw new NumberFormatException();
- }
- if (nums.length <= 1) {
- return new byte[2];
- }
- //System.out.println(“copy1: ” + toString(nums));
- byte[] other = new byte[nums.length];
- other[0] = (byte) nums[0];
- int over = 0;
- int num = 0;
- for (int i = 1; i < nums.length; i++) {
- over += nums[i];
- other[i] = (byte) (over % 100);
- over /= 100;
- }
- return copy(other, –1);
- }
- public int signum() {
- return compareTo(this.data, new byte[2]);
- }
- private static byte[] abs(byte[] bytes) {
- byte[] other = copy(bytes, –1);
- other[0] = 0x0;
- return other;
- }
- public static LargeInteger abs(LargeInteger num) {
- return new LargeInteger(abs(num.data));
- }
- public LargeInteger abs() {
- return new LargeInteger(abs(this.data));
- }
- private static byte[] negate(byte[] bytes) {
- byte[] other = copy(bytes, –1);
- other[0] ^= 0x1;
- return other;
- }
- public static LargeInteger negate(LargeInteger num) {
- return new LargeInteger(negate(num.data));
- }
- public LargeInteger negate() {
- return new LargeInteger(negate(this.data));
- }
- private static boolean isZero(byte[] bytes) {
- if (bytes == null) {
- throw new NumberFormatException();
- }
- for (int i = 1; i < bytes.length; i++) {
- if (bytes[i] != 0x0) {
- return false;
- }
- }
- return true;
- }
- private static int compareTo(byte[] bytes1, byte[] bytes2) {
- if (bytes1 == null || bytes2 == null) {
- throw new NumberFormatException();
- }
- if (isZero(bytes1) && isZero(bytes2)) {
- return 0;
- } else if (isZero(bytes1)) {
- return bytes2[0] == 0x1 ? 1 : –1;
- } else if (isZero(bytes2)) {
- return bytes1[0] == 0x1 ? –1 : 1;
- } else if (bytes1[0] > bytes2[0]) {
- return –1;
- } else if (bytes1[0] < bytes2[0]) {
- return 1;
- } else if (bytes1[0] == 0x1) {
- return compareTo(abs(bytes2), abs(bytes1));
- }
- byte[] other1 = copy(bytes1, –1);
- byte[] other2 = copy(bytes2, –1);
- if (other1.length < other2.length) {
- return –1;
- } else if (other1.length > other2.length) {
- return 1;
- } else {
- for (int i = other1.length – 1; i >= 1; i–) {
- if (other1[i] < other2[i]) {
- return –1;
- } else if (other1[i] > other2[i]) {
- return 1;
- }
- }
- return 0;
- }
- }
- public static int compareTo(LargeInteger num1, LargeInteger num2) {
- return compareTo(num1.data, num2.data);
- }
- public int compareTo(LargeInteger num) {
- return compareTo(this.data, num.data);
- }
- private static byte[] add(byte[] data1, byte[] data2) {
- if (data1 == null || data2 == null) {
- throw new NumberFormatException();
- }
- if (data1[0] != data2[0]) {
- // 如果正负号相异,则A+B = A-(-B)
- return subtract(data1, negate(data2));
- }
- //System.out.println(“data1: ” + toString(data1));
- //System.out.println(“data2: ” + toString(data2));
- // 复制A,B,并加长一位,以保证进位
- int length = data1.length > data2.length ? data1.length + 1 : data2.length + 1;
- // byte1复制A,被加数,并作为结果
- byte[] byte1 = copy(data1, length – data1.length);
- // byte2复制B,加数
- byte[] byte2 = copy(data2, length – data2.length);
- // 因为AB同正负号,所以符号不变
- byte1[0] = data1[0];
- // 进位
- int over = 0;
- // 运算位
- int num = 0;
- // 从低位到高位相加计算
- for (int i = 1; i < byte1.length; i++) {
- // 相应位再加进位,相加
- num = byte1[i] + byte2[i] + over;
- //System.out.println(“num: ” + num);
- if (num >= 100) {
- // 有进位
- over = 1;
- num -= 100;
- } else {
- // 无进位
- over = 0;
- }
- byte1[i] = (byte) num;
- }
- return byte1;
- }
- public LargeInteger add(LargeInteger… nums) {
- byte[] augend = this.data;
- for (LargeInteger num : nums) {
- augend = add(augend, num.data);
- }
- return new LargeInteger(augend);
- }
- private static byte[] subtract(byte[] data1, byte[] data2) {
- if (data1 == null || data2 == null) {
- throw new NumberFormatException();
- }
- //System.out.println(“data1: ” + toString(data1));
- //System.out.println(“data2: ” + toString(data2));
- if (data1[0] != data2[0]) {
- // 如果正负号相异,则A-B = A+(-B)
- return add(data1, negate(data2));
- } else if (compareTo(abs(data1), abs(data2)) < 0) {
- // 如果A的绝对值>B的绝对值,则A-B = -(B-A),以保证结果与被减数同符号
- return negate(subtract(data2, data1));
- }
- // data复制A,被减数,并作为结果
- byte[] data = copy(data1, 0);
- // 结果与被减数同符号
- data[0] = data1[0];
- // 退位
- int over = 0;
- // 运算位
- int num = 0;
- for (int i = 1; i < data.length; i++) {
- // 相应位相减,再减退位
- num = data[i] – (i >= data2.length ? 0 : data2[i]) – over;
- //System.out.println(“num: ” + num);
- if (num < 0) {
- // 有退位
- over = 1;
- num += 100;
- } else {
- // 无退位
- over = 0;
- }
- data[i] = (byte) num;
- }
- return data;
- }
- public LargeInteger subtract(LargeInteger… nums) {
- byte[] minuend = this.data;
- for (LargeInteger num : nums) {
- minuend = subtract(minuend, num.data);
- }
- return new LargeInteger(minuend);
- }
- private static byte[] multiply(byte[] data1, byte[] data2) {
- if (data1 == null || data2 == null) {
- throw new NumberFormatException();
- }
- //System.out.println(“data1: ” + toString(data1));
- //System.out.println(“data2: ” + toString(data2));
- int[] data = new int[data1.length + data2.length];
- data[0] = data1[0] ^ data2[0];
- int num = 0;
- for (int i = 1; i < data1.length; i++) {
- for (int j = 1; j < data2.length; j++) {
- num = data1[i] * data2[j];
- data[i + j – 1] += num;
- }
- }
- return copy(data);
- }
- public LargeInteger multiply(LargeInteger… nums) {
- byte[] multiplicand = this.data;
- for (LargeInteger num : nums) {
- multiplicand = multiply(multiplicand, num.data);
- }
- return new LargeInteger(multiplicand);
- }
- private static byte[][] divide(byte[] data1, byte[] data2) {
- if (data1 == null || data2 == null) {
- throw new NumberFormatException();
- } else if (compareTo(data2, new byte[2]) == 0) {
- //System.out.println(“data2: ” + toString(data2));
- throw new ArithmeticException();
- }
- //System.out.println(“data1: ” + toString(data1));
- //System.out.println(“data2: ” + toString(data2));
- byte[] bytes1 = abs(copy(data1, –1));
- byte[] bytes2 = abs(copy(data2, –1));
- byte[][] result = new byte[bytes1.length – bytes2.length + 2][2];
- if (bytes1.length < bytes2.length) {
- result[0] = new byte[2];
- result[1] = bytes1;
- return result;
- }
- byte[] result1 = new byte[bytes1.length – bytes2.length + 2];
- result1[0] = (byte) (data1[0] ^ data2[0]);
- for (int i = result1.length – 1; i >= 1; i–) {
- //System.out.println(“bytes1.length : ” + bytes1.length);
- //System.out.println(“bytes2.length : ” + bytes2.length);
- //System.out.println(“i: ” + i);
- byte[] num2 = shift(bytes2, 1);
- byte[] num1 = subarray(bytes1, i – 1, num2.length);
- //System.out.println(“bytes1: ” + toString(bytes1));
- //System.out.println(“num1 : ” + toString(num1));
- //System.out.println(“num2 : ” + toString(num2));
- for (int j = 99; j > 0; j–) {
- num2 = subtract(num2, bytes2);
- //System.out.println(“j: ” + j);
- //System.out.println(“num1: ” + toString(num1));
- //System.out.println(“num2: ” + toString(num2));
- if (compareTo(num1, num2) >= 0) {
- result1[i] = (byte) j;
- bytes1 = subtract(bytes1, shift(num2, i – 1));
- break;
- }
- }
- }
- result[0] = result1;
- bytes1[0] = data1[0];
- result[1] = bytes1;
- return result;
- }
- public LargeInteger divide(LargeInteger… nums) {
- byte[] quotient = this.data;
- for (LargeInteger num : nums) {
- quotient = divide(quotient, num.data)[0];
- }
- return new LargeInteger(quotient);
- }
- public LargeInteger remainder(LargeInteger num) {
- byte[] remainder = divide(this.data, num.data)[1];
- return new LargeInteger(remainder);
- }
- public LargeInteger mod(LargeInteger num) {
- if (num.data == null) {
- throw new NumberFormatException();
- } else if (compareTo(num.data, new byte[2]) <= 0) {
- throw new ArithmeticException();
- }
- byte[] remainder = divide(this.data, num.data)[1];
- //System.out.println(“remainder: ” + toString(remainder));
- return new LargeInteger(remainder[0] == 0x0 ? remainder : add(num.data, remainder));
- }
- public String toString() {
- return toString(data);
- }
- private static String toString(byte[] data) {
- // 验证数据
- if (data == null || data.length <= 1) {
- return null;
- }
- byte[] bytes = copy(data, –1);
- // 获得数据长度
- int length = bytes.length;
- // 设置输出char array及从低位到高位进行处理的索引
- int index = length + length;
- char[] chars = new char[index–];
- for (int i = 1; i < length; i++) {
- // 获得个位数
- int num1 = bytes[i] % 10;
- // 获得十位数
- int num10 = bytes[i] / 10;
- // 保存个位数的字符
- chars[index–] = (char) (bytes[i] % 10 + ‘0’);
- // 保存十位数的字符
- chars[index–] = (char) (bytes[i] / 10 + ‘0’);
- }
- // 若最高位是’0’,截去
- int left = chars[2] == ‘0’ ? 3 : 2;
- // 设置正负符号
- if (bytes[0] == 0x1) {
- chars[–left] = ‘-‘;
- }
- // 返回字符串
- return new String(chars, left, chars.length – left);
- }
- public static void main(String[] args) {
- System.out.println(“题目要求:如果系统要使用超大整数(超过long的范围),请你设计一个数据结构来存储这种超大型数字以及设计一种算法来实现超大整数的加法运算”);
- String str1 = “7363246083486034683046834068860303406834063467340660286027670238403508439035870357057037452750657194361385618374019364013560156019406349215631248654728652462263”;
- String str2 = “-890450326502467843206225206846783926523485737101634543894739462923749016316021651061090106189734913864619057083749828964002176309116341493496”;
- String str3 = “64068204572572309572305203498204327203957234853207432074230653057026723”;
- LargeInteger num1 = new LargeInteger(str1);
- LargeInteger num2 = new LargeInteger(str2);
- LargeInteger num3 = new LargeInteger(str3);
- BigInteger int1 = new BigInteger(str1);
- BigInteger int2 = new BigInteger(str2);
- BigInteger int3 = new BigInteger(str3);
- //System.out.println(“num2 : ” + num2);
- //System.out.println(“shift: ” + toString(shift(num2.data, 1)));
- //System.out.println(“subarray: ” + toString(subarray(num2.data, 1, 5)));
- System.out.println(“result1: “ + num1);
- System.out.println(“result1: “ + int1);
- System.out.println(“result2: “ + num2);
- System.out.println(“result2: “ + int2);
- System.out.println(“negate: “ + num1.negate());
- System.out.println(“negate: “ + int1.negate());
- System.out.println(“abs: “ + num2.abs());
- System.out.println(“abs: “ + int2.abs());
- System.out.println(“add1: “ + num1.add(num2));
- System.out.println(“add1: “ + int1.add(int2));
- System.out.println(“add2: “ + num1.add(num2, num2, num2));
- System.out.println(“add2: “ + int1.add(int2).add(int2).add(int2));
- System.out.println(“add3: “ + num2.add(num2.negate()));
- System.out.println(“add3: “ + int2.add(int2.negate()));
- System.out.println(“add4: “ + num2.add(num3.negate()));
- System.out.println(“add4: “ + int2.add(int3.negate()));
- System.out.println(“add5: “ + num2.add(num2));
- System.out.println(“add5: “ + int2.add(int2));
- System.out.println(“subtract4: “ + num2.subtract(num3));
- System.out.println(“subtract4: “ + int2.subtract(int3));
- System.out.println(“subtract5: “ + (new LargeInteger(“10000”)).subtract((new LargeInteger(“1”))));
- System.out.println(“subtract5: “ + (new BigInteger(“10000”)).subtract((new BigInteger(“1”))));
- System.out.println(“subtract6: “ + (new LargeInteger(“10000”)).subtract((new LargeInteger(“9999”))));
- System.out.println(“subtract6: “ + (new BigInteger(“10000”)).subtract((new BigInteger(“9999”))));
- System.out.println(“subtract7: “ + (new LargeInteger(“1”)).subtract((new LargeInteger(“10000”))));
- System.out.println(“subtract7: “ + (new BigInteger(“1”)).subtract((new BigInteger(“10000”))));
- System.out.println(“subtract8: “ + (new LargeInteger(“9999”)).subtract((new LargeInteger(“10000”))));
- System.out.println(“subtract8: “ + (new BigInteger(“9999”)).subtract((new BigInteger(“10000”))));
- System.out.println(“subtract9: “ + (new LargeInteger(“-9999”)).subtract((new LargeInteger(“10000”))));
- System.out.println(“subtract9: “ + (new BigInteger(“-9999”)).subtract((new BigInteger(“10000”))));
- System.out.println(“multiply1: “ + num1.multiply(num2));
- System.out.println(“multiply1: “ + int1.multiply(int2));
- System.out.println(“multiply2: “ + num1.multiply(num2, num3));
- System.out.println(“multiply2: “ + int1.multiply(int2).multiply(int3));
- System.out.println(“divide5: “ + (new LargeInteger(“130000”)).divide(new LargeInteger(“4”)));
- System.out.println(“divide5: “ + (new BigInteger(“130000”)).divide(new BigInteger(“4”)));
- System.out.println(“divide6: “ + (new LargeInteger(“-13”)).divide(new LargeInteger(“4”)));
- System.out.println(“divide6: “ + (new BigInteger(“-13”)).divide(new BigInteger(“4”)));
- System.out.println(“divide7: “ + (new LargeInteger(“13”)).divide(new LargeInteger(“-4”)));
- System.out.println(“divide7: “ + (new BigInteger(“13”)).divide(new BigInteger(“-4”)));
- System.out.println(“divide8: “ + (new LargeInteger(“-13”)).divide(new LargeInteger(“-4”)));
- System.out.println(“divide8: “ + (new BigInteger(“-13”)).divide(new BigInteger(“-4”)));
- System.out.println(“mod5: “ + (new LargeInteger(“13”)).mod(new LargeInteger(“4”)));
- System.out.println(“mod5: “ + (new BigInteger(“13”)).mod(new BigInteger(“4”)));
- System.out.println(“mod6: “ + (new LargeInteger(“-13”)).mod(new LargeInteger(“4”)));
- System.out.println(“mod6: “ + (new BigInteger(“-13”)).mod(new BigInteger(“4”)));
- System.out.println(“divide1: “ + num1.divide(num1));
- System.out.println(“divide1: “ + int1.divide(int1));
- System.out.println(“divide2: “ + int1.divide(int1.negate()));
- System.out.println(“divide2: “ + num1.divide(num1.negate()));
- System.out.println(“divide3: “ + num2.divide(num2.negate().add(num3)));
- System.out.println(“divide3: “ + int2.divide(int2.negate().add(int3)));
- System.out.println(“divide4: “ + num2.divide(num2.negate().subtract(num3)));
- System.out.println(“divide4: “ + int2.divide(int2.negate().subtract(int3)));
- System.out.println(“mod1: “ + num2.mod(num3));
- System.out.println(“mod1: “ + int2.mod(int3));
- System.out.println(“mod2: “ + num2.negate().mod(num3));
- System.out.println(“mod2: “ + int2.negate().mod(int3));
- }
- }
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/160065.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...