Разделить на 10 с помощью битового сдвига?

Примечание редактора: это не, на самом деле компиляторы, а дает неправильный ответ для больших положительных целых чисел, оканчивающихся на 9, начиная с div10(1073741829) = 107374183, а не с 107374182. Это точно для меньших входных данных, хотя этого может быть достаточно для некоторых применений.

Компиляторы (включая MSVC) действительно используют мультипликативные инверсии с фиксированной точкой для постоянных делителей, но они используют другую магическую константу и сдвигают результат с высокой половиной, чтобы получить точный результат для всех возможных входов, соответствующий тому, что требуется абстрактной машине C. См. статью Гранлунда и Монтгомери об алгоритме.

См. Почему GCC использует умножение странным числом при реализации целочисленного деления? на примерах реальных x86 asm gcc, clang, MSVC, ICC и других современных компиляторов.

Это быстрое приближение, которое неточно для больших входных данных.

Это даже быстрее, чем точное деление через умножение + сдвиг вправо, которое используют компиляторы.

Вы можете использовать высокую половину результата умножения для деления на малые интегральные константы. Предположим, что на 32-битной машине (код может быть скорректирован соответствующим образом):

int32_t div10(int32_t dividend)
{
    int64_t invDivisor = 0x1999999A;
    return (int32_t) ((invDivisor * dividend) >> 32);
}

Здесь мы умножаем на близкое приближение 1/10 * 2 ^ 32, а затем удаляем 2 ^ 32. Этот подход можно адаптировать к разным делителям и разной разрядности.

Это отлично работает для архитектуры ia32, поскольку ее инструкция IMUL помещает 64-битный продукт в edx: eax, а значение edx будет желаемым значением. Визуализация (предполагается, что дивиденды передаются в EAX, а частное возвращается в EAX)

div10 proc 
    mov    edx,1999999Ah    ; load 1/10 * 2^32
    imul   eax              ; edx:eax = dividend / 10 * 2 ^32
    mov    eax,edx          ; eax = dividend / 10
    ret
    endp

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

Хотя приведенные до сих пор ответы соответствуют фактическому вопросу, они не соответствуют названию. Итак, вот решение, в значительной степени вдохновленное Hacker's Delight, который действительно использует только битовые сдвиги.

unsigned divu10(unsigned n) {
    unsigned q, r;
    q = (n >> 1) + (n >> 2);
    q = q + (q >> 4);
    q = q + (q >> 8);
    q = q + (q >> 16);
    q = q >> 3;
    r = n - (((q << 2) + q) << 1);
    return q + (r > 9);
}

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

Конечно, можете, если можете жить с некоторой потерей точности. Если вы знаете диапазон значений ваших входных значений, вы можете придумать битовый сдвиг и точное умножение. Некоторые примеры, как вы можете разделить на 10, 60, ... как это описано в этом блоге для формата самый быстрый способ.

temp = (ms * 205) >> 11;  // 205/2048 is nearly the same as /10

чтобы немного расширить ответ Алоиса, мы можем расширить предлагаемый y = (x * 205) >> 11 еще на несколько кратных / смен:

y = (ms *        1) >>  3 // first error 8
y = (ms *        2) >>  4 // 8
y = (ms *        4) >>  5 // 8
y = (ms *        7) >>  6 // 19
y = (ms *       13) >>  7 // 69
y = (ms *       26) >>  8 // 69
y = (ms *       52) >>  9 // 69
y = (ms *      103) >> 10 // 179
y = (ms *      205) >> 11 // 1029
y = (ms *      410) >> 12 // 1029
y = (ms *      820) >> 13 // 1029
y = (ms *     1639) >> 14 // 2739
y = (ms *     3277) >> 15 // 16389
y = (ms *     6554) >> 16 // 16389
y = (ms *    13108) >> 17 // 16389
y = (ms *    26215) >> 18 // 43699
y = (ms *    52429) >> 19 // 262149
y = (ms *   104858) >> 20 // 262149
y = (ms *   209716) >> 21 // 262149
y = (ms *   419431) >> 22 // 699059
y = (ms *   838861) >> 23 // 4194309
y = (ms *  1677722) >> 24 // 4194309
y = (ms *  3355444) >> 25 // 4194309
y = (ms *  6710887) >> 26 // 11184819
y = (ms * 13421773) >> 27 // 67108869

каждая строка представляет собой отдельный независимый расчет, и вы увидите свою первую «ошибку» / неверный результат в значении, указанном в комментарии. вам обычно лучше брать наименьший сдвиг для данного значения ошибки, так как это минимизирует дополнительные биты, необходимые для хранения промежуточного значения в вычислении, например (x * 13) >> 7 "лучше", чем (x * 52) >> 9, так как требует на два бита меньше накладных расходов, в то время как оба начинают давать неправильные ответы выше 68.

если вы хотите вычислить больше из них, можно использовать следующий код (Python):

def mul_from_shift(shift):
    mid = 2**shift + 5.
    return int(round(mid / 10.))

и я сделал очевидную вещь для вычисления, когда это приближение начинает ошибаться:

def first_err(mul, shift):
    i = 1
    while True:
        y = (i * mul) >> shift
        if y != i // 10:
            return i
        i += 1

(обратите внимание, что // используется для "целочисленного" деления, то есть обрезает / округляет до нуля)

Причина появления шаблона "3/1" в ошибках (т.е. 8 повторений 3 раза, за которыми следуют 9), по-видимому, связана с изменением оснований, то есть log2(10) составляет ~ 3,32. если мы построим график ошибок, мы получим следующее:

где относительная погрешность определяется выражением: mul_from_shift(shift) / (1<<shift) - 0.1

На архитектурах, которые могут сдвигать только одно место за раз, серия явных сравнений с уменьшающейся степенью двойки, умноженной на 10, может работать лучше, чем решение формы хакерского удовольствия. Предполагая 16-битное делимое:

uint16_t div10(uint16_t dividend) {
  uint16_t quotient = 0;
  #define div10_step(n) \
    do { if (dividend >= (n*10)) { quotient += n; dividend -= n*10; } } while (0)
  div10_step(0x1000);
  div10_step(0x0800);
  div10_step(0x0400);
  div10_step(0x0200);
  div10_step(0x0100);
  div10_step(0x0080);
  div10_step(0x0040);
  div10_step(0x0020);
  div10_step(0x0010);
  div10_step(0x0008);
  div10_step(0x0004);
  div10_step(0x0002);
  div10_step(0x0001);
  #undef div10_step
  if (dividend >= 5) ++quotient; // round the result (optional)
  return quotient;
}

Учитывая ответ Кубы Обера, есть еще один в том же духе. Он использует итеративную аппроксимацию результата, но я не ожидал никаких удивительных результатов.

Допустим, нам нужно найти x, где x = v / 10.

Мы будем использовать обратную операцию v = x * 10, потому что у нее есть замечательное свойство: когда x = a + b, то x * 10 = a * 10 + b * 10.

Позвольте использовать x как переменную, содержащую наилучшее приближение результата на данный момент. Когда поиск закончится, x сохранит результат. Мы установим каждый бит b из x от наиболее значимого к менее значимому, один за другим, и сравним (x + b) * 10 с v. Если он меньше или равен v, то бит b устанавливается в x. Чтобы проверить следующий бит, мы просто сдвигаем b на одну позицию вправо (делим на два).

Мы можем избежать умножения на 10, удерживая x * 10 и b * 10 в других переменных.

Это дает следующий алгоритм деления v на 10.

uin16_t x = 0, x10 = 0, b = 0x1000, b10 = 0xA000;
while (b != 0) {
    uint16_t t = x10 + b10;
    if (t <= v) {
        x10 = t;
        x |= b;
    }
    b10 >>= 1;
    b >>= 1;
}
// x = v / 10

Изменить: чтобы получить алгоритм Куба Обера, который позволяет избежать использования переменной x10, мы можем вместо этого вычесть b10 из v и v10. В этом случае x10 больше не нужен. Алгоритм становится

uin16_t x = 0, b = 0x1000, b10 = 0xA000;
while (b != 0) {
    if (b10 <= v) {
        v -= b10;
        x |= b;
    }
    b10 >>= 1;
    b >>= 1;
}
// x = v / 10

Цикл можно развернуть, и различные значения b и b10 могут быть предварительно вычислены как константы.

Ну, деление - это вычитание, так что да. Сдвиньте вправо на 1 (разделите на 2). Теперь вычтите 5 из результата, считая, сколько раз вы выполняли вычитание, пока значение не стало меньше 5. Результат - это количество вычитаний, которые вы сделали. Да, и деление, вероятно, будет быстрее.

Гибридная стратегия сдвига вправо и деления на 5 с использованием нормального деления может улучшить производительность, если логика в делителе еще не делает этого за вас.

Я разработал новый метод сборки AVR, только с lsr / ror и sub / sbc. Он делится на 8, затем сутрактирует число, разделенное на 64 и 128, затем вычитает 1024-е и 2048-е, и так далее и так далее. Работает очень надежно (с точным округлением) и быстро (370 микросекунд на 1 МГц). Исходный код для 16-битных чисел находится здесь: http://www.avr-asm-tutorial.net/avr_en/beginner/DIV10/div10_16rd.asm Страница с комментариями к этому исходному коду находится здесь: http://www.avr-asm-tutorial.net/avr_en/beginner/DIV10/DIV10.html Я надеюсь что это помогает, хотя этому вопросу уже десять лет. brgs, gsc

Код комментариев elemakil можно найти здесь: https://doc.lagout.org/security/Hackers%20Delight.pdf стр. 233. Беззнаковое деление на 10 [и 11.]