Java中任意长度二进制整数的算术运算

1. 概述

在数字信号处理、计算机图形学和密码学等领域，二进制数的位运算是核心操作。这些场景通常需要处理任意长度的二进制数，而Java原生类型（如int/long）的位数限制（32/64位）显然不够用。

本文将探讨在Java中实现任意精度二进制算术运算的两种方案：

✅ 使用BigInteger类（推荐方案）
✅ 自定义实现（适用于无BigInteger的环境）

同时会分析二进制字面量的限制，解释为什么原生类型无法满足需求，以及负数的二进制表示方式。

2. 二进制字面量的位数限制

Java允许使用二进制字面量（如0b1010）表示整数，但存在两个关键限制：

2.1 位数限制

int类型：最多32位
long类型：最多64位

@Test
void givenTwoBinaryLiterals_whenAdding_thenResultIsCorrect() {
    int a = 0b110100101101010;
    int b = 0b1000;
    int expected = 0b110100101110010; // a + b的二进制结果
    assertEquals(expected, a + b, "加法结果应正确");
}

2.2 负数表示

负数使用补码（two's complement）表示，例如：

@Test
void whenComparingBinaryToDecimal_thenValuesAreEqual() {
    int c = 0b11111111111111111111111111111000; // 2^32 - 8
    int expected = -8;
    assertEquals(expected, c, "二进制值应等于-8");
}

2.3 超限问题

当二进制字面量超过类型限制时，编译器会报错：二进制字面量超出范围错误

⚠️ 结论：二进制字面量无法满足任意精度需求，但补码表示法在后续自定义实现中仍会用到。

3. 任意长度二进制整数

3.1 方案选择

方案	适用场景	优点	缺点
`BigInteger`	标准Java环境	✅ 简单可靠 ✅ 高度优化	❌ 不适用于Java ME等受限环境
自定义实现	无`BigInteger`环境	✅ 完全可控 ✅ 教育价值	❌ 实现复杂 ❌ 性能较差

3.2 使用BigInteger

BigInteger支持任意精度运算，且无需手动处理补码：

@Test
void givenTwoBigIntegers_whenAdding_thenResultIsCorrect() {
    BigInteger a = new BigInteger("1101001011010101010101010101010101010101010101010101010101010101010", 2);
    BigInteger b = new BigInteger("-10000", 2);
    BigInteger expected = new BigInteger("1101001011010101010101010101010101010101010101010101010101010011010", 2);
    assertEquals(expected, BigIntegerExample.add(a, b), "加法结果应正确");
}

3.3 自定义实现（BinaryStringOperations）

当BigInteger不可用时（如Java ME CLDC 8），需手动实现。核心设计要点：

3.3.1 符号表示

正数：直接使用二进制字符串（如"1010"）
负数：添加负号前缀（如"-1010"）

@Test
void givenTwoBinaryStrings_whenAdding_thenResultIsCorrect() {
    String a = "1101001011010101010101010101010101010101010101010101010101010101010"; // 67位
    String b = "-10000";
    String expected = "1101001011010101010101010101010101010101010101010101010101010011010";
    assertEquals(expected, BinaryStringOperations.add(a, b), "加法结果应正确");
}

3.3.2 运算方法结构

所有运算方法（add/subtract/multiply/divide）遵循统一结构：

✅ 输入验证（确保是合法二进制字符串）
✅ 符号处理（提取符号位）
✅ 根据符号组合调用无符号运算
✅ 结果符号处理

以加法为例：

static String add(String a, String b) {
    String unsignedA = removePlusMinus(a);
    String unsignedB = removePlusMinus(b);

    if (isPositive(a)) {
        if (isPositive(b)) {
            return unsignedAdd(unsignedA, unsignedB); // 正+正
        } else {
            return subtract(unsignedA, unsignedB);     // 正+负
        }
    } else {
        if (isPositive(b)) {
            return subtract(unsignedB, unsignedA);     // 负+正
        } else {
            return '-' + unsignedAdd(unsignedA, unsignedB); // 负+负
        }
    }
}

3.3.3 核心无符号运算实现

(1) 无符号加法（`unsignedAdd`）

模拟手工二进制加法，逐位处理进位：

static String unsignedAdd(String a, String b) {
    validateUnsignedBinaryString(a);
    validateUnsignedBinaryString(b);
    
    // 去除前导零
    a = a.replaceFirst("^0+(?!$)", "");
    b = b.replaceFirst("^0+(?!$)", "");

    int length = Math.max(a.length(), b.length());
    a = String.format("%" + length + "s", a).replace(' ', '0');
    b = String.format("%" + length + "s", b).replace(' ', '0');

    StringBuilder result = new StringBuilder(length * 2);
    boolean carry = false;

    // 从最低位(LSB)向最高位(MSB)迭代
    for (int i = length - 1; i >= 0; i--) {
        boolean v1 = (a.charAt(i) == '1');
        boolean v2 = (b.charAt(i) == '1');

        // 计算当前位结果（使用真值表优化）
        boolean r = carry && v1 && v2 || carry && !v1 && !v2 || !carry && v1 && !v2 || !carry && !v1 && v2;
        carry = carry && v1 || carry && v2 || v1 && v2;
        result.insert(0, r ? '1' : '0');
    }

    if (carry) result.insert(0, '1');
    return result.toString();
}

(2) 无符号减法（`unsignedSubtract`）

利用补码将减法转换为加法：

static String unsignedSubtract(String a, String b) {
    // 补码步骤1：反转所有位
    StringBuilder inverted = new StringBuilder();
    for (int i = 0; i < b.length(); i++) {
        inverted.append(b.charAt(i) == '0' ? '1' : '0');
    }
    
    // 补码步骤2：加1
    String b2complement = addOne(inverted.toString());
    
    // 执行加法并丢弃进位位
    return unsignedAdd(a, b2complement).substring(1);
}

(3) 无符号乘法（`unsignedMultiply`）

模拟手工乘法，通过移位和累加实现：

static String unsignedMultiply(String a, String b) {
    String result = "0";
    int zeros = 0;
    
    // 从最低位向最高位遍历乘数b
    for (int i = b.length() - 1; i >= 0; i--) {
        zeros++;
        if (b.charAt(i) == '1') {
            // 计算部分积（移位后的a）
            String partialProduct = appendZeros(a, zeros);
            result = unsignedAdd(result, partialProduct);
        }
    }
    return result;
}

(4) 无符号除法（`unsignedDivide`）

模拟手工除法，逐位比较和减法：

static String unsignedDivide(String a, String b) {
    StringBuilder result = new StringBuilder();
    String remainder = "";
    
    // 从最高位向最低位遍历被除数a
    for (int i = 0; i < a.length(); i++) {
        if (result.length() == 0) {
            // 初始化阶段
            if (compareBinaryStrings(a.substring(0, i + 1), b) >= 0) {
                result.append('1');
                remainder = unsignedSubtract(a.substring(0, i + 1), b);
            }
        } else {
            // 常规步骤
            remainder += a.charAt(i);
            if (compareBinaryStrings(remainder, b) >= 0) {
                result.append('1');
                remainder = unsignedSubtract(remainder, b);
            } else {
                result.append('0');
            }
        }
    }
    return result.toString();
}

3.3.4 性能优化

⚠️ 重要提醒：自定义实现虽正确，但性能远不如BigInteger。后者使用了高度优化的算法（如Karatsuba乘法、Burnikel-Ziegler除法等），在处理大数时性能差异可达数量级。

4. 结论

在Java中处理任意长度二进制整数时：

✅ **优先使用BigInteger**：简单、高效、可靠
✅ 自定义实现作为备选：适用于无BigInteger的环境或教学目的
❌ 避免使用二进制字面量：位数限制使其无法满足任意精度需求

完整实现代码可在GitHub获取。对于生产环境，强烈建议直接使用BigInteger，避免重复造轮子。

Persistence

REST

Security