Что такое поразрядная конъюнкция

Задание 12. Краткие теоретические сведения

1. Все адреса, используемые в современных компьютерных сетях – это 32-разрядные двоичные числа.

адрес_сети = адрес_узла & маска.

Пример 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

Свойства поразрядной конъюнкции, которые отмечены в примерах 4 и 5, можно записать так. Пусть A–целое число от 0 до 255, тогда

A & 255 = A

A & 0 = 0

4. При выполнении задания B11 полезно учитывать следующее.

Поэтому третье слева число в маске может принимать только такие значения:

. 128 = 1000 0000₂ = 255-127

. 192 = 1100 0000₂ = 128+64 = 255 – 63

. 224 = 1110 0000₂ = 128+64 + 32 = 255 – 31

. 240 = 1111 0000₂ = 128+64 + 32 + 16 = 255 – 15

. 248 = 1111 1000₂ = 128+64 + 32 + 16 + 8 = 255 – 7

. 252 = 1111 1100₂ = 128+64 + 32 + 16 + 8 +4 = 255 – 3

. 254 = 1111 1110₂ = 128+64 + 32 + 16 + 8 +4 +2 = 255 – 1

. 255 = 1111 1111₂ = 128+64 + 32 + 16 + 8 +4 +2 + 1

— первое и второе число в адресе сети те же, что и в адресе узла сети;

— четвертое – всегда 0;

— третье получается из третьего числа адресе узла сети обнулением определенного количества младших разрядов. Например, если третье число в маске подсети равно 248, то обнуляются три младших разряда третьего числа адреса узла подсети.

Источник

Поразрядная конъюнкция задачи 3

Лада Есакова, преподаватель информатики и математики, автор книги «Информатика. Полный курс подготовки к ЕГЭ».

Давайте разберем поразрядную конъюнкцию. Это задача, которая несколько лет была на ЕГЭ и на всех СтатГрадах, и она как-то исторически вызывает неприятные эмоции у учеников. На самом деле, ничего сложного.

Что такое поразрядная конъюнкция? Это перевод чисел в двоичную систему, а потом разряд с разрядом умножаем. Например, 7 х 4. 7 перевожу в двоичную систему – 1 1 1. 4 перевожу в двоичную систему – 1 0 0. И умножаю разряд с разрядом – 111 х 100=100.

Давайте порешаем задачи.

«Введем выражение М & К, обозначающие поразрядную конъюнкцию М и К (логическое «И» между соответствующими битами двоичной записи). Определите наименьшее натуральное число А, такое, что выражение

Избавляемся от импликации. Формулу напоминать не буду, наверное, ее уже все знают наизусть.

Теперь мой любимый прием – известная часть пусть будет нулем (0), тогда искомая часть обязана быть единицей (1)

На какой-то момент я забываю про предметную область, я занимаюсь преобразованием до системы.

С нулем работать не очень приятно, поэтому сделаю отрицание и будет единица.

На что мне надо умножить 48, чтобы получились одни нули?

У X должны быть в первом разряде нули, чтобы обнулить единицы у 48, а остальное не важно

И те же самые X я должна умножить на 56 и не получить ноль. Чтобы не получить ноль, мне нужно здесь поставить единицу, чтобы она зацепила единицу от 56

Дальше может стоять что угодно. Все такие X являются решением этого уравнения.

Второе уравнение говорит, что все такие X (001…) нужно умножить на А и не получить ноль.

На первой и второй позиции у А может стоять что угодно. Три последние позиции тоже без разницы. Нужно поймать единственную единицу.

Если у А будет здесь единица, я умножу А и Х и ноль не получу. Вот такое А должно быть.
Нужно найти наименьшее. Тогда остальные пусть будут нули.

Источник

Что такое поразрядная конъюнкция

Примечание: Перед поразрядным сравнением операнды number1 и number2 округляются до меньшего целого.

/* присвоение 00000001, 00000011 */

/* возвращает 1 (00000001) */

Поразрядное исключающее ИЛИ

Операция используется для сравнения каждого бита первого операнда с соответствующим битом второго операнда. Если оба бита не равны, результирующий бит устанавливается в единицу.

analog = number1 ^ number2;

Примечание: Перед поразрядным сравнением операнды number1 и number2 округляются до меньшего целого.

/* присвоение 00000001, 00000011 */

Val = Num1 ^ Num2;

/* возвращает 2 (00000010) */

Дизъюнкция

analog = number1 | number2;

Примечание: Перед поразрядным сравнением операнды number1 и number2 округляются до меньшего целого.

/* присвоение 00000001, 00000011 */

Val = Num1 | Num2;

/* возвращает 3 (00000011) */

Логическое И

Операция используется для сравнения двух числовых значений и возвращает ненулевой результат, если оба операнда ненулевые.

discrete = number1 && number2;

Логическое ИЛИ

Операция используется для сравнения двух числовых значений и возвращает ненулевое значение, если хотя бы один из сравниваемых операндов ненулевой.

discrete = number1 || number2;

Val = Num1 || Num2;

Val = Num1 || Num2;

/* возвращает 0 */

Источник

Что такое поразрядная конъюнкция

Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14&5 = 1110₂&0101₂ = 0100₂ = 4.

Для какого наименьшего неотрицательного целого числа А формула

x&25 ≠ 0 → (x&17 = 0 → x&А ≠ 0)

тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной х)?

Преобразуем выражение по законам алгебры логики:

¬Х → (Y → ¬Z) = Х + (Y → ¬Z) = Х + ¬Y + ¬Z = X + ¬(YZ) = YZ → X.

Далее применяем обозначения и реализуем способ решения, изложенный К. Ю. Поляковым в теоретических материалах (см., например, раздел «Теория» на нашем сайте) без дополнительных пояснений.

Имеем импликацию Z₁₇Z_A → Z₂₅ или Z_{(17 or A)} → Z₂₅. Запишем число 25 в двоичной системе счисления: 25₁₀ = 11001₂. Единичные биты, стоящие в правой части, должны являться единичными битами левой. Поскольку 17₁₀ = 10001₂, двоичная запись искомого числа А должна содержать единичный бит в третьем разряде (как обычно, считая справа налево, начиная с нуля).

Тем самым, наименьшее А = 1000₂ = 8₁₀.

Приведём другое решение.

Решим задание с помощью языка программирования PascalABC методом перебора:

for A := 0 to 31 do begin

if not (((x and 25) = 0) or ((x and 17) <> 0) or ((x and A) <> 0)) then

Приведём решение на языке Python.

Заметим, что можно не перебирать числа, большие 31, поскольку для записи чисел 25 и 17 хватит пяти разрядов. Программа выведет ответ 8.

Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14 & 5 = 1110₂ & 0101₂ = 0100₂ = 4. Для какого наименьшего неотрицательного целого числа А формула

тождественно истинна (то есть принимает значение 1 при любом неотрицательном целом значении переменной х)?

Преобразуем выражение по законам алгебры логики:

¬Х → (Y → ¬Z) = Х + (Y → ¬Z) = Х + ¬Y + ¬Z = X + ¬(YZ) = YZ → X.

Далее применяем обозначения и реализуем способ решения, изложенный К. Ю. Поляковым в теоретических материалах (см., например, раздел «Теория» на нашем сайте), без дополнительных пояснений.

Имеем импликацию Z₁₂Z_A → Z₂₉ или Z_{(12 or A)} → Z₂₉. Запишем число 29 в двоичной системе счисления: 29₁₀ = 11101₂. Единичные биты, стоящие в правой части, должны являться единичными битами левой. Поскольку 12₁₀ = 01100₂, двоичная запись искомого числа А должна содержать единичные биты в нулевом и четвертом разрядах (как обычно, считая справа налево, начиная с нуля).

Тем самым, наименьшее А = 10001₂ = 17₁₀.

Приведём другое решение.

Решим задание с помощью языка программирования PascalABC методом перебора:

for A := 0 to 31 do begin

if not (((x and 29) = 0) or ((x and 12) <> 0) or ((x and A) <> 0)) then

Приведём решение на языке Python.

Заметим, что можно не перебирать числа, большие 31, поскольку для записи чисел 29 и 12 хватит пяти разрядов. Программа выведет ответ 17.

Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n.

Для какого наименьшего неотрицательного целого числа А формула

тождественно истинна (то есть принимает значение 1 при любом неотрицательном целом значении переменной x)?

Преобразуем выражение по законам алгебры логики:

(¬Х + ¬Y) → (W → ¬Z) = ¬(¬Х + ¬Y) + (¬W + ¬Z) = ХY + ¬(WZ) = WZ → XY.

Далее применяем обозначения и реализуем способ решения, изложенный К. Ю. Поляковым в теоретических материалах (см., например, раздел «Теория» на нашем сайте), без дополнительных пояснений.

Имеем импликацию Z₁₇Z_A → Z₂₈Z₄₅ или Z_{(17 or А)} → Z_{(28 or 45)}. Поскольку 28₁₀ = 11100₂, 45₁₀ = 101101₂, для побитовой дизъюнкции имеем: 28or45 = 111101. Тогда Z_{(17 or А)} = Z₆₁.

Импликация принимает вид Z_{(17 or A)} → Z₆₁. Единичные биты двоичной записи числа 61, должны являться единичными битами левой части. Поэтому в побитовой дизъюнкции 17orA единицы должны стоять на нулевой, второй, третьей, четвертой и пятой позициях (как обычно, считая справа налево, начиная с нуля). Запишем числа 17, А и 61 в двоичной системе счисления, и выясним, что наименьшее число, дающее при поразрядной дизъюнкции единицы на указанных позициях:

Приведём другое решение.

Решим задание с помощью языка программирования PascalABC методом перебора:

for A := 0 to 63 do begin

if not (((x and 28) = 0) and ((x and 45) = 0) or ((x and 17) <> 0) or ((x and A) <> 0)) then

Приведем аналогичную программу на языке Python.

Заметим, что можно не перебирать числа, большие 63, поскольку для записи чисел 28, 45 и 17 хватит шести разрядов. Программа выведет ответ 44.

Источник

Поразрядные (битовые) операции

Логические операции

Эти операции используются при построении сложных логических выражений. В эту группу входят 3 операции:

· !— логическое отрицание (логическое НЕ);

Правила записи и результаты выполнения логических операций приведены в следующей таблице:

Пусть, например, имеется математическое неравенство: 0 x) или (х > 0) && (x x > 10должно выглядеть следующим образом: (0 > x) || (10 10).

Особенностью выполнения операций && и || является то, что второй операнд (в правой части операций) вычисляется не всегда. Он вычисляется только в том случае, если значения первого операнда недостаточно для получения результата операций && или ||.

—сдвиг влево

Операции выполняют копирование битов двоичного представления первого операнда с сдвигом на количество разрядов, указанное во втором операнду, в соответствующем направлении.

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

unsigned a = 20, n = 3, r;

r = a > n;

cout > n

Значение r: 0 0 … 0 0 0 0 0 0 0 1 0 = 2

Операция сдвига влево осуществляет перемещение битов левого операнда a в сторону больших разрядов на количество разрядов, равное значению правого операнда n. Это эквивалентно умножению значения a на 2 в степени n(20 * 8 = 160).

Операция сдвига вправо осуществляет перемещение битов левого операнда a в сторону меньших разрядов на количество разрядов, равное значению правого операнда n. Это эквивалентно делению значения a на 2 в степени n(целочисленное деление 20 / 8 = 2).

Используя операцию сдвига влево очень просто получить любую целую степень двойки в диапазоне степеней равной количеству двоичных разрядов правого операнда без 1. Например, так:

Операндами этих операций целочисленных типов данных. Результат также целочисленный.

Операция побитовое отрицание (

) осуществляет инвертирование всех байтов двоичного представления своего операнда. Например:

Источник