Fastest way to modify one digit of an integer

Question

Suppose I have an int x = 54897, old digit index (0 based), and the new value for that digit. What's the fastest way to get the new value?

Example

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

Edit: by fastest, I definitely mean faster performance. No string processing.

Answer 1

You gotta get specific with your compute platform if you're talking about performance.

I would approach this by converting the number into pairs of decimal digits, 4 bit each.

Then I would find and process the pair that needs modification as a byte.

Then I would put the number back together.

There are assemblers that do this very well.

Answer 2

If your index started at the least significant digit, you could do something like

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

But since your index is backwards, a string is probably the way to go. It would also be more readable and maintainable.

Answer 3

1. Calculate the "mask" M: 10 raised to the power of index, where index is a zero-based index from the right. If you need to index from the left, recalculate index accordingly.

2. Calculate the "prefix" PRE = x / (M * 10) * (M * 10)

3. Calculate the "suffix" SUF = x % M

4. Calculate the new "middle part" MID = value * M

5. Generate the new number new_x = PRE + MID + POST.

P.S. ruslik's answer does it more elegantly :)

Answer 4

In simplest case (considering the digits are numbered from LSB to MSB, the first one being 0) AND knowing the old digit, we could do as simple as that:

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

For the real problem we would need:

1) the MSB-first version of the pos, that could cost you a log() or at most log10(MAX_INT) divisions by ten (could be improved using binary search).

2) the digit from that pos that would need at most 2 divisions (or zero, using results from step 1).

You could also use the special fpu instruction from x86 that is able to save a float in BCD (I have no idea how slow it is).

UPDATE: the first step could be done even faster, without any divisions, with a binary search like this:

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;
    }
}

Answer 5

You need to start by figuring out how many digits are in your input. I can think of two ways of doing that, one with a loop and one with logarithms. Here's the loop version. This will fail for negative and zero inputs and when the index is out of bounds, probably other conditions too, but it's a starting point.

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)

P.S. This is working Python code. The principle of something simple like this is easy to work out, but the details are so tricky that you really need to iterate it a bit. In this case I started with the principle that I wanted to subtract out the old digit and add the new one; from there it was a matter of getting the correct multiplier.