algorithm - 修改整数一位数的最快方法

Question

假设我有一个 int x = 54897、旧数字索引(基于 0)和该数字的新值。获取新值的最快方法是什么？

例子

x = 54897
index = 3
value = 2
y = f(x, index, value) // => 54827

编辑:所谓最快，我指的绝对是更快的性能。没有字符串处理。

Answer 1

在最简单的情况下(考虑到数字是从 LSB 到 MSB 编号的，第一个是 0)并且知道旧数字，我们可以这么简单:

num += (new_digit - old_digit) * 10**pos;

对于真正的问题，我们需要:

1) pos 的 MSB 优先版本，这可能会花费您 log() 或最多 log10(MAX_INT)除以十(可以使用二进制搜索进行改进)。

2) pos 中最多需要 2 个除法的数字(或零，使用步骤 1 的结果)。

您还可以使用 x86 中的特殊 fpu 指令，该指令能够以 BCD 格式保存 float (我不知道它有多慢)。

更新:第一步可以更快地完成，没有任何划分，使用像这样的二进制搜索:

int my_log10(unsigned short n){
    // short: 0.. 64k -> 1.. 5 digits 
    if (n < 1000){  // 1..3
        if (n <  10) return 1;
        if (n < 100) return 2;
        return 3;
    } else { // 4..5
        if (n < 10000) return 4;
        return 5;
    }
}