Проверить, является ли двоичное представление числа палиндромом

Формулировка. Дано число типа byte. Проверить, является ли палиндромом его двоичное представление с учетом того, что сохранены старшие нули. Пример таких чисел: 102 (т. к. 102 = 0110 01102, а это палиндром), 129 (129 = 1000 00012) и т. д.

Решение. Данная задача частично повторяет задачу 9. Сходство состоит в том, что и там, и здесь у проверяемых чисел фиксированная разрядность (длина), ведь здесь нам уже задан тип и получено указание сохранить старшие нули, так что в данном случае двоичные представления всех подаваемых на вход программе чисел будут восьмизначными.

Но как же упростить решение, чтобы не делать сравнение всех разрядов «в лоб»? Для этого нам нужно вспомнить правило, упомянутое в задаче 6, на этот раз несколько уточненное и дополненное:

– Остаток от деления любого числа x в системе счисления с основанием p на само число p дает нам крайний справа разряд числа x.

– Умножение любого числа x в системе счисления с основанием p на само число p добавляет числу x новый разряд справа.

Для примера возьмем число 158 в десятичной системе счисления. Мы можем получить его крайнюю цифру справа, которая равна 8, если возьмем остаток от деления 158 на число 10, являющееся в данном случае основанием системы счисления. С другой стороны, если мы умножим 158 на 10, то появляется новый разряд справа, и в результате мы получаем число 1580.

Согласно правилу те же самые арифметические законы актуальны и для двоичной системы счисления. А это в свою очередь означает, что мы можем разработать алгоритм наподобие того, который использовался в задаче 9 для формирования числа, представляющего собой правую половину исходного числа, которая записана в реверсном порядке. Для этого нам нужно использовать четыре переменных для хранения двоичных разрядов правой половины двоичной записи введенного числа, добыть эти самые разряды с удалением их в исходном числе, сформировать из них двоичную реверсную запись и выполнить сравнение. Обозначим эти переменные типа byte как a, b, c, и d.

Опишем сам алгоритм:

  1. Вводим число n;
  2. Последовательно получаем 4 крайних справа разряда двоичной записи числа n: присваиваем их значение соответствующей переменной, а затем отбрасываем в исходном числе: 
    a := n mod 2;
n := n div 2;
b := n mod 2;
n := n div 2;
c := n mod 2;
n := n div 2;
d := n mod 2;
n := n div 2;
  3. Теперь нужно подумать, как видоизменится формула, с помощью которой мы получали реверсную запись числа взадаче 5 и задаче 9. Очевидно, что в десятичной системе счисления реверсную запись четырехзначного числа, разряд единиц которого находится в переменной k, разряд десятков – в переменной l, сотен – в m и тысяч – в n мы можем найти по следующей формуле (x в данной случае – любая переменная типа word): 
    x := 1000 * k + 100 * l + 10 * m + n;

    Можно представить, что мы формируем четыре числа, которые затем складываем. Первое число 1000 * k – это разряд единиц исходного числа, к которому справа приписано три разряда (три нуля), то есть, трижды произведено умножение на основание системы счисления 10, проще говоря, число k умножено на 103. Аналогично, к l нужно приписать два нуля, к m – один ноль, а n оставить без изменения, так как эта цифра будет находиться в разряде единиц формируемого «перевертыша». Вспомнив правило, высказанное немного выше, преобразуем предыдущую формулу для двоичной системы счисления (будем умножать цифры на двойку в соответствующих степенях). Она получится такой (для формирования числа используется переменная a):

    a := 8 * a + 4 * b + 2 * c + d;
  4. После применения вышеприведенной строки останется лишь вывести на экран результат сравнения полученных чисел: 
    writeln(n = a);

Код:

  1. program BinaryPalindrome;
  3. var
  4. n, a, b, c, d: byte;
  6. begin
  7. readln(n);
  8. a := n mod 2;
  9. n := n div 2;
  10. b := n mod 2;
  11. n := n div 2;
  12. c := n mod 2;
  13. n := n div 2;
  14. d := n mod 2;
  15. n := n div 2;
  16. a := 8 * a + 4 * b + 2 * c + d;
  17. writeln(n = a)
  18. end.

Выполним «ручную прокрутку» программы при вводе числа 102. Покажем в таблице, какие значения будут принимать переменные после выполнения соответствующих строк (операторов) кода. Значения переменных для наглядности представлены как в десятичной, так и в двоичной системе счисления (при этом дописаны старшие нули до заполнения тетрады). При этом прочерк означает, что значение переменных на данном шаге не определено, а красным цветом выделены переменные, которые изменяются:

№ строки Десятичная система Двоичная система
n a b c d n a b c d
7 102 — — — — 0110 0110 — — — —
8 102 0 — — — 0110 0110 0000 — — —
9 51 0 — — — 0011 0011 0000 — — —
10 51 0 1 — — 0011 0011 0000 0001 — —
11 25 0 1 — — 0001 1001 0000 0001 — —
12 25 0 1 1 — 0001 1001 0000 0001 0001 —
13 12 0 1 1 — 0000 1100 0000 0001 0001 —
14 12 0 1 1 0 0000 1100 0000 0001 0001 0000
15 6 0 1 1 0 0000 0110 0000 0001 0001 0000
16 6 6 1 1 0 0000 0110 0110 0001 0001 0000