Разделите на 9 без использования оператора деления или умножения

Question

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

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

Answer 1

Вот решение сильно вдохновлен Hacker's Delight, что на самом деле использует только битовые сдвиги:

def divu9(n): 
    q = n - (n >> 3) 
    q = q + (q >> 6) 
    q = q + (q>>12) + (q>>24); q = q >> 3 
    r = n - (((q << 2) << 1) + q) 
    return q + ((r + 7) >> 4) 
    #return q + (r > 8) 

Answer 2

Этот алгоритм http://en.wikipedia.org/wiki/Ancient_Egyptian_multiplication может сделать это, используя только вычитание и двоичные сдвиги в log (n) времени. Однако, насколько я знаю, современные аппаратные средства уже используют этот или даже лучшие алгоритмы. Поэтому я не думаю, что вы можете что-то сделать (предполагая, что производительность - это ваша цель), если вы не можете каким-то образом полностью отказаться от разделения или изменить свой прецедент, чтобы вы могли делиться силой 2, потому что есть некоторые трюки для этих случаев.

Answer 3

Смотрите этот ответ: https://stackoverflow.com/a/11694778/4907651

Именно то, что вы ищете, кроме делителя 3.

EDIT: объяснение

заменит функцию add с просто +, как вы «искать решение без использования * или /.

В этом объяснении мы предполагаем, что мы делим на 3.

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

int divideby3 (int num) { 
    int sum = 0; 
    while (num > 3) { 
     sum += (num >> 2); 
     num = (num >> 2) + (num & 3); 
    } 
    if (num == 3) 
     sum += 1; 
    return sum; 
} 

Этот подход использует битовые операторы:

• побитовое И: &.
• Побитовый сдвиг влево: <<. Сдвигает двоичные значения.
• Побитовый сдвиг вправо: >>. Сдвигает двоичные значения вправо.
• побитовое исключающее ИЛИ: ^

Первое условие (num > 3) как таковой, потому что делитель 3. В вашем случае, делитель 9, поэтому, когда вы используете его, то условие должно быть (num > 9).

Пусть число, которое мы хотим разделить это 6.

В двоичном, 6 представлена ​​в виде 000110.

Теперь мы вводим петлю while (num > 3). В первом заявлении добавляется sum (инициализировано до 0) до num >> 2.

Что num >> 2 делает:

Num в двоичном первоначально: 00000000 00000110

после побитового сдвига: 00000000 00000001 i.e. 1 in decimal

sum после добавления num >> 2 является 1.

Поскольку мы знаем, что num >> 2 равно 1, добавьте это к num & 3.

Num в двоичной системе изначально: 00000000 00000110

3 в двоичной системе: 00000000 00000011

Для каждой битовой позиции в результате экспрессии a & b, бит равен 1, если оба операнда содержат 1, и 0 в противном случае

результат num & 3: 00000000 00000010 i.e. 2 in decimal

num после num = (num >> 2) + (num & 3) равна 1 + 2 = 3

Теперь, так как num равно 3, мы входим в if (num==3) петлю.

Затем мы добавляем 1 к сумме и возвращаем значение. Это значение sum является частным.

Как и следовало ожидать, возвращаемое значение равно 2.

Надежда, что не было ужасное объяснение.

Answer 4

Создать петлю и каждый шаг, который вы должны вычитать N-9 .. затем (N-9)-9 .. до N<9 OR N=0 и каждое вычитание вы посчитайте шаг для Exemple: 36/9 36-9=27 cmpt (1) 27-9=18 cmpt(2) 18-9=9 cmpt(3) 9-9=0 cmpt (4)

Так 36/9= 4

Answer 5

Если вам нужно разделить положительное число, вы можете использовать следующую функцию:

unsigned int divideBy9(unsigned int num) 
{ 
    unsigned int result = 0; 
    while (num >= 9) 
    { 
     result += 1; 
     num -= 9; 
    } 
    return result; 
} 

В случае отрицательного номера вы можете использовать аналогичный подход.

Надеюсь, это поможет!

Answer 6

Если вам не разрешено размножаться/делить, вы остаетесь с добавлением/вычитанием. Разделение на число показывает, сколько раз делитель содержит дивиденд. Вы можете использовать это взамен: сколько раз вы можете вычесть число из исходного значения?

divisor = 85; 
dividend = 9; 
remaining = divisor; 
result = 0; 
while (remaining >= dividend) 
{ 
    remaining -= dividend; 
    result++; 
} 
std::cout << divisor << "/" << dividend << " = " << result; 

Answer 7

Хотя ответ был принят, я отправляю мое для чего это стоит.

ОБНОВЛЕНИЕ. Это работает путем умножения на повторяющуюся двоичную дробь. В десятичном значении 1/9 = 0,1111111 повторяется. В двоичном, это 1/1001 = 0.000111000111000111 повторяющийся.

Обратите внимание, что бинарный множитель находится в группах по 6 бит, десятичный 7 повторяющийся. Итак, что я хочу сделать здесь, это умножить дивиденд на 7, сдвинуть его на 6 бит и добавить его к текущему коэффициенту. Однако, чтобы сохранить значение, я делаю смену после с добавлением и сдвигаю фактор q после того, как концы цикла закончатся.

Существует до 6 итераций цикла вычисления для 32 бит int (6 бит * 6 сдвигов = 36 бит).

#include<stdio.h> 

int main(void) 
{ 
    unsigned x, y, q, d; 
    int i, err = 0; 

    for (x=1; x<100; x++) {    // candidates 
     q = 0;       // quotient 
     y = (x << 3) - x;    // y = x * 7 

     while(y) {      // until nothing significant 
      q += y;      // add (effectively) binary 0.000111 
      y >>= 6;     // realign 
     } 
     q >>= 6;      // align 

     d = x/9;      // the true answer 
     if (d != q) { 
      printf ("%d/9 = %d (%d)\n", x, q, d);  // print any errors 
      err++; 
     } 
    } 

    printf ("Errors: %d\n", err); 
    return 0; 
} 

К сожалению, это не выполняется для каждого кандидата, который является кратным 9, для ошибок округления, по той же причине, что умножение десятичного 27 * 0.111111 = 2.999999, а не 3. Так что я теперь усложнять ответ, сохраняя 4 ls бит частного для округления. В результате он работает для всех значений int, ограниченных двумя верхними полубайтами, один для * 7 и один для значения * 16. .

#include<stdio.h> 

int main(void) 
{ 
    unsigned x, y, q, d; 
    int i, err = 0; 

    for (x=1; x<0x00FFFFFF; x++) { 
     q = 8;       // quotient with (effectively) 0.5 for rounding 
     y = (x << 3) - x;    // y = x * 7 
     y <<= 4;      // y *= 16 for rounding 

     while(y) {      // until nothing significant 
      q += y;      // add (effectively) binary 0.000111 
      y >>= 6;     // realign 
     } 
     q >>= (4 + 6);     // the 4 bits significance + recurrence 

     d = x/9;      // the true answer 
     if (d != q) { 
      printf ("%d/9 = %d (%d)\n", x, q, d);  // print any errors 
      err++; 
     } 
    } 

    printf ("Errors: %d\n", err); 
    return 0; 
}