Что такое поразрядная конъюнкция и как обозначается
Поразрядные операции выполняются над отдельными разрядами или битами чисел. Данные операции производятся только над целыми числами. Но сначала вкратце рассмотрим, что представляют собой разряды чисел.
Двоичное представление чисел
На уровне компьютера все данные представлены в виде набора бит. Каждый бит может иметь два значения: 1 (есть сигнал) и 0 (нет сигнала). И все данные фактически представляют набор нулей и единиц. 8 бит представляют 1 байт. Подобную систему называют двоичной .
Например, число 13 в двоичной системе будет равно 1101 2. Как мы это получили:
// перевод десятичного числа 13 в двоичную систему 13 / 2 = 6 // остаток 1 (13 - 6 *2 = 1) 6 / 2 = 3 // остаток 0 (6 - 3 *2 = 0) 3 / 2 = 1 // остаток 1 (3 - 1 *2 = 1) 1 / 2 = 0 // остаток 1 (1 - 0 *2 = 1)
Общий алгоритм состоит в последовательном делении числа и результатов деления на 2 и получение остатков, пока не дойдем до 0. Затем выстраиваем остатки в линию в обратном порядке и таким образом формируем двоичное представление числа. Конкретно в данном случае по шагам:
- Делим число 13 на 2. Результат деления — 6, остаток от деления — 1 (так как 13 — 6 *2 = 1)
- Далее делим результат предыдущей операции деления — число 6 на 2. Результат деления — 3, остаток от деления — 0
- Делим результат предыдущей операции деления — число 3 на 2. Результат деления — 1, остаток от деления — 1
- Делим результат предыдущей операции деления — число 1 на 2. Результат деления — 0, остаток от деления — 1
- Последний результат деления равен 0, поэтому завершаем процесс и выстраиваем остатки от операций делений, начиная с последнего — 1101
При обратном переводе из двоичной системы в десятичную умножаем значение каждого бита (1 или 0) на число 2 в степени, равной номеру бита (нумерация битов идет от нуля):
// перевод двоичного числа 1101 в десятичную систему 1(3-й бит)1(2-й бит)0(1-й бит)1(0-й бит) 1 * 23 + 1 * 22 + 0 * 21 + 1 * 20 = 1 * 8 + 1 * 4 + 0 * 2 + 1 * 1 = 8 + 4 + 0 + 1 = 13
Представление отрицательных чисел
Для записи чисел со знаком в С++ применяется дополнительный код (two’s complement), при котором старший разряд является знаковым. Если его значение равно 0, то число положительное, и его двоичное представление не отличается от представления беззнакового числа. Например, 0000 0001 в десятичной системе 1.
Если старший разряд равен 1, то мы имеем дело с отрицательным числом. Например, 1111 1111 в десятичной системе представляет -1. Соответственно, 1111 0011 представляет -13.
Чтобы получить из положительного числа отрицательное, его нужно инвертировать и прибавить единицу:
Например, получим число -3. Для этого сначала возьмем двоичное представление числа 3:
310 = 0000 00112
~0000 0011 = 1111 1100
1111 1100 + 1 = 1111 1101
Таким образом, число 1111 1101 является двоичным представлением числа -3.
Рассмотрим, как будет идти сложение числа со знаком и без знака. Например, сложим 12 и -8:
1210 = 000011002 + -810 = 111110002 (8 - 00001000, после инверсии - 11110111, после +1 = 11111000) = 410 = 000001002
Мы видим, что в двоичной системе получилось число 00000100 2 или 4 10 в десятичной системе.
Для большей наглядности в C++ удобно использовать бинарную запись числа, которая предваряется символами 0b :
#include int main() < unsigned int number; // 12 std::cout
В данном случае переменная number имеет значение 0b0000’1100 , что в десятичной системе соответствует числу 12.
Операции сдвига
Каждое целое число в памяти представлено в виде определенного количества разрядов. И операции сдвига позволяют сдвинуть битовое представление числа на несколько разрядов вправо или влево. Операции сдвига применяются только к целочисленным операндам. Есть две операции:
unsigned int a = 2 > 3; // 10000 на три разряда вправо = 10 - 2
Число 2 в двоичном представлении 10. Если сдвинуть число 10 на два разряда влево, то получится 1000, что в десятичной системе равно число 8.
Число 16 в двоичном представлении 10000. Если сдвинуть число 10 на три разряда вправо (три последних разряда отбрасываются), то получится 10, что в десятичной системе представляет число 2.
Можно заметить, что сдвиг на один разряд влево фактически аналогично умножению на 2, тогда как сдвиг вправо на один раз эквивалентно делению на два. Мы можем обобщить: сдвиг влево на n аналогичен умножению числа на 2 n , а сдвиг вправо на n разрядов аналогичен делению на 2 n , что можно использовать вместо умножения/деления на степени двойки:
#include int main() < unsigned int x; unsigned int number; unsigned int result; // 7 * 2*2*2 = 56 std::cout > x; // 26 / (2*2*2) = 3 std::cout
Поразрядные операции
Поразрядные операции также проводятся только над соответствующими разрядами целочисленных операндов:
- & : поразрядная конъюнкция (операция И или поразрядное умножение). Возвращает 1, если оба из соответствующих разрядов обоих чисел равны 1
- | : поразрядная дизъюнкция (операция ИЛИ или поразрядное сложение). Возвращает 1, если хотя бы один из соответствующих разрядов обоих чисел равен 1
- ^ : поразрядное исключающее ИЛИ. Возвращает 1, если только один из соответствующих разрядов обоих чисел равен 1
- ~ : поразрядное отрицание или инверсия. Инвертирует все разряды операнда. Если разряд равен 1, то он становится равен 0, а если он равен 0, то он получает значение 1.
int a = 5 | 2; // 101 | 010 = 111 - 7 int b = 6 & 2; // 110 & 010 = 10 - 2 int c = 5 ^ 2; // 101 ^ 010 = 111 - 7 int d = ~9; // -10
Например, выражение 5 | 2 равно 7. Число 5 в двоичной записи равно 101, а число 2 — 10 или 010. Сложим соответствующие разряды обоих чисел. При сложении если хотя бы один разряд равен 1, то сумма обоих разрядов равна 1. Поэтому получаем:
| 1 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 1 | 1 |
В итоге получаем число 111, что в десятичной записи представляет число 7.
Возьмем другое выражение 6 & 2 . Число 6 в двоичной записи равно 110, а число 2 — 10 или 010. Умножим соответствующие разряды обоих чисел. Произведение обоих разрядов равно 1, если оба этих разряда равны 1. Иначе произведение равно 0. Поэтому получаем:
| 1 | 1 | 0 |
| 0 | 1 | 0 |
| 0 | 1 | 0 |
Получаем число 010, что в десятичной системе равно 2.
Пример практического применения операций
Многие недооценивают поразрядные операции, не понимают, для чего они нужны. Тем не менее они могут помочь в решении ряда задач. Прежде всего они позволяют нам манипулировать данными на уровне отдельных битов. Один из примеров. У нас есть три числа, которые находятся в диапазоне от 1 до 3:
int value1 ; // 0b0000'0011 int value2 ; // 0b0000'0010 int value3 ; // 0b0000'0001
Мы знаем, что значения этих чисел не будут больше 3, и нам нужно эти данные максимально сжать. Мы можем три числа сохранить в одно число. И в этом нам помогут поразрядные операции.
#include int main() < int value1 ; // 0b0000'0011 int value2 ; // 0b0000'0010 int value3 ; // 0b0000'0001 int result ; // сохраняем в result значения из value1 result = result | value1; // 0b0000'0011 // сдвигаем разряды в result на 2 разряда влево result = result
Разберем этот код. Сначала определяем все сохраняемые числа value1, value2, value3. Для хранения результата определена переменная result, которая по умолчанию равна 0. Для большей наглядности ей присвоено значение в бинарном формате:
int result = 0b0000'0000;
Сохраняем первое число в result:
result = result | value1; // 0b0000'0011
Здесь мы имеем дело с логической операцией поразрядного сложения - если один из соответствующих разрядов равен 1, то результирующий разряд тоже будет равен 1. То есть фактически
0b0000'0000 + 0b0000'0011 = 0b0000'0011
Итак, первое число сохранили в result. Мы будем сохранять числа по порядку. То есть сначала в result будет идти первое число, затем второе и далее третье. Поэтому сдвигаем число result на два разряда влево (наши числа занимают в памяти не более двух разрядов):
result = resultТо есть фактически выполняем следующее вычисление:
0b0000'0011Далее повторяем логическую операцию сложения, сохраняем второе число:
result = result | value2; // 0b0000'11100b0000'1100 + 0b0000'0010 = 0b0000'1110Далее повторяем сдвиг на два разряда влево и сохраняем третье число. В итоге мы получим в двоичном представлении число 0b0011'1001 . В десятичной системе это число равно 57. Но это не имеет значения, потому что нам важны конкретные биты числа. Стоит отметить, что мы сохранили в одно число три числа, и в переменной result еще есть свободное место. Причем в реальности не важно, сколько именно битов надо сохранить. В данном случае для примера сохраняем лишь два бита.
Для восстановления данных прибегнем к обратному порядку:
#include int main() < int result ; // обратное получение данных int newValue3 = result & 0b000'0011; // сдвигаем данные на 2 разряда вправо result = result >> 2; int newValue2 = result & 0b000'0011; // сдвигаем данные на 2 разряда вправо result = result >> 2; int newValue1 = result & 0b000'0011; std::coutПолучаем числа в порядке, обратном тому, в котором они были сохранены. Поскольку мы знаем, что каждое сохраненное число занимает лишь два разряда, то по сути нам надо получить лишь последние два бита. Для этого применяем битовую маску 0b000'0011 и операцию логического умножения, которая возвращает 1, если каждый из двух соответствующих разрядов равен 1. То есть операция
int newValue3 = result & 0b000'0011;0b0011'1001 * 0b0000'0011 = 0b0000'0001Таким образом, последнее число равно 0b0000'0001 или 1 в десятичной системе
Стоит отметить, что если мы точно знаем структуру данных, то мы легко можем составить битовую маску, чтобы получить нужно число:
#include int main() < int result ; int recreatedValue1 = (result & 0b0011'0000) >> 4; std::cout
Здесь получаем первое число, которое, как мы знаем, что оно занимает третий и четвертый бит совокупного числа. Для этого применяем умножение на битовую маску 0b0011'0000. И затем сдвигаем число на 4 разряда вправо.
0b0011'1001 * 0b0011'0000 = 0b0011'0000 >> 4 = 0b0000'0011Аналогично, если мы точно знаем структуру, по которой сохраняются данные, то мы могли бы сохранить данные сразу в нужное место в числе result:
#include int main() < int value1 ; // 0b0000'0011 int value2 ; // 0b0000'0010 int value3 ; // 0b0000'0001 int result ; // сохраняем в result значения из value1 result = result | (value1конъюнкция и дизъюнкция. люди объясните пожалуйста простым языком что это такое. (нужно срочно, а то умру от любопытства)
конъюкция - объединение двух высказываний союзом И.
Например, если даны высказывания "чётное число" и "точный квадрат" то их конъюкцией будет высказывание "чётное число и точный квадрат".
Число 36 будет удовлетворять этому высказыванию, потому, что оно является чётным и является квадратом числа 6. Число 12 не будет удовлетворять этому условию, потому что оно хотя и является чётным, но не является полным квадратом. Число 25 также не будет удовлетворять этому условию, потому что хотя оно и является чётным квадратом, но не является чёётным.
Если даны высказывания А и В то их конъюкция обозначается A&B.
дизъюкция - объединение двух высказываний союзом илиэ
Например, "чётное число или точный квадрат" Этому высказыванию будут удовлетворять числа 36, 12, 6, 25. Ему не будет удовлетворять, например, число
17 потому что оно не является ни чётным ни точным квадратом.
Дизъюкция высказываний А и В обозначается A\/B
В логике, кроме конъюкции и дизъюкции рассматривается, также, отрицание и импликация.Остальные ответы
операции логического умножения и сложенияну это операции такие, если вы логику имеете в виду. Примерно то же самое, что сложение и умножение, тем же законам подчиняются.. .
Для высказываний еще можно заменить словами И / ИЛИ.Странные вещи вы для любопытства выбираете, хочу сказать.
ермrаов иванМастер (1607) 13 лет назад
просто сейчас изучаю php, и там встретилась тема поразрядные операторы, в разделе программирование ничего дельного не дали в ответ, только дали ссылку на сайт, в котором было поразрядная конъюнкция и поразрядная дизкъюнкция, теперь решил сначала выяснить что такое конъюнкция и дизъюнкция
Задание 12. Краткие теоретические сведения
1. Все адреса, используемые в современных компьютерных сетях – это 32-разрядные двоичные числа.
Для вычисления адреса сети компьютер применяет к адресу узла сети и маске, представленным в двоичном виде, операцию поразрядной конъюнкции. Это значит, что в определенном разряде итогового числа стоит 1 тогда и только тогда, когда у обоих исходных чисел в этом разряде стоит 1. При разборе задания эта операция обозначается символом &. Таким образом, ,
адрес_сети = адрес_узла & маска.
2. Чтобы пояснить операцию поразрядной конъюнкции, разберем несколько примеров. В этих примеров для удобства двоичные разряды рассматриваемых двоичных чисел собраны в группы по 4 разряда. Такие группы удобно обозначать 16-чными цифрами (полезная информация про системы счисления здесь) .
Пример 1. Пусть X = 1101; Y = 1011. Тогда X&Y = 1001 (только в первом и последнем разряде и в X, и в Y стоит 1).
Пример 2. Пусть X = 1101; Y = 0011. Тогда X&Y = 0001
Пример 3. Пусть X = 1111 1101; Y = 1010 0011. Тогда X&Y = 1010 0001
Пример 4. Пусть X = 1111 1111; Y = 1010 0011. Тогда X&Y = 1010 0011
Для любого 8-разрядного числа Y выполнено: 11111111 & Y = Y
Пример 5. Пусть X = 0000 0000; Y = 1010 0011. Тогда X&Y = 0000 0000
Для любого 8-разрядного числа Y выполнено: 00000000 & Y = 00000000
3. Работать с 32-разрядными двоичными числами человеку неудобно, поэтому для IP-адресов используют побайтное представление, записывая каждый байт (т.е. восьмерку двоичных разрядов, иногда говорят - октет) в десятичной системе счисления, например IP-адрес 11011001 11101001 11101000 00000011 можно записать как 217.233.232.3. Байты (точнее - их десятичные представления) принято отделять точками.
Свойства поразрядной конъюнкции, которые отмечены в примерах 4 и 5, можно записать так. Пусть A–целое число от 0 до 255, тогда
A & 255 = A
A & 0 = 0
4. При выполнении задания B11 полезно учитывать следующее.
- В маске подсети старшие (левые) байты всегда 255 (т.е. в них все разряды 1), младший байт (четвертый слева, т.е. самый правый) всегда 0 (т.е. в нем все разряды 0).
- В третьем слева байте слева стоит какое-то количество единиц и далее – нули.
Поэтому третье слева число в маске может принимать только такие значения:
. 128 = 1000 00002 = 255-127
. 192 = 1100 00002 = 128+64 = 255 – 63
. 224 = 1110 00002 = 128+64 + 32 = 255 – 31
. 240 = 1111 00002 = 128+64 + 32 + 16 = 255 – 15
. 248 = 1111 10002 = 128+64 + 32 + 16 + 8 = 255 – 7
. 252 = 1111 11002 = 128+64 + 32 + 16 + 8 +4 = 255 – 3
. 254 = 1111 11102 = 128+64 + 32 + 16 + 8 +4 +2 = 255 – 1
. 255 = 1111 11112 = 128+64 + 32 + 16 + 8 +4 +2 + 1
- первое и второе число в адресе сети те же, что и в адресе узла сети;
- четвертое – всегда 0;
- третье получается из третьего числа адресе узла сети обнулением определенного количества младших разрядов. Например, если третье число в маске подсети равно 248, то обнуляются три младших разряда третьего числа адреса узла подсети.
ПОРАЗРЯДНАЯ КОНЪЮНКЦИЯ
�� Что означает операция поразрядной конъюнкции? 14 & 5 = 1100 & 0101 = 0100 = 8 — вот и всё.
�� Для выражения (‘x & A = 0’ —> ‘x & 13 = 0’) v ‘x & 23 = 23 0’ найти наименьшее А, чтобы выражение принимало значение 1 для всех х
�� Преобразуем запись.
Пусть ‘x & m = 0’ = Z(m), тогда:
(Z(A) —> Z(13)) v Z(23) = -Z(A) v Z(13) v Z(23)Z(13) = Либо у числа х не должно быть битов
Z(23) = Либо у числа х не должно быть битовК примеру для х = 8 выражение будет истинным, потому что, хоть Z(13) = 0, Z(23) = 1
-Z(A) = Либо у числа x есть биты там же, где они есть у A:�� Какое A надо взять, чтобы оно дополняло условия Z(13) или Z(23)
если А = 1, тогда ЛЮБОЕ нечётное число (у всех у них есть бит 1) будет -Z(A) = 1 — значит и общее выражение будет истинно.
Биты в составе -Z сводят на нет действие битов в Z(13) или Z(23).
�� Какой надо взять наименьший A, чтобы не осталось ‘активных’ битов либо в Z(13) либо в Z(23)? Ответ: А = 13
