Задачка на побитные операции

[MGM]

Определена функция от трех битов такая, что если два и более бита равны единице, то и значение функции единица. И ноль в противном случае.
Нужно реализовать такую функцию только с использованием побитных операций. У меня получилось пять операций: три попарных "и" и две "или".
Есть ли более быстрая реализация?

[svv]

MGM в сообщении #1601407 писал(а):

Нужно реализовать такую функцию только с использованием побитных операций. У меня получилось пять операций: три попарных "и" и две "или".

Скорее всего, Вы понимаете побитовые операции не так, как я, иначе я вообще не понимаю, как это можно сделать.

[MGM]

Побитовые операции мы понимает одинаково. Просто вы понимаете такие операции для "слов" содержащих более одного бита. У меня переменные однобитные (или однобитовые, не знаю, как правильно).

[Geen]

MGM в сообщении #1601407 писал(а):

с использованием побитных операций.

каких именно?

[Booker48]

MGM в сообщении #1601407 писал(а):

Есть ли более быстрая реализация?

С меньшим числом операций? Есть.
$x_1x_2 \vee x_3(x_1\vee x_2)$

[MGM]

Booker48 в сообщении #1601418 писал(а):

MGM в сообщении #1601407 писал(а):

Есть ли более быстрая реализация?

С меньшим числом операций? Есть.
$x_1x_2 \vee x_3(x_1\vee x_2)$

Спасибо. То есть четыре операции?
А три никак?

[Booker48]

MGM в сообщении #1601422 писал(а):

А три никак?

Если использовать только И, ИЛИ и НЕ, то никак.

[svv]

Такая тема уже была на форуме. Я там писал:

svv в сообщении #1552748 писал(а):

В точности эта функция в полном одноразрядном сумматоре по двум операндам $x,y$ и переносу $z$ вычисляет следующий перенос.

Так что можете поискать, не реализовано ли где-нибудь вычисление переноса с помощью И, ИЛИ, НЕ проще. (Говорю сразу, что нет.)

[MGM]

А галочка $\vee$, это "или"?
Кстати, иногда так определяют min. А значит эквивалент "и".
Странно, но смысл противоположный.

[svv]

Да, это "или".

[MGM]

svv в сообщении #1601426 писал(а):

Такая тема уже была на форуме. Я там писал:

svv в сообщении #1552748 писал(а):

В точности эта функция в полном одноразрядном сумматоре по двум операндам $x,y$ и переносу $z$ вычисляет следующий перенос.

Так что можете поискать, не реализовано ли где-нибудь вычисление переноса с помощью И, ИЛИ, НЕ проще. (Говорю сразу, что нет.)

Только значение самого бита получается через исключающее или.

[svv]

Речь не о бите суммы (там да, лучше всего XOR, если его разрешено использовать), а о бите переноса, который определяет, нужно ли переносить единицу в следующий разряд.

[MGM]

svv в сообщении #1601433 писал(а):

Речь не о бите суммы (там да, лучше всего XOR, если его разрешено использовать), а о бите переноса, который определяет, нужно ли переносить единицу в следующий разряд.

Это я понял. Потому как именно буфер переноса меня и интересует. Не знаю зачем.
А вот XOR почему-то в Булеву алгебру не включают. Проблемы с дистрибутивностью?

[svv]

MGM в сообщении #1601450 писал(а):

А вот XOR почему-то в Булеву алгебру не включают. Проблемы с дистрибутивностью?

Наверное, потому, что там эта операция — производная, выражается через исходные. Это не значит, что она "под запретом", никто не мешает изучать её свойства.

А вот в поле Галуа $\mathbb F_2$ сложение по модулю 2 $\oplus$ играет роль той операции "сложения", которая требуется самим определением поля.
Поле из двух элементов
Ну, а в поле проблем с дистрибутивностью точно нет: $(a\oplus b)\cdot c = (a\cdot c)\oplus (b\cdot c)$.

[tolstopuz]

Кстати, если нужны и бит суммы, и бит переноса, и разрешается XOR, то хватает пяти операций.