Алгоритм модификации блока на процессоре без оператора деления

Я могу придумать два возможных подхода. Поскольку это домашнее задание, я просто упомяну их и позволю вам поработать, если они осуществимы и как их реализовать:

1. A / B = 2 ^ (log2 (A) -log2 (b)): Если вы можете получить логарифм значений, вы можете точно аппроксимировать деление.

2. Двоичное деление в столбик: Вы узнали, как выполнять десятичное деление в столбик, прежде чем научились делать деление, верно? Так что научите свой компьютер выполнять двоичное деление в столбик (на самом деле это должно быть проще в двоичном формате).

(edit: исправлено №1., Уравнение логарифмического деления)

Это не дает прямого ответа на ваш вопрос, но, тем не менее, это интересный случай. Если число модулируется степенью двойки, операция может выполняться как

x % 2^n = x & (2^n - 1)

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

Дополнительная информация В Википедии

Похоже, что вычитание (или добавление, если a отрицательно) на b до тех пор, пока вы не достигнете или не пересечете 0, было бы простой реализацией, хотя почти наверняка не самой эффективной.

Jweede, я понятия не имел, как решить вашу проблему, но я нашел похожее сообщение здесь .

A / B = Q, поэтому A = B * Q. Мы знаем как A, так и B, мы хотим Q.

Моя идея добавить в смесь: Бинарный поиск Q. Начните с Q = 0 и Q = 1, возможно, в качестве базовых случаев. Продолжайте удваивать, пока B * Q> A, и тогда у вас будет две границы (Q и Q / 2), поэтому найдите правильный Q между двумя из них. O (log (A / B)), но немного сложнее реализовать:

#include <stdio.h>
#include <limits.h>
#include <time.h>

// Signs were too much work.
// A helper for signs is easy from this func, too.
unsigned int div(unsigned int n, unsigned int d)
{
    unsigned int q_top, q_bottom, q_mid;
    if(d == 0)
    {
        // Ouch
        return 0;
    }

    q_top = 1;
    while(q_top * d < n && q_top < (1 << ((sizeof(unsigned int) << 3) - 1)))
    {
        q_top <<= 1;
    }
    if(q_top * d < n)
    {
        q_bottom = q_top;
        q_top = INT_MAX;
    }
    else if(q_top * d == n)
    {
        // Lucky.
        return q_top;
    }
    else
    {
        q_bottom = q_top >> 1;
    }

    while(q_top != q_bottom)
    {
        q_mid = q_bottom + ((q_top - q_bottom) >> 1);
        if(q_mid == q_bottom)
            break;

        if(d * q_mid == n)
            return q_mid;
        if(d * q_mid > n)
            q_top = q_mid;
        else
            q_bottom = q_mid;
    }
    return q_bottom;
}

int single_test(int n, int d)
{
    int a = div(n, d);
    printf("Single test: %u / %u = %u\n", n, d, n / d);
    printf(" --> %u\n", a);
    printf(" --> %s\n", a == n / d ? "PASSED" : "\x1b[1;31mFAILED\x1b[0m");
}

int main()
{
    unsigned int checked = 0;
    unsigned int n, d, a;

    single_test(1389797028, 347449257);
    single_test(887858028, 443929014);
    single_test(15, 5);
    single_test(16, 4);
    single_test(17, 4);
    single_test(0xFFFFFFFF, 1);

    srand(time(NULL));

    while(1)
    {
        n = rand();
        d = rand();

        if(d == 0)
            continue;

        a = div(n, d);
        if(n / d == a)
            ++checked;
        else
        {
            printf("\n");
            printf("DIVISION FAILED.\n");
            printf("%u / %u = %u, but we got %u.\n", n, d, n / d, a);
        }

        if((checked & 0xFFFF) == 0)
        {
            printf("\r\x1b[2K%u checked.", checked);
            fflush(stdout);
        }
    }

    return 0;
}

Кроме того, вы также можете перебирать биты, устанавливая для каждого из них значение 1. Если B * Q <= A истинно, оставьте бит как 1, иначе обнулить. Выполните MSB-> LSB. (Однако вы должны быть в состоянии обнаружить это переполнение B * Q.

Всем спасибо за совет!

Я начал использовать алгоритм простого деления на повторное вычитание, чтобы реализовать это. Но, как указывает ysth, есть гораздо более простой способ. Вот первый алгоритм:

        .macro mod a, b, r
        mov a, r
divlp:  sub r, b, r
        cmp r, b
        bge divlp
        .endmacro

Он очень похож на:

mod(a, b){
   int r = a
   while(r >= b){
      r = r - b
   }
   return r
}