Самый быстрый способ изменить одну цифру целого

Question

Предположим, у меня есть int x = 54897, старый цифровой индекс (на основе 0) и новое значение для этой цифры. Какой самый быстрый способ получить новое значение?

Пример

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

Edit: по самым быстрым, я определенно имею в виду более высокую производительность. Нет строковой обработки.

Answer 1

В простейшем случае (с учетом цифр нумеруются от LSB до MSB, первый из которых является 0), зная старый цифру, мы могли бы сделать так же просто, как:

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

Для реальной задачи нужно было:

1) MSB первой версии pos, которые могут стоить вам log() или в лучшем случае log10(MAX_INT) деления на десять (может быть улучшена с помощью бинарного поиска).

2) цифра от pos, которой потребуется не более 2 делений (или ноль, используя результаты этапа 1).

Вы также можете использовать специальную инструкцию fpu от x86, которая может сохранить поплавок в BCD (я понятия не имею, насколько это медленное время).

UPDATE: первый шаг можно сделать еще быстрее, без каких-либо подразделений, с бинарным поиском, как это:

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 2

Вы должны уточнить свою вычислительную платформу, если речь идет о производительности.

Я бы приблизился к этому путем преобразования числа в пары десятичных цифр, по 4 бит каждый.

Тогда я бы нашел и обработал пару, которая нуждается в модификации в виде байта.

Тогда я бы поставил номер обратно вместе.

Есть ассемблеры, которые делают это очень хорошо.

Answer 3

Если ваш индекс начал в значащих цифрах, вы могли бы сделать что-то вроде

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

Но так как ваш индекс в обратном направлении, строка, вероятно, путь. Он также был бы более читабельным и поддерживаемым.

Answer 4

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.

P.S. Ответ Ruslik в делает это более элегантно :)

Answer 5

Вы должны начать выяснить, сколько цифр в вашем входе. Я могу представить два способа сделать это: один с петлей и один с логарифмами. Вот версия цикла. Это не удастся для отрицательных и нулевых входов, а когда индекс окажется за пределами границ, возможно, и других условий, но это отправная точка.

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. Это рабочий код Python. Принцип чего-то простого подобного легко проработать, но детали настолько сложны, что вам действительно нужно немного повторить его. В этом случае я начал с принципа, что я хотел бы вычесть старую цифру и добавить новую; оттуда нужно было получить правильный множитель.