Java中如何将LSB优先的大BitList转换为十进制字符串？

我完成了一项作业，实现了BinaryNumber类，该类包含一个以LSB（最低有效位）优先方式表示二进制数的BitList。现在需要实现toIntString()方法，输出该二进制数对应的十进制字符串——即使数值远大于int、long等基本数据类型的范围。示例如下：

BinaryNumber fib100 = new BinaryNumber("354224848179261915075");
// 内部BitList的LSB优先二进制表示（下方为拆分显示的二进制串，实际是连续的LSB在前序列）
// 100110011001111011011011
// 101101010011111000101100
// 101001011111111000011
System.out.println(fib100.toIntString()); // 输出 354224848179261915075

我曾尝试在初始化BinaryNumber时存储十进制数值，但不被允许。想了解是否存在无需存储数值、仅通过算法即可完成转换的方法？

当然有纯算法实现的方法，核心思路是用字符串模拟大数运算，遍历LSB优先的二进制位，逐步构建十进制字符串，不需要依赖任何大整数类或预存数值。具体步骤如下：

1. 初始化结果：从十进制字符串"0"开始，作为初始累加值。
2. 遍历每一位二进制位：因为是LSB优先，从第0位（对应2^0）开始依次处理每一位：
   • 先将当前十进制字符串乘以2：这相当于把之前的累加值位权提升一级（比如之前是2^{i的贡献，乘2后变成2}(i+1)），模拟二进制左移一位的效果。
   • 如果当前二进制位是1，就将十进制字符串加1：加上当前位对应的2^i的贡献。
3. 完成遍历：处理完所有二进制位后，得到的字符串就是最终的十进制结果。

关键辅助方法实现思路 #

需要自己实现两个字符串版的大数运算方法：

• multiplyByTwo(String num)：将十进制字符串乘以2，从末尾向前逐位计算，处理进位。
  示例："123" → "246"，"999" → "1998"
• addOne(String num)：将十进制字符串加1，从末尾向前处理进位。
  示例："123" → "124"，"999" → "1000"

Java代码示例框架 #

public class BinaryNumber {
    private BitList bits; // LSB优先的二进制位列表

    // 构造方法等其他代码...

    public String toIntString() {
        String result = "0";
        for (int i = 0; i < bits.size(); i++) {
            // 先乘2，提升位权
            result = multiplyByTwo(result);
            // 如果当前位是1，加1
            if (bits.get(i)) { // 假设BitList的get方法返回该位是否为1
                result = addOne(result);
            }
        }
        return result;
    }

    // 辅助方法：十进制字符串乘2
    private String multiplyByTwo(String num) {
        StringBuilder sb = new StringBuilder();
        int carry = 0;
        // 从末尾开始处理每一位
        for (int i = num.length() - 1; i >= 0; i--) {
            int digit = num.charAt(i) - '0';
            int product = digit * 2 + carry;
            sb.append(product % 10);
            carry = product / 10;
        }
        // 处理剩余进位
        if (carry > 0) {
            sb.append(carry);
        }
        // 反转得到正确顺序
        return sb.reverse().toString();
    }

    // 辅助方法：十进制字符串加1
    private String addOne(String num) {
        StringBuilder sb = new StringBuilder(num);
        int i = sb.length() - 1;
        // 从末尾找第一个不是9的位
        while (i >= 0 && sb.charAt(i) == '9') {
            sb.setCharAt(i, '0');
            i--;
        }
        if (i < 0) {
            // 所有位都是9，需要新增一位
            return "1" + sb.toString();
        } else {
            sb.setCharAt(i, (char)(sb.charAt(i) + 1));
            return sb.toString();
        }
    }
}

这种方法完全基于字符串运算，不需要存储任何超出基本类型的数值，完全符合需求。

内容的提问来源于stack exchange，提问作者Shlompi