The Four Arithmetic Operation of BigInteger
大整数的四则运算，很多数人都写过，本文提供一个 Java 版本的朴素实现，即模拟竖式。除法使用了递归，效率不高，递推公式如下：求商 = 连接( 被除数大于等于除数的最小前缀 / 除数, 逐位连接(上式余数, 被除数剩余部分)[期间, 若连接后的被除数小于除数, 商上零], [连接完毕后, 若被除数不小于除数, 求商(连接后的被除数, 除数)] )当商高于一千位时，递归版本栈溢出，改为等价迭代后，一亿位被除数测试通过。 Java Implementation package im.logi.math; import java.util.ArrayList; import java.util.List; import java.util.Random; import java.util.function.BiFunction; import java.util.stream.IntStream; /** * @author logi * @version 1.0 * @time 2022/1/5 16:08 */ public class BigInteger implements Comparable<BigInteger>, Cloneable { private static final BigInteger ZERO = new BigInteger("0"); private static final BigInteger ONE = new BigInteger("1"); private boolean positive = true; private StringBuilder value; private BigInteger() { value = new StringBuilder(); } public BigInteger(String valueString) { int beginIndex = 0; if (valueString.charAt(0) == '-') { beginIndex = 1; positive = false; } else if (valueString.charAt(0) == '+') beginIndex = 1; while (beginIndex < valueString.length() && valueString.charAt(beginIndex) == '0') beginIndex++; // 仅是一个符号或全部为零，回退 if (beginIndex == valueString.length()) beginIndex--; value = new StringBuilder(valueString.length() - beginIndex); for (int i = beginIndex; i < valueString.length(); i++) { char c = valueString.charAt(i); if (c < '0' || c > '9') throw new IllegalArgumentException(); value.append(c); } setZeroPositive(); } // 只存正零 private void setZeroPositive() { if (value.length() == 1 && value.charAt(0) == '0') positive = true; } @Override protected Object clone() throws CloneNotSupportedException { BigInteger clone = (BigInteger) super.clone(); clone.positive = positive; clone.value = new StringBuilder(value); return clone; } @Override public boolean equals(Object obj) { if (obj instanceof BigInteger o) return positive == o.positive && value.toString().equals(o.value.toString()); return false; } @Override public int compareTo(BigInteger o) { if (positive != o.positive) return positive ? 1 : -1; int absRet = value.length() - o.value.length(); if (absRet != 0) return positive ? absRet : -absRet; for (int i = 0; i < value.length(); i++) { absRet = get(i) - o.get(i); if (absRet != 0) break; } return positive ? absRet : -absRet; } @Override public String toString() { return (positive ? "" : "-") + value; } // 相反数，拷贝返回 public BigInteger negative() { BigInteger negative; try { negative = (BigInteger) clone(); } catch (CloneNotSupportedException e) { throw new RuntimeException(); } negative.positive = !positive; negative.setZeroPositive(); return negative; } // 绝对值，拷贝返回 public BigInteger absolute() { BigInteger absolute = negative(); absolute.positive = true; return absolute; } private int get(int index) { return value.charAt(index) - '0'; } private void set(int index, int place) { value.setCharAt(index, (char) (place + '0')); } // 去除前导零，时间复杂度 O(n) private void trimZero() { int i = 0; // 唯一零不处理 //noinspection StatementWithEmptyBody for (; i < value.length() - 1 && get(i) == 0; i++) ; value.delete(0, i); } // 加 public BigInteger add(BigInteger second) { if (positive != second.positive) { return positive ? subtract(second.negative()) : second.subtract(negative()); } // 以下为同号情况 BigInteger sum = new BigInteger(); sum.positive = positive; BigInteger longer = this; BigInteger shorter = second; if (value.length() < second.value.length()) { longer = second; shorter = this; } // 多开一位 for (int i = 0; i <= longer.value.length(); i++) sum.value.append(0); int i = longer.value.length() - 1; int j = shorter.value.length() - 1; for (; j >= 0; i--, j--) { int k = i + 1; int s = longer.get(i) + shorter.get(j) + sum.get(k); sum.set(k, s % 10); sum.set(i, s / 10); } for (; i >= 0; i--) { int k = i + 1; int s = longer.get(i) + sum.get(k); sum.set(k, s % 10); sum.set(i, s / 10); } sum.trimZero(); return sum; } // 减 public BigInteger subtract(BigInteger second) { if (equals(second)) return ZERO; if (positive != second.positive) { return positive ? add(second.negative()) : second.add(negative()).negative(); } BigInteger abs = absolute(); BigInteger secAbs = second.absolute(); if (abs.compareTo(secAbs) < 0) { BigInteger diff = secAbs.subtract(abs); diff.positive = !positive; return diff; } else if (!positive) { BigInteger diff = abs.subtract(secAbs); diff.positive = false; return diff; } // 以下为全正且 this > second 的情况 BigInteger diff = new BigInteger(); if (value.length() == 1) { diff.value.append(get(0) - second.get(0)); return diff; } // 多开一位 diff.value.append(0); diff.value.append((char) ('0' - 1)); for (int i = 2; i < value.length(); i++) diff.value.append(9); diff.value.append((char) ('9' + 1)); int i = value.length() - 1; int j = second.value.length() - 1; for (; j >= 0; i--, j--) { int k = i + 1; int d = get(i) - second.get(j) + diff.get(k); diff.set(k, d % 10); diff.set(i, d / 10 + diff.get(i)); } for (; i >= 0; i--) { int k = i + 1; int d = get(i) + diff.get(k); diff.set(k, d % 10); diff.set(i, d / 10 + diff.get(i)); } diff.trimZero(); return diff; } // 乘 public BigInteger multiply(BigInteger second) { if (equals(ZERO) || second.equals(ZERO)) return ZERO; BigInteger oneMul = null; if (absolute().equals(ONE)) oneMul = second; else if (second.absolute().equals(ONE)) oneMul = this; if (oneMul != null) return positive == second.positive ? oneMul.absolute() : oneMul.absolute().negative(); BigInteger product = new BigInteger(); product.positive = positive == second.positive; for (int i = 0; i < value.length() + second.value.length(); i++) product.value.append(0); for (int i = value.length() - 1; i >= 0; i--) { for (int j = second.value.length() - 1; j >= 0; j--) { int h = i + j; int l = h + 1; int p = get(i) * second.get(j) + product.get(l); product.set(l, p % 10); product.set(h, p / 10 + product.get(h)); } } product.trimZero(); return product; } // 除 public BigInteger divide(BigInteger second) { if (second.equals(ZERO)) throw new ArithmeticException(); // if (equals(ZERO)) return ZERO; if (absolute().compareTo(second.absolute()) < 0) return ZERO; if (second.absolute().equals(ONE)) return positive == second.positive ? absolute() : absolute().negative(); if (absolute().equals(second.absolute())) return positive == second.positive ? ONE : ONE.negative(); if (positive != second.positive) return absolute().divide(second.absolute()).negative(); if (!positive) return absolute().divide(second.absolute()); // 以下为全正且 this > second 的情况 BigInteger quotient = new BigInteger(); quotient.positive = true; BigInteger dividend = this; outer: while (true) { BigInteger diff = new BigInteger(); int i = 0; // this > second，总能取到 diff > second，不会越界 do { diff.value.append(dividend.get(i++)); } while (diff.compareTo(second) < 0); // diff >= second 首次成立, 商至少为 1 且不大于 9 int c = 1; //noinspection StatementWithEmptyBody for (; (diff = diff.subtract(second)).compareTo(second) >= 0; c++) ; quotient.value.append(c); if (i >= dividend.value.length()) break; BigInteger rest = new BigInteger(); if (diff.equals(ZERO)) { // 除尽，检查后续若干零 while (dividend.get(i++) == 0) { quotient.value.append(0); if (i >= dividend.value.length()) { break outer; } } } else { // 未除尽，余数作下一轮被除数前缀 rest.value.append(diff.value); } // 若必要，商补若干零 do { rest.value.append(dividend.get(i++)); if (rest.compareTo(second) < 0) quotient.value.append(0); else break; if (i >= dividend.value.length()) break outer; } while (true); rest.value.append(dividend.value.substring(i)); if (rest.compareTo(second) < 0) break; dividend = rest; } return quotient; } public static void testOperation( BiFunction<BigInteger, BigInteger, BigInteger> testedOperation, BiFunction<java.math.BigInteger, java.math.BigInteger, java.math.BigInteger> standardOperation, char operator, String a, String b ) { Exception testedException = null; BigInteger testedResult = null; try { testedResult = testedOperation.apply(new BigInteger(a), new BigInteger(b)); } catch (Exception e) { testedException = e; } Exception expectedException = null; java.math.BigInteger expectedResult = null; try { expectedResult = standardOperation.apply(new java.math.BigInteger(a), new java.math.BigInteger(b)); } catch (Exception e) { expectedException = e; } if (expectedException != null && testedException != null) return; if (expectedException != null) { System.out.printf("The result is wrong: %s %s %s = %s, got %s\n", a, operator, b, expectedException, testedResult); throw new RuntimeException(); } if (testedException != null) { System.out.printf("The result is wrong: %s %s %s = %s, got %s\n", a, operator, b, expectedResult, testedException); throw new RuntimeException(); } if (!testedResult.toString().equals(expectedResult.toString())) { System.out.printf("The result is wrong: %s %s %s = %s, got %s\n", a, operator, b, expectedResult, testedResult); throw new RuntimeException(); } } public static void testOne(List<String> pair) { testOperation(BigInteger::add, java.math.BigInteger::add, '+', pair.get(0), pair.get(1)); testOperation(BigInteger::subtract, java.math.BigInteger::subtract, '-', pair.get(0), pair.get(1)); testOperation(BigInteger::multiply, java.math.BigInteger::multiply, 'x', pair.get(0), pair.get(1)); testOperation(BigInteger::divide, java.math.BigInteger::divide, '/', pair.get(0), pair.get(1)); } public static void testAll(List<String> pair) { List<List<String>> cases = List.of( List.of(pair.get(0), pair.get(1)), List.of(pair.get(0), "-" + pair.get(1)), List.of("-" + pair.get(0), pair.get(1)), List.of("-" + pair.get(0), "-" + pair.get(1)) ); cases.forEach(BigInteger::testOne); if (pair.get(0).equals(pair.get(1))) return; cases.stream().map(p -> List.of(p.get(1), p.get(0))) .forEach(BigInteger::testOne); } public static String generateRandomBigInteger(int spaceBound) { spaceBound = Math.max(spaceBound, 1001); Random r = new Random(); StringBuilder s = new StringBuilder(); for (int i = 0; i < r.nextInt(spaceBound - 1000, spaceBound); i++) { s.append(r.nextInt(0, 10)); } return s.toString(); } public static void main(String[] args) { // If no exception thrown during execution, test will pass. int spaceBound = 100000; List<List<String>> cases = new ArrayList<>(List.of( List.of("0", "0"), List.of("0", "34291743"), List.of("1", "1"), List.of("1", "3247091"), List.of("7", "392"), List.of("000007", "392"), List.of("7", "00000392"), List.of("0007", "00000392"), List.of("0007", "sa23bcd"), List.of("---3427190", "sa23bcd"), List.of("++34721", "32147"), List.of("432134", "842097") )); IntStream.range(0, 10).forEach(_ignored -> cases.add( List.of(generateRandomBigInteger(spaceBound), generateRandomBigInteger(spaceBound)))); cases.forEach(BigInteger::testAll); } } Rust Implementation 本文链接生成方法 "The Four Arithmetic Operation of BigInteger".split(" ").map(word => word.toLowerCase()).join("-") RelatedIEEE 754 基本浮点数的精度和范围
Resolving Spring Boot Configuration Annotation Processor Not Configured Warning in IntelliJ IDEA
在 IDEA 2021.2.2 中编写 Spring Boot 项目，打开使用了 @ConfigurationProperties 注解的类时，标签页下方会出现 Spring Boot Configuration Annotation Processor not configured 的提示，而提示给出的文档链接已经 404 了。搜索后发现 Spring Boot Configuration Annotation Processor 会扫描被 @ConfigurationProperties 注解的类，以此生成配置元数据，这些元数据可以被编译器读取用于 application.properties 中配置项的自动补全和错误检查。根据 Spring Boot 文档，只要引入相应依赖并重新编译项目便可生成配置元数据。但即便如此，IDEA 的提示有时并不消失，此时需要重载项目。之后，提示文字转为 Re-run Spring Boot Configuration Annotation Processor to update generated metadata，并且背景由红色转为深灰。这个提示只是在说，如果更改了类，记得重新编译更新元数据，并非警告，无需理会。此时打开 application.properties 就会发现自动补全已经可以正常使用了。网络上的一些文章说的打开 IDEA 设置里的 Enable annotation processing 实际是另一个功能，与此无关。[...]
FieldA data member of a class. Unless specified otherwise, a field is not static.类的数据成员。除非指定，它不是静态的。举例：public class Customer { // Fields of Customer final String field1 = "Fixed Value"; int name; }AttributeAn attribute is another term for a field. It’s typically a public field that can be accessed directly.Field 的别称，它通常是可以直接访问的 public field，例如数组的长度。（Java SE 术语表中无此定义）PropertyCharacteristics of an object that users can set, such as the color of a window.对象的特征，用户可以设置它，例如窗户的颜色。举例：public class Window { // Property of Window private String color; public String getColor() { return this.color; } public void setColor(String color) { this.color = color; } }ReferencesWhat is the difference between field, variable, attribute, and property in JavaWhat is the difference between field, variable, attribute, and property in Java POJOs?Glossary of Terms
Double Curly Braces Initialization in Java
准备给之前 Python 写的 QQ 机器人加点功能，发现升级后的依赖库变动很大，加上之前有些 Bug，瞬间不想用了，用上游框架重写吧。上游项目基于 Kotlin，我不熟悉，但提供 Java API，克隆示例代码，OK，可以运行。正准备往前推进，突然发现 有段代码 的语法我竟然看不懂，心想 Java 用了挺长时间不至于吧。[...]