java - 在算术中避免 BigInteger 类/大数

Question

我正在对字符串执行一些 mod 算术类型的操作，其中每个字符都会获得特定的初始值(取决于其 ascii)和字符串中的位置。这些数字变得非常大，因为它们的初始值为 (ascii)*26^charPos。值得注意的是，数字字符仅将其值(0-9)添加到总数中；

有没有办法避免使用 BigInt 类(因为我只对 (intialVal)%(相对较小的数字)感兴趣) 我想你可以使用通常的:

value += val;
  if(value >= mod)
   value = value % mod;

但这仅适用于整数的排序列表，也无法解决单个字符使用上述字符值公式生成 BigInt 的问题。我确信可以使用 mod 运算符来完成一些事情。

顺便说一句；如果 bigNum 超过了 long(或 int，无论 foo 是如何声明的)的大小，那么算术将无法正确计算，对吗？

int(or long) foo = BigNum(possibly bigger than long) % smallMod;

我意识到我可以声明几个 BigInteger 对象，然后将所有值添加到totalValue，然后对总计执行最终的 mod 操作，但如果可能的话，我宁愿避免这种情况，因为 BigInteger 算术是我没有太多使用的东西(而且它看起来很痛苦，在这种情况下通常是不必要的)。我知道会有很多方法，但我不介意听到一些不同的观点。提前致谢。

这是我想出的一些代码，只要长阈值没有被打破，它们就可以工作；

public static void main(String[] args) {

    String str = "st4ck0ver";

    char[] x = str.toCharArray();
    long value = 0;
    int mod = 87;

    for(int i = 0; i < x.length; i++) {

        long val;
        int charVal;
        int exp = x.length - (i+1);

        if((int)x[i] < 58) {
            charVal = (int)x[i] - 48;
            val = charVal;
        }
        else{
            charVal = (int)x[i]- 96;
            val = (long) (charVal * Math.pow(26, exp));
        }

        value += val;

        System.out.println("exp:" + exp + ",  char:" + x[i] + ", "
                + ",  charValue:" + charVal + " value:" + val + ",  curr total value:" + value);
    }
    value %= mod;
    System.out.println("Final value:" + value); 
}

<小时/>

编辑:回应大卫·华莱士的回答:

抱歉，我重读了您的解释，我确实理解您在做什么...您的回答正是我的意思。我只是在处理字符是数字的情况时遇到麻烦，因为它只添加数值而不是乘以 26^pos。我保留了数值的运行总计，以便将其添加到最终答案中(如果超过 mod 值，则再次对其进行修改)，但我也不知道如何将适当的功率增加 1。我可能遗漏了一些非常明显的东西。注释的代码是我解决这个问题的一半尝试:

public static void main(String[] args) {
    //String str = "st4ck0ver";
    //String str = "hello";
    String str = "time2go";

    char[] x = str.toCharArray();
    int mod = 2004;

    int answer = 0;
    int power = 1;
    int numericalVal = 0;
    //int skipPower;

    for (int i = x.length - 1; i >=0; i--) {
        int charVal;

        if((int)x[i] < 58)  {
            charVal = (int)x[i] - 48;
            numericalVal += charVal;
            //skipPower++; //perhaps need to use something like this?
                //
        }       //      down
        else {  //   in here somewhere
            charVal = (int)x[i]- 96;

            answer += ( charVal * power);
            answer %= mod;
            power *= 26;
            power %= mod;
            //skipPower = 0; //reset skipPower in case it was used
        }
    }
    //answer += numericalVal;
    //if(answer + numericalVal >= mod)
    //  answer %= mod;

    System.out.println("Final value:" + answer);    
}

Answer 1

如果您在某个模数中执行此操作，则迭代您的字符串，跟踪该模数中所需值的运行总计，以及同样在该模数中的 26 的相应幂的值。如果模数非常小，正如您所说，那么 int 应该足以满足其中每一个。

请注意，我假设您的String 此处仅包含小写字母。如果需要，请修复此问题。

int answer = 0;
int power = 1;

for (int i = 0; i < inputString.length(); i++) {
    int charValue = inputString.charAt(i) - 'a';
    answer += ( charValue * power );
    answer %= mod;
    power *= 26;
    power %= mod;
}

编辑

适应OP的编辑，它表明String必须以相反的顺序遍历，并且在遇到数字时不考虑位置值，代码可能应如下所示。

int answer = 0;
int power = 1;

for (int i = inputString.length() - 1; i >=0; i--) {

    if(inputString.charAt( i ) < 58)  {
        int charValue  = inputString.charAt( i ) - 48;
        answer += charValue;
    }       
    else {  
        int charValue  = inputString.charAt( i ) - 96;
        answer += ( charValue * power );
    }

    answer %= mod;
    power *= 26;
    power %= mod;
}