вторник, 5 апреля 2011 г.

Перевод целых чисел из десятичной системы счисления в двоичную


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

Двоичная система счисления — это позиционная система счисления с основанием 2. В этой системе счисления числа записываются с помощью двух символов (1 и 0).
Сначала, немного применения:

Двоичная система используется в цифровых устройствах, поскольку является наиболее простой и соответствует требованиям:
*-Нравится статья? Кликни по рекламе! :)

  • Чем меньше значений существует в системе, тем проще изготовить отдельные элементы, оперирующие этими значениями. В частности, две цифры двоичной системы счисления могут быть легко представлены многими физическими явлениями: есть ток (ток больше пороговой величины) — нет тока (ток меньше пороговой величины), индукция магнитного поля больше пороговой величины или нет (индукция магнитного поля меньше пороговой величины) и т. д.
  • Чем меньше количество состояний у элемента, тем выше помехоустойчивость и тем быстрее он может работать. Например, чтобы закодировать три состояния через величину напряжения, тока или индукции магнитного поля, потребуется ввести два пороговых значения и два компаратора, что не будет способствовать помехоустойчивости и надёжности хранения информации.
  • Двоичная арифметика является довольно простой. Простыми являются таблицы сложения и умножения — основных действий над числами.
В цифровой электронике одному двоичному разряду в двоичной системе счисления соответствует (очевидно) один двоичный разряд двоичного регистра, то есть двоичный триггер с двумя состояниями (0,1).
Общеизвестный алгоритм получения двоичного числа из десятичного можно описать следующим образом:

1. Исходное десятичное число делится на два (основание двоичной системы счисления).
2. В одну переменную записывается частное в виде целого числа, в другую – остаток в виде строки (если остатка нет, то записывается ноль).
3. Если частное не было равно нулю, то оно снова делится на два. Переменная, связанная со старым частным связывается с новым (прежнее частное теряется). Новый остаток с помощью операции конкатенации добавляется в начало строковой переменной, где хранятся остатки.
4. П. 3 продолжает повторяться до тех пор, пока частное не станет равно нулю.
5. Остатки от деления, записанные в обратном порядке, представляют собой двоичное представление заданного десятичного числа.

def IntToByte(x):
    n = "" if x>0 else "0"
    while x > 0:
        y = str(x % 2)
        n = y + n
        x = int(x / 2)
    print (n)

Другой же алгоритм, несколько излишний, т.к. ему нужно пройтись по всем разрядам
int числа(или другого типа, но тогда нужно будет брать другое число за основание).
Идея состоит в применении операции конъюнкции.
Конъюнкция — это функция двух, трёх или более переменных (они же —
операнды операции, они же — аргументы функции). Переменные могут
принимать значения из множества ~\{0, 1\}. Результат также принадлежит множеству ~\{0, 1\}.  Вычисление результата производится по простому правилу, либо по таблице истинности. Вместо значений ~0, 1 может использоваться любая другая пара подходящих символов, например ~false, true или ~F, T или "ложь", "истина".
Правило: результат равен ~1, если все операнды равны ~1;
во всех остальных случаях результат равен ~0.

2-й метод:
Т.к. тип int это 4 байта = 32 бита, то нужно взять число 10000000000000000000000000000000, что в 10-й равно 2147483648(а в 16-й 0x80000000) и применить операцию конъюнкции к этому числу и тому, что нужно перевести в 2-й вид. Исходя из вышеописаного св-ва этой магической операции, результатом конъюнкции может быть 0, только если у искомого числа в 1-м разряде стоит 0(1 разряд - это место, соответствующее 1 у числа 2147483648). После этого, мы делаем сдвиг вправо, числа 2147483648(т.е. делим его на 2) и получаем 01000000000000000000000000000000 и повторяем операцию конъюнкции, которая теперь даст нам 0, если стоит 0 у исходного числа во 2-м разряде и т.д.

Теперь код:
def IntToByte(n):
    b = 2147483648;
    str=''
    while b > 0:
        z = n & b;
        if z == 0:
             str=str+'0'
        else:
             str=str+'1'
        b = b >> 1;
    print str
Соответственно, если число больше int, то основание выбираем больше 2147483648.
Сравнив выводы ф-ий, например для числа 200:
  1. 11001000
  2. 00000000000000000000000011001000
Видим, что 2-я ф-ия  делает больше действий(лишних, проходит по всем разрядам), но это св-во конъюнкции может пригодиться, так что я считаю, что это наглядный пример.

Используемая литература:
http://younglinux.info/algorithm/binary
Двоичная система счисления
Конъюнкция