НГУ
http://forum.nsu.ru/

Двоичное сложение, перенос битов
http://forum.nsu.ru/viewtopic.php?f=18&t=22766
Страница 1 из 1

Автор:  Коба [ Вс окт 30, 2011 1:39 am ]
Заголовок сообщения:  Двоичное сложение, перенос битов

Допустим, есть у нас абелева группа . Как она устроена - понятно, при желании на ней можно даже ввести умножение и превратить её в поле характеристики .

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

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

Автор:  Cagnaccio [ Вс окт 30, 2011 4:30 pm ]
Заголовок сообщения:  Re: Двоичное сложение, перенос битов

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

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

Автор:  Коба [ Вс окт 30, 2011 8:27 pm ]
Заголовок сообщения:  Re: Двоичное сложение, перенос битов

Cagnaccio писал(а):
Коба писал(а):
Кое-что, безусловно, сделать можно: например, взятие противоположного элемента соответсвует вычислению для него двоично-дополнительного кода, так что , где .

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

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

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

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

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

Автор:  fenster [ Пн окт 31, 2011 11:48 am ]
Заголовок сообщения: 

У меня не получилось понять смысл исходного вопроса, потому что непонятно, что такое -- это какое-то стандартное обозначение для чего-то?

Тем не менее, если речь идёт о вопросе, можно ли сложение в дополнительном коде выразить только через 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 в некоторой степени).

Автор:  Cagnaccio [ Пн окт 31, 2011 12:40 pm ]
Заголовок сообщения: 

fenster писал(а):
У меня не получилось понять смысл исходного вопроса, потому что непонятно, что такое -- это какое-то стандартное обозначение для чего-то?
это нестандартное обозначение для операции сложения в группе вычетов по модулю степени двойки. Например, , т.к. 3+3=2 (mod 4)

Автор:  Коба [ Пн окт 31, 2011 3:33 pm ]
Заголовок сообщения: 

fenster писал(а):
Тем не менее, если речь идёт о вопросе, можно ли сложение в дополнительном коде выразить только через xor -- ответ, скорее всего, нет.

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

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

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

Автор:  В.П. [ Пн окт 31, 2011 4:16 pm ]
Заголовок сообщения: 

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

Автор:  Cagnaccio [ Пн окт 31, 2011 7:08 pm ]
Заголовок сообщения: 

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

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

Автор:  Cagnaccio [ Пн окт 31, 2011 7:49 pm ]
Заголовок сообщения: 

и, кстати, на счёт полиномов Жегалкина и т.п., функция не булева. А как представить её в виде булевой?

Автор:  В.П. [ Пн окт 31, 2011 9:47 pm ]
Заголовок сообщения: 

И правда посмотрел невнимательно, обычно и используют наоборот.
Cagnaccio писал(а):
и, кстати, на счёт полиномов Жегалкина и т.п., функция не булева. А как представить её в виде булевой?

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

Автор:  Cagnaccio [ Пн окт 31, 2011 10:32 pm ]
Заголовок сообщения: 

В.П. писал(а):
Cagnaccio писал(а):
и, кстати, на счёт полиномов Жегалкина и т.п., функция не булева. А как представить её в виде булевой?

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

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

Автор:  В.П. [ Пн окт 31, 2011 11:31 pm ]
Заголовок сообщения: 

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

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

Автор:  fenster [ Вт ноя 01, 2011 11:01 am ]
Заголовок сообщения: 

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

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

Страница 1 из 1 Часовой пояс: UTC + 7 часов
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/