Divisiblity of 5 без использования% и/оператора

Ответ 1

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

В частности, вы можете следить за прикрепленным сообщением, чтобы использовать следующую стратегию. Сначала "разделить на 5" с использованием умножения и бит-сдвигов:

 int32_t div5(int32_t dividend) {
     int64_t invDivisor = 0x33333333;
     return 1 + (int32_t) ((invDivisor * dividend) >> 32);
 }

Затем возьмем результат и умножим на 5:

int result = div5(dividend) * 5;

Тогда result == dividend, если и только dividend делится на 5.

if(result == dividend) {
    // dividend is divisible by 5
}
else {
    // dividend is not divisible by 5
}

Ответ 2

Есть две причины, по которым я могу видеть такой алгоритм: (1) домашнее задание или (2) написать эффективный код для микроконтроллера, который не имеет эффективных инструкций разделения. Предполагая, что ваша причина вторая, но учитывая, что она может быть первой, я не дам вам полного решения, но предположим, что если вы разделите свой номер на куски, которые кратно четырем битам каждый, сумма всех этих кусков будет делиться на пять, только если исходное число было; обратите внимание, что при выполнении таких вычислений вы должны либо избегать переполнения, либо добавить к вашему результату количество переполнений, которые произошли. Я не знаю эффективного способа сделать последнее на C, но на многих машинных языках это легко. В качестве простого примера, на 8051, если у него было 32-битное целое число, можно было бы что-то вроде:

    mov a,Number   ; Byte 0
    add a,Number+1 ; Byte 1
    adc a,Number+2 ; Byte 2, plus carry from last add
    adc a,Number+3 ; Byte 3, plus carry from last add
    adc a,#0       ; Add in carry, if any (might overflow)
    adc a,#0       ; Add in carry, if any (can't overflow)

Обратите внимание, что в машинный код добавление возвращаемого числа в число намного быстрее, чем выполнение 16-разрядной математики.

Как только значение было уменьшено до диапазона 0-255, можно добавить верхние четыре бита в младшие 4 бита, чтобы получить значение в диапазоне от 0 до 30. Можно было либо проверить на семь таких значений, которые кратным пяти, или работать для уменьшения количества возможных значений [eg если значение не менее 15, вычесть 15; если не менее 10, вычесть 10; если 5, вычесть пять; если ноль, он кратен пяти].

Ответ 3

Обозначим число в базе 2. Имеем:

abcdefgh*101 = ABCDEFGHIJ

или

+abcdefgh00
+  abcdefgh
 ----------
 ABCDEFGHIJ

Нам присваивается ABCDEFGHIJ и мы хотим найти abcdefgh.

Если вы поочередно - и + abcdefgh со своим последовательным правдоповтором, вы получите...

+  ABCDEFGH
-    ABCDEF
+      ABCD
-        AB
-----------
+  abcdefgh
+    abcdef
-    abcdef
-      abcd
+      abcd
+        ab
-        ab
-----------
   abcdefgh

Ответ!

Ответ 4

Наконец-то он разблокирован, поэтому я могу объяснить свой комментарий, который, кстати, получается для генерации лучшего кода, чем GCC для x % 5 == 0. См. здесь, заполните

#include <stdint.h>
bool divisible_by_5(uint32_t x)
{
   return x % 5 == 0;
}
bool divisible_by_5_fast(uint32_t x)
{
   return x * 0xCCCCCCCD <= 0x33333333;
}

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

0xCCCCCCCD является модульным мультипликативным обратным 5, по модулю 2 ³². Умножение кратного k (например, n * k) на (модульное) мультипликативное обратное эквивалентно делению на k, поскольку

(n * k) * inv(k) =
// use associativity
n * (k * inv(k)) =
// use definition of multiplicative inverse
n * 1 =
// multiplicative identity
n

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

Так как умножение на нечетное число обратимо и на самом деле является биекцией, оно не может отображать любые не кратные k в диапазон 0 - (2 ³² -1)/k.

Поэтому, когда он выходит за пределы этого диапазона, он не может быть кратным k.

0x33333333 есть (2 ³² -1)/5, поэтому, если x * 0xCCCCCCCD выше, x не может быть кратным 5.

Ответ 5

Добавьте все байты и проверьте (по таблице), если сумма делится на 5.

Ответ 6

Сохраняйте вычитание кратным 5, например 50, 500, 100 и т.д. Начните с больших чисел. Если результат идет отрицательным, то вычитайте с меньшим номером числа, пока не достигнете 0. В противном случае число не делится.

Ответ 7

bool trythis(int number){
  Int start = number;
  Do{
    start = start - 5;
  } while (start > 5)

  If (start == 5 || start == 0) {
    Return true;
  } else return false;
}

Ответ 8

Typecast или конвертировать в строку, а затем посмотреть, является ли последний символ 5 или 0.