Перевод натурального числа в двоичную систему счисления и обратно

Не совсем олимпиадная задача, но все же я подробно остановлюсь на ней, так как есть несколько вариантов решения этой задачи.
Известно, что остатки от деления на 2 дают цифры в двоичной системе.
Например, дано число 19:
19: 2 = 9 целых 1 в остатке
  9: 2 = 4 целых 1 в остатке
  4: 2 = 2 целых 0 в остатке
  2: 2 = 1 целых 0 в остатке
  1: 2 = 0 целых 1 в остатке
дальнейшие действия бесполезны: на ноль делим - получим ноль целых и ноль в остатке.
Для получения итогового числа собираем остатки с конца, получим: 10011
Итак, мы видим цикличность действий и условие останова (окончания цикла).
Запишем через переменные:
а - исходное число и число, которое делим на 2
с - остаток от деления
а=0 - условие останова
вывод цифр будем осуществлять в строку.

Напишем часть кода:

s:=''; readln(a);

while not (a=0) do 

begin

   a := a div 2;

   c := a mod 2;

   if  c=0 then s:=s+'0' else s:=s+'1';

end;

writeln(s);

По нашему мнению это правильно. Но давайте проверим:
Введем а = 19, т.к. a не равно 0 идем выполнять тело цикла:
a = a div 2 = 19 div 2 = 9
c = a mod 2 = 1 mod 2 =1
Что получается? Изменилось значение переменной а сразу после первого оператора присваивания! Возникает вопрос: а если поменять местами два оператора, что изменится?
c = a mod 2 = 19 mod 2 = 1
a = a div 2 = 19 div 2 =9
Что и требовалось в итоге.
Перепишем код программы:

s:=''; readln(a);

while not (a=0) do 

begin

   c := a mod 2; 

   a := a div 2;

   if  c=0 then s:=s+'0' else s:=s+'1';

end;

writeln(s);

Теперь посмотрим как собирается строка:
так как остаток равен 1, то выполнится оператор после слова else:
s=s+'1' =''+ '1'='1'

Переходим к началу цикла и проверяем условие продолжения цикла (т.е. отрицание условия останова): a<>0 (9<>0) и выполняем тело цикла:

c = a mod 2 = 9 mod 2 = 1
a = a div 2 = 9 div 2 = 4
s=s+'1'='1'+'1'='11'

Продолжим выполнение до выхода из цикла:

c = a mod 2 = 4 mod 2 = 0
a = a div 2 = 4 div 2 = 2

s=s+'0'='11'+'0'='110'

Стоп! Но ведь в результате стоит все наоборот: 10011, а не как у нас 110! Это потому что мы присоединяем цифры справа, а не слева полученной строки. Изменим оператор:
if  c=0 then s:='0'+s else s:='1'+s;

До этого все было нормально, теперь с измененным оператором
s='0'+s='0'+'11'='011'
И так далее.

Теперь рассмотрим второй вариант: используя операции shl и  shr - битовые сдвиги влево и вправо. Число 19 в двоичной системе и в памяти компьютера 00010011. Операция битового сдвига выглядит так:
19 shl 1 = [00100110]
19 shr 1 = [00001001]
Чтобы отличать десятичное число от двоичного представления, последнее заключим в квадратные скобки. Что мы имеем? При сдвиге влево все биты сдвигаются влево и добавляется 0 справа, а при сдвиге вправо все биты сдвигаются вправо, теряя 1 младший разряд, и добавляется 0 слева. Что нам это дает? Если сделаем сдвиг вправо, потом влево, то получим число без единицы, т.е. если вычитаем результат битовых операций из исходного числа, то получим младший разряд в двоичном представлении числа:
c:=a - (a shr 1) shl 1 = [00010011] - (19 shr 1) shl 1 = [00010011] - [00001001] shl 1 =
= [00010011] - [00010010] = 1.
Для дальнейшей работы нужно изменить переменную, используя операцию сдвига вправо:
a:=a shr 1 = 19 shr 1 = [00001001].

Получим следующий код программы:

s:=''; readln(a);

while not (a=0) do 

begin

   c :=a - (a shr 1) shl 1; 

   a := a shr 1;

   s:=chr(ord('0')+c)+s;

end;

writeln(s);

Объясню как образуется строчка
s:=chr(ord('0')+c)+s;
Цифры в таблице ASCII стоят по порядку от '0' до '9', поэтому, зная код нуля ord('0') и прибавляя нужное число C, можно получить символ, соответствующий этому числу.

В случае, если число достаточно большое, то используйте работу с вещественными числами (например, тип comp - у него нет дробных чисел) или длинную арифметику.

Теперь рассмотрим  обратный процесс:
 10011=1*2^4+0*2^3+0*2^2+1*2^1+1*2^0
Пусть число хранится в строке S. Тогда, зная длину строки, можно перебирать все символы строки по очереди и  выполнять умножение и сложение. Нули можно не учитывать в сложении. Но как получить степень двойки? Мы уже этот вопрос разбирали, когда обсуждали тему циклы:
p:=1;
for i:=1 to n do p:=p*2;

где n - степень числа. Но можно каждый раз не вычислять степень, а только домножать на 2 и складывать степени. Только нужно учесть в этом случае, что первым будет нулевая степень, следовательно числа нужно считывать из строки в обратном порядке:

Readln(S); 

p:=1; 

a:=0;

for i:=length(s) to 1 do

  if s[i]='1' then  a:=a+p;

  p:=p*2;

end;

writeln(a);

Вместо умножения на 2 можно использовать операцию битового сдвига влево на 1 бит:
  p:=p shl 1;
Действительно,
1 shl 1 =10 =2
2 shl 1 = 100 = 4
4 shl 1 =1000 = 8 и т. д.

Другой способ получить десятичное число - использовать схему умножения Горнера:
10011=1*2^4+0*2^3+0*2^2+1*2^1+1*2^0 = 1+2*(1+2*(0+2*(0+2*1)))
Построим рекуррентную формулу, начиная с самой первой вложенной скобки:

a=1*2+0=0+2*1
a=a*2+0=0+2*(0+2*1)
a=a*2+1=1+2*(0+2*(0+2*1))
a=a*2+1=1+2*(1+2*(0+2*(0+2*1)))
Если в начале взять a=0, то получим цикличный алгоритм:
a=a*2+1
a=a*2+0
a=a*2+0
a=a*2+1
a=a*2+1
Получили тело цикла: a:=a*2+c; где с-числовое представление символа '0' или '1'. Зная правила кодирования символов, для получения цифры из символа , воспользуемся следующим преобразованием:
с:=ord(S[i]) - ord('0');
Объясню еще раз: символы цифр в таблице ASCII стоят подряд:
'0' - допустим у нуля десятичный код 87
'1' - тогда у единицы код 88
'2' - у двойки код 89
... - и т.д.
Если знаем код числа и нуля - вычитаем и получаем соответствующую цифру:
ord('0') - ord('0') =  88-88 =0
ord('1') - ord('0') =  88-87 =1
ord('2') - ord('0') =  89-87 =2
и т.д.

Запишем код программы:

Readln(S); 

zero:=ord('0'); 

a:=0;

for i:=1 to length(s) do

  a:=a shl 1 + ord(S[i]) - zero;

end;

writeln(a);

Элегантно и просто, не правда ли?

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