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

Question

Можно ли разделить целое число без знака на 10, используя чистые битовые сдвиги, сложение, вычитание и возможно умножение?Использование процессора с очень ограниченными ресурсами и медленным делением.

Answer 1

Вот что делает компилятор Microsoft при компиляции делений по маленьким интегральным константам.Предположим, что 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

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

Answer 2

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

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

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

Answer 3

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

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

Answer 4

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

Допустим, мы должны найти 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 могут быть предварительно вычислены как константы.

Answer 5

На архитектурах, которые могут смещаться только на одно место за раз, ряд явных сравнений с уменьшением степени двойки, умноженным на 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;
}

Answer 6

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

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

Answer 7

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

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