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

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) MSB-первая версия pos, которая может стоить вам log() или максимум log10(MAX_INT) делений на десять (может быть улучшено с помощью бинарного поиска).

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

Вы также можете использовать специальную инструкцию fpu из x86, которая способна сохранить число с плавающей запятой в 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;
    }
}

Answer 2

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

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

Но так как ваш индекс обратный, возможно, вам подойдет строка. Это также было бы более читабельным и ремонтопригодным.

Answer 3

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

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

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.

PS Ответ Руслика делает это более элегантно:)

Answer 5

Вы должны быть конкретны с вашей вычислительной платформой, если вы говорите о производительности.

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

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

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

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