проверить делимость на 13 двоичного числа

Как проверить, делится ли двоичное число на 13, если пользователь вводит цифры от старшего к младшему?

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

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

как к этому подойти?
пример:

110010000100100
это делится на 13

111111111111111
не делится на 13

0

Решение

Вот алгоритм O (N):

Пройдите биты слева направо. Каждая дополнительная позиция эквивалентна умножению текущего значения на 2, а затем добавлению 0 или 1. Это также верно в арифметике по модулю 13. Когда вы доберетесь до последнего бита, посмотрите, равно ли конечное значение 0. Если это так, то исходное число делится на 13.

3

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector