НГУ

Форумы НГУ
Текущее время: Вт ноя 19, 2019 5:01 am

Часовой пояс: UTC + 7 часов




Начать новую тему Ответить на тему  [ Сообщений: 13 ] 
Автор Сообщение
 Заголовок сообщения: Двоичное сложение, перенос битов
СообщениеДобавлено: Вс окт 30, 2011 1:39 am 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
Допустим, есть у нас абелева группа . Как она устроена - понятно, при желании на ней можно даже ввести умножение и превратить её в поле характеристики .

А теперь будем рассматривать элементы как двочные записи чисел из , считая, что каждый множитель в декартовом произведении представляет значение некоторого бита в фиксированной позиции. И введём на новую операцию , которая складывает элементы как элементы группы в соответствии с обозначенным представлением. Получим опять абелеву группу, причём с тем же нулём, но структура у неё будет уже другая и свойства другие. В некоторых местах, надо заметить, совсем нехорошие.

Вопрос такой: можно ли выразить новую операцию через старую, и наоборот. Кое-что, безусловно, сделать можно: например, взятие противоположного элемента соответсвует вычислению для него двоично-дополнительного кода, так что , где . Но минуса мало, хотелось бы иметь выражение для суммы. Возможно ли это?

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вс окт 30, 2011 4:30 pm 
Не в сети
Начинающий автор

Зарегистрирован: Чт мар 08, 2007 7:29 pm
Сообщения: 246
Откуда: Тюшин Илья
Коба писал(а):
Кое-что, безусловно, сделать можно: например, взятие противоположного элемента соответсвует вычислению для него двоично-дополнительного кода, так что , где .

Я не очень понял эту формулу. Вот, например:
пусть , тогда
а . И что-то ничего не совпадает :-?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вс окт 30, 2011 8:27 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
Cagnaccio писал(а):
Коба писал(а):
Кое-что, безусловно, сделать можно: например, взятие противоположного элемента соответсвует вычислению для него двоично-дополнительного кода, так что , где .

Я не очень понял эту формулу. Вот, например:
пусть , тогда
а . И что-то ничего не совпадает :-?

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

А имелось в виду вот что. Равенство бесспорно. Против него, надеюсь, Вы возражать не будете. Далее, под единицей я понимал набор (то есть набор, задающий двоичное представления единичного элемента в группе , рассматриваемой как кольцо вычетов по модулю ). Ясно, что . Так что, на самом деле, я хотел написать , имея в виду именно "жирную" единицу , но в последний момент потерял перед ней знак минус.

Можно теперь это равенство по всякому вертеть, переписывая его в виде . Или, например, .

На самом деле речь идёт об очень простой вещи, хорошо знакомой всем программерам. Если представлять целые числа из от до как множество значений -битного регистра, то после инверсии всех битов в регистре полученное значение в сумме с исходным значением даст минус единицу. А исходную задачу можно сформулировать так: выразить операцию обычной суммы над целыми числами, являющимися значениями -битового регистра (естественно, сумму приходится рассматривать по модулю ) через операцию xor побитового сложения двух регистров.

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн окт 31, 2011 11:48 am 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Сб сен 01, 2001 7:00 am
Сообщения: 1577
Откуда: Александр Фенстер
У меня не получилось понять смысл исходного вопроса, потому что непонятно, что такое -- это какое-то стандартное обозначение для чего-то?

Тем не менее, если речь идёт о вопросе, можно ли сложение в дополнительном коде выразить только через xor -- ответ, скорее всего, нет. Функция сложения двух чисел, написанная с использованием битовых операций, выглядит примерно так:

Код:
unsigned int sum(unsigned int a, unsigned int b)
{
        unsigned int xor, and, t;

        and = a & b;
        xor = a ^ b;

        while (and != 0 )
        {
                and = and << 1;
                tmp = xor ^ and;
                and = and & xor;
                xor = tmp;
        }
        return xor;
}


Операция ^ -- это xor, & -- двоичное "и", << -- сдвиг влево на несколько позиций (т.е. умножение на 2 в некоторой степени).

_________________
АФ


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн окт 31, 2011 12:40 pm 
Не в сети
Начинающий автор

Зарегистрирован: Чт мар 08, 2007 7:29 pm
Сообщения: 246
Откуда: Тюшин Илья
fenster писал(а):
У меня не получилось понять смысл исходного вопроса, потому что непонятно, что такое -- это какое-то стандартное обозначение для чего-то?
это нестандартное обозначение для операции сложения в группе вычетов по модулю степени двойки. Например, , т.к. 3+3=2 (mod 4)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн окт 31, 2011 3:33 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
fenster писал(а):
Тем не менее, если речь идёт о вопросе, можно ли сложение в дополнительном коде выразить только через xor -- ответ, скорее всего, нет.

Блин, всё никак не могу нормально сформулировать.

Только через xor конечно же невозможно в силу "симметрии" xor относительно всех битов. Но на самом деле кроме xor допустимо ещё умножение в , если последнее рассматривать как поле Галуа. Причём умножение, с помощью которого эта абелева группа превращается в поле, нужно ввести любым из допустимых способов.

Попозже напишу точную формулировку.

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн окт 31, 2011 4:16 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Пт окт 01, 2004 6:27 pm
Сообщения: 1869
Во-первых - стандартное обозначение. Всю жизнь так писал :)
Во-вторых в базисе из и конъюнкции можно выразить любую булеву функцию. Это выражение даже называется нормальная алгебраическая форма или полином Жегалкина. Какова минимальная длина формулы, реализующий целочисленное сложение - вопрос к специалистам. Чтобы выразить наоборот нужны ещё операции выделения координаты и размножения аргумента, чтобы по размерности сходилось.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн окт 31, 2011 7:08 pm 
Не в сети
Начинающий автор

Зарегистрирован: Чт мар 08, 2007 7:29 pm
Сообщения: 246
Откуда: Тюшин Илья
В.П. писал(а):
Во-первых - стандартное обозначение. Всю жизнь так писал :)
Во-вторых в базисе из и конъюнкции можно выразить любую булеву функцию. Это выражение даже называется нормальная алгебраическая форма или полином Жегалкина. Какова минимальная длина формулы, реализующий целочисленное сложение - вопрос к специалистам. Чтобы выразить наоборот нужны ещё операции выделения координаты и размножения аргумента, чтобы по размерности сходилось.

эмм, В.П., кажется, Вы не поняли. То, что обычно обозначается как , здесь обозначается как +. А плюс в кружочке здесь это не "исключающее или", а сумма в группе вычетов. Соответственно, Ваше утверждение про полиномы Жегалкина надо переформулировать так: "в базисе из + и конъюнкции можно выразить любую булеву функцию. Это выражение даже называется нормальная алгебраическая форма или полином Жегалкина."


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн окт 31, 2011 7:49 pm 
Не в сети
Начинающий автор

Зарегистрирован: Чт мар 08, 2007 7:29 pm
Сообщения: 246
Откуда: Тюшин Илья
и, кстати, на счёт полиномов Жегалкина и т.п., функция не булева. А как представить её в виде булевой?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн окт 31, 2011 9:47 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Пт окт 01, 2004 6:27 pm
Сообщения: 1869
И правда посмотрел невнимательно, обычно и используют наоборот.
Cagnaccio писал(а):
и, кстати, на счёт полиномов Жегалкина и т.п., функция не булева. А как представить её в виде булевой?

Имеем n штук булевых функций по числу координат в области значений.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн окт 31, 2011 10:32 pm 
Не в сети
Начинающий автор

Зарегистрирован: Чт мар 08, 2007 7:29 pm
Сообщения: 246
Откуда: Тюшин Илья
В.П. писал(а):
Cagnaccio писал(а):
и, кстати, на счёт полиномов Жегалкина и т.п., функция не булева. А как представить её в виде булевой?

Имеем n штук булевых функций по числу координат в области значений.

а аргументы какие у этих функций? 2n аргументов что ли у каждой функции? но тогда в полином Жегалкина войдут конъюкции между цифрами в двоичной записи первого числа (ну или второго). А это никак нельзя назвать "одна операция хорошо выражается через другую".


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн окт 31, 2011 11:31 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Пт окт 01, 2004 6:27 pm
Сообщения: 1869
Cagnaccio писал(а):
а аргументы какие у этих функций? 2n аргументов что ли у каждой функции? но тогда в полином Жегалкина войдут конъюкции между цифрами в двоичной записи первого числа (ну или второго). А это никак нельзя назвать "одна операция хорошо выражается через другую".

"Хорошо" - не математический, а педагогический предикат :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт ноя 01, 2011 11:01 am 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Сб сен 01, 2001 7:00 am
Сообщения: 1577
Откуда: Александр Фенстер
Cagnaccio писал(а):
но тогда в полином Жегалкина войдут конъюкции между цифрами в двоичной записи первого числа (ну или второго). А это никак нельзя назвать "одна операция хорошо выражается через другую".

Чудес-то не бывает, получится нечто очень напоминающее приведённую выше функцию на си, если раскрутить цикл в многочлен :)

_________________
АФ


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Часовой пояс: UTC + 7 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 4


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB