2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: Задачка на побитные операции
Сообщение17.07.2023, 22:14 
Аватара пользователя
MGM в сообщении #1601407 писал(а):
Нужно реализовать такую функцию только с использованием побитных операций. У меня получилось пять операций: три попарных "и" и две "или".
Скорее всего, Вы понимаете побитовые операции не так, как я, иначе я вообще не понимаю, как это можно сделать.

 
 
 
 Re: Задачка на побитные операции
Сообщение17.07.2023, 22:27 
Аватара пользователя
Побитовые операции мы понимает одинаково. Просто вы понимаете такие операции для "слов" содержащих более одного бита. У меня переменные однобитные (или однобитовые, не знаю, как правильно).

 
 
 
 Re: Задачка на побитные операции
Сообщение17.07.2023, 22:36 
Аватара пользователя
MGM в сообщении #1601407 писал(а):
с использованием побитных операций.

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

 
 
 
 Re: Задачка на побитные операции
Сообщение17.07.2023, 22:46 
MGM в сообщении #1601407 писал(а):
Есть ли более быстрая реализация?

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

 
 
 
 Re: Задачка на побитные операции
Сообщение17.07.2023, 22:57 
Аватара пользователя
Booker48 в сообщении #1601418 писал(а):
MGM в сообщении #1601407 писал(а):
Есть ли более быстрая реализация?

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

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

 
 
 
 Re: Задачка на побитные операции
Сообщение17.07.2023, 23:01 
MGM в сообщении #1601422 писал(а):
А три никак?

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

 
 
 
 Re: Задачка на побитные операции
Сообщение17.07.2023, 23:04 
Аватара пользователя
Такая тема уже была на форуме. Я там писал:
svv в сообщении #1552748 писал(а):
В точности эта функция в полном одноразрядном сумматоре по двум операндам $x,y$ и переносу $z$ вычисляет следующий перенос.
Так что можете поискать, не реализовано ли где-нибудь вычисление переноса с помощью И, ИЛИ, НЕ проще. :-) (Говорю сразу, что нет.)

 
 
 
 Re: Задачка на побитные операции
Сообщение17.07.2023, 23:05 
Аватара пользователя
А галочка $\vee$, это "или"?
Кстати, иногда так определяют min. А значит эквивалент "и".
Странно, но смысл противоположный.

 
 
 
 Re: Задачка на побитные операции
Сообщение17.07.2023, 23:08 
Аватара пользователя
Да, это "или".

 
 
 
 Re: Задачка на побитные операции
Сообщение17.07.2023, 23:09 
Аватара пользователя
svv в сообщении #1601426 писал(а):
Такая тема уже была на форуме. Я там писал:
svv в сообщении #1552748 писал(а):
В точности эта функция в полном одноразрядном сумматоре по двум операндам $x,y$ и переносу $z$ вычисляет следующий перенос.
Так что можете поискать, не реализовано ли где-нибудь вычисление переноса с помощью И, ИЛИ, НЕ проще. :-) (Говорю сразу, что нет.)

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

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

 
 
 
 Re: Задачка на побитные операции
Сообщение18.07.2023, 00:24 
Аватара пользователя
svv в сообщении #1601433 писал(а):
Речь не о бите суммы (там да, лучше всего XOR, если его разрешено использовать), а о бите переноса, который определяет, нужно ли переносить единицу в следующий разряд.

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

 
 
 
 Re: Задачка на побитные операции
Сообщение18.07.2023, 00:56 
Аватара пользователя
MGM в сообщении #1601450 писал(а):
А вот XOR почему-то в Булеву алгебру не включают. Проблемы с дистрибутивностью?
Наверное, потому, что там эта операция — производная, выражается через исходные. Это не значит, что она "под запретом", никто не мешает изучать её свойства.

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

 
 
 
 Re: Задачка на побитные операции
Сообщение18.07.2023, 01:04 
Кстати, если нужны и бит суммы, и бит переноса, и разрешается XOR, то хватает пяти операций.

 
 
 [ Сообщений: 21 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group