0

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

例子

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

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

4

5 回答 5

3

在最简单的情况下（考虑到数字从 LSB 到 MSB，第一个是 0）并且知道旧数字，我们可以这样做：

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

对于我们需要的真正问题：

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

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

您还可以使用 x86 中的特殊 fpu 指令，该指令能够在 BCD 中保存浮点数（我不知道它有多慢）。

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

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;
    }
}
于 2010-10-04T18:41:52.127 回答
2

如果您的索引从最低有效位开始，您可以执行类似的操作

p = pow(10,index);
x = (x / (p*10) * (p*10) + value * p + x % p).

但是由于您的索引是向后的，因此字符串可能是要走的路。它也将更具可读性和可维护性。

于 2010-10-04T18:34:51.817 回答
1

  1. 计算“掩码” M： 10 的 次方index，其中index是从右侧开始的从零开始的索引。如果您需要从左侧开始索引，请相应地重新计算index。

  2. 计算“前缀”PRE = x / (M * 10) * (M * 10)

  3. 计算“后缀”SUF = x % M

  4. 计算新的“中间部分”MID = value * M

  5. 生成新号码new_x = PRE + MID + POST。

PS ruslik 的回答做得更优雅:)

于 2010-10-04T18:37:55.873 回答
1

您需要首先弄清楚您的输入中有多少位数字。我可以想到两种方法，一种是循环，另一种是对数。这是循环版本。这对于负输入和零输入以及索引超出范围时（可能还有其他条件）将失败，但这是一个起点。

def f(x, index, value):
    place = 1
    residual = x
    while residual > 0:
        if index < 0:
            place *= 10
        index -= 1
        residual /= 10
    digit = (x / place) % 10
    return x - (place * digit) + (place * value)

PS这是工作Python代码。像这样简单的事情的原理很容易解决，但细节非常棘手，你真的需要迭代一下。在这种情况下，我从要减去旧数字并添加新数字的原则开始；从那里得到正确的乘数是一个问题。

于 2010-10-04T18:42:06.680 回答
0

如果您谈论性能，则必须具体说明您的计算平台。

我会通过将数字转换为十进制数字对来解决这个问题，每个数字为 4 位。

然后我会找到并处理需要修改为字节的对。

然后我会把号码重新组合在一起。

有些汇编程序做得很好。

于 2010-10-04T18:31:14.077 回答