Что такое поразрядная конъюнкция
Каждое целое число в памяти представлено в виде определенного количества разрядов. И операции сдвига позволяют сдвинуть битовое представление числа на несколько разрядов вправо или влево. Операции сдвига применяются только к целочисленным операндам. Есть две операции:
Сдвигает битовое представление числа, представленного первым операндом, влево на определенное количество разрядов, которое задается вторым операндом.
Сдвигает битовое представление числа вправо на определенное количество разрядов.
Число 2 в двоичном представлении 10. Если сдвинуть число 10 на два разряда влево, то получится 1000, что в десятичной системе равно число 8.
Число 16 в двоичном представлении 10000. Если сдвинуть число 10 на три разряда вправо (три последних разряда отбрасываются), то получится 10, что в десятичной системе представляет число 2.
Поразрядные операции
Поразрядные операции также проводятся только над разрядами целочисленных операндов:
& : поразрядная конъюнкция (операция И или поразрядное умножение). Возвращает 1, если оба из соответствующих разрядов обоих чисел равны 1
| : поразрядная дизъюнкция (операция ИЛИ или поразрядное сложение). Возвращает 1, если хотя бы один из соответствующих разрядов обоих чисел равен 1
^ : поразрядное исключающее ИЛИ. Возвращает 1, если только один из соответствующих разрядов обоих чисел равен 1
: поразрядное отрицание. Инвертирует все разряды операнда. Если разряд равен 1, то он становится равен 0, а если он равен 0, то он получает значение 1.
Например, выражение 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.
Теперь рассмотрим последний пример — инверсию числа.
Представление отрицательных чисел
Для записи чисел со знаком в Си применяется дополнительный код (two’s complement), при котором старший разряд является знаковым. Если его значение равно 0, то число положительное, и его двоичное представление не отличается от представления беззнакового числа. Например, 0000 0001 в десятичной системе 1.
Если старший разряд равен 1, то мы имеем дело с отрицательным числом. Например, 1111 1111 в десятичной системе представляет -1. Соответственно, 1111 0011 представляет -13.
Чтобы получить из положительного числа отрицательное, его нужно инвертировать и прибавить единицу:
Поразрядная конъюнкция задачи 3
Давайте разберем поразрядную конъюнкцию. Это задача, которая несколько лет была на ЕГЭ и на всех СтатГрадах, и она как-то исторически вызывает неприятные эмоции у учеников. На самом деле, ничего сложного.
Что такое поразрядная конъюнкция? Это перевод чисел в двоичную систему, а потом разряд с разрядом умножаем. Например, 7 х 4. 7 перевожу в двоичную систему – 1 1 1. 4 перевожу в двоичную систему – 1 0 0. И умножаю разряд с разрядом – 111 х 100=100.
Давайте порешаем задачи.
«Введем выражение М & К, обозначающие поразрядную конъюнкцию М и К (логическое «И» между соответствующими битами двоичной записи). Определите наименьшее натуральное число А, такое, что выражение
Начнем с короткого обозначения. Выражение Х х 56 =0 обозначим как Х56, в коротком виде. Первое уравнение принимает вид . Нам нужно найти наименьшее натуральное А.
Избавляемся от импликации. Формулу напоминать не буду, наверное, ее уже все знают наизусть.
Теперь мой любимый прием – известная часть пусть будет нулем (0), тогда искомая часть обязана быть единицей (1)
На какой-то момент я забываю про предметную область, я занимаюсь преобразованием до системы.
С нулем работать не очень приятно, поэтому сделаю отрицание и будет единица.
На что мне надо умножить 48, чтобы получились одни нули?
У X должны быть в первом разряде нули, чтобы обнулить единицы у 48, а остальное не важно
И те же самые X я должна умножить на 56 и не получить ноль. Чтобы не получить ноль, мне нужно здесь поставить единицу, чтобы она зацепила единицу от 56
Дальше может стоять что угодно. Все такие X являются решением этого уравнения.
Второе уравнение говорит, что все такие X (001…) нужно умножить на А и не получить ноль.
На первой и второй позиции у А может стоять что угодно. Три последние позиции тоже без разницы. Нужно поймать единственную единицу.
Если у А будет здесь единица, я умножу А и Х и ноль не получу. Вот такое А должно быть.
Нужно найти наименьшее. Тогда остальные пусть будут нули.
А это значит 8 в десятичной системе.
Благодарим за то, что пользуйтесь нашими статьями. Информация на странице «Поразрядная конъюнкция задачи 3» подготовлена нашими авторами специально, чтобы помочь вам в освоении предмета и подготовке к ЕГЭ и ОГЭ. Чтобы успешно сдать нужные и поступить в высшее учебное заведение или техникум нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий. Также вы можете воспользоваться другими статьями из данного раздела.
Глава 4 операции и выражения
Каждое выражение состоит из одного или нескольких операндов, символов операций и ограничителей, в качестве которых чаще всего выступают круглые скобки ().
Назначение любого выражения – формирование некоторого значения. В зависимости от типа формируемых значений определяются типы выражений.
Если значениями выражений являются целые или вещественные числа, то говорят об арифметических выражениях.
Операндами для арифметических выражений служат константы и переменные арифметических типов, а также выражения, заключенные в круглые скобки.
Выражения отношения и логические выражениятрадиционно должны давать одно значение: истина или ложь. В СИ истина – всегда ненулевое значение, 0 – ложь.
Отношение определяется как пара арифметических выражений, соединенных (разделенных) знаком операции отношения.
Операндами логических выражений являются выражения отношения.
Для формирования и последующего вычисления выражений используются операции. Для изображения одной операции в большинстве случаев используется несколько символов. В таблице приведены все знаки операций, определенные стандартом языка. Операции в таблице разбиты на группы в соответствие с их рангами.
Ассоциативность
(); []; />; .
& (поразрядная конъюнкция “И”)
^ (поразрядное исключающее “ИЛИ”)
| (поразрядная дизъюнкция “ИЛИ”)
За исключением операций “[]”, “()” и “?:” все знаки операций распознаются компилятором как отдельные лексемы. В зависимости от контекста одна и та же лексема может обозначать разные операции, т.е. один и тот же знак операции может употребляться в различных выражениях и по разному интерпретироваться в зависимости от контекста.
Например, бинарная операция & – это поразрядная конъюнкция, а унарная & – это операция получения адреса.
Порядок выполнения выражения однозначно определяется рангами и ассоциативностью входящих в него операций. Изменить данный порядок можно только используя ( ).
Операции ранга 1 имеют наивысший приоритет.
Операции одного ранга имеют одинаковый приоритет, и если их в выражении несколько, то они выполняются в соответствие с правилом ассоциативности либо слева направо (), либо справа налево (). Если один и тот же знак операции приведен в таблице дважды (например знак *), то первое появление (с меньшим по номеру, т.е. старшим по приоритету, рангом) соответствует унарной операции, а второе – бинарной.
Унарные (одноместные) операции
Для изображения одноместных префиксных и постфиксных операций используются следующие символы:
& – операция получения адреса операнда. Нельзя &(x+1).
* – операция обращения по адресу, т.е. раскрытия ссылки, иначе операция разыменования (доступа по адресу к значению того объекта, на который указывает операнд). Оператором должен быть указатель.
– – унарный минус, изменяет знак арифметического операнда.
+ – унарный плюс, введен для симметрии с унарным минусом.
– поразрядное инвертирование внутреннего двоичного кода целочисленного аргумента – побитовое отрицание.
Пример:
Unsigned char a:
A=201: (=c9 (16) = 11001001(2))
A=54: (= 36 (16) = 00110110(2))
! – логическое отрицание (НЕ) значения операнда. Применяется к стандартным операндам. Целочисленный результат 0 (если операнд не нулевой, т.е. истинный) или 1 (если операнд нулевой, т.е. ложный). Напомним, что в качестве логических значений в языке используются целые числа: 0 – ложь и не нуль, т.е. (!0) – истина. Отрицание любого ненулевого числа будет 0, а отрицанием 0 будет 1. Таким образом: !1 равно 0; !2 равно 0; !(–5) равно 0; !0 равно 1;
++ – увеличение на единицу (инкремент или автоувеличение); имеет две формы:
++<имя> префиксная операция – увеличение значения операнда на 1 до его использования. Ассоциативность справа в соответствие со стандартом.
<имя>++ постфиксная операция – увеличение значения операнда на 1 после его использования. Ассоциативность слева в соответствие со стандартом.
выражение ++m увеличивает на 1 значение m, и это полученное значение используется как значение выражения ++m (префиксная форма).
выражение – – k уменьшает на 1 значение k, и это полученное значение используется как значение выражения – –k (префиксная форма).
выражение i++ (постфиксная форма) уменьшает на 1 значение i, однако значением выражения i++ будет предыдущее значение i (до его увеличения).
выражение j – – (постфиксная форма) уменьшает на 1 значение j, однако значением выражения j – – будет предыдущее значение j (до его уменьшения.
Например
rez= arg ++*2; // rez=8, arg=5
rez=++ arg *2; // arg=6, rez=12
Внешнюю неоднозначность имеют выражения, в которых знак унарной операции ++ (или – –) записан непосредственно рядом со знаком бинарной операции +.
В этих случаях трактовка однозначно и полностью определяется рангами операций (бинарные аддитивные + имеют ранг 4;унарные ++ и –– имеют ранг 2).Таким образом:
z– – –dэквивалентно (z– –)–d.
Операнд для операции ++ (и для операции – – ) не может быть константой либо произвольным выражением. Записи ++5 или 84++ будут неверными. ++(j+k) также неверная запись. Операндами унарных операций ++ и – – должны быть всегда модифицируемые выражения (L– value, left value, l – значение, леводопустимое выражение).
Термины «леводопустимое выражение» и «l–значение» происходят от объяснения действия операции присваивания E=D, в которой операнд Е слева от знака операции присваивания может быть только модифицируемым l – значением. Примером модифицируемого l – значения служит имя переменной, которой выделена память. L – значение – ссылка на область памяти, значение которой доступно изменениям.
Sizeof – операция вычисления размера (в байтах) для объекта того типа, который имеет операнд. Разрешается два формата операции:
Пример:
sizeof (20.0) 
8 байтов
sizeof (a) 
2байта
sizeof (b) 
200байтов
sizeof (*x) 
2байта
sizeof (int) 
2байта
sizeof (date) 
12байтов
Что такое поразрядная конъюнкция
Во всех языках программирования под выражением подразумевается конструкция, составленная из констант, переменных, знаков операций, функций, скобок. Выражение определяет порядок вычисления некоторого значения. Если это числовое значение, то такое выражение называют арифметическим. Вот несколько примеров арифметических выражений, записанных по правилам языка Си:
х++ х+++ b — — n *2 n *=1
Три первых выражения имеют традиционную форму для языков программирования высокого уровня, поэтому их смысл очевиден. Следующие четыре выражения специфичны для языка Си.
Опишем набор операций, используемых в Си, а также правила записи и вычисления выражений. Напомним, что операция, применяемая к одному операнду, называется унарной, а операция с двумя операндами — бинарной.
Арифметические операции . К арифметическим операциям относятся:
— вычитание или унарный минус;
+ сложение или унарный плюс;
% деление по модулю ;
++ унарная операция увеличения на единицу (инкремент);
— — унарная операция уменьшения на единицу (декремент).
Все операции, кроме деления по модулю, применимы к любым числовым типам данных. Операция % применима только к целым числам.
Рассмотрим особенности выполнения операции деления. Если делимое и делитель — целые числа, то и результат — целое число. Например, значение выражения 5/3 будет равно 2, а при вычислении 1/5 получится 0 .
Если хотя бы один из операндов имеет вещественный тип, то и результат будет вещественным. Например, операции 5./3, 5./3., 5/3. дадут вещественный результат 1.6666.
Операции инкремента и декремента могут применяться только к переменным и не могут — к константам и выражениям. Операция ++ увеличивает значение переменной на единицу, операция — — — уменьшает значение переменной на единицу. Оба знака операции могут записываться как перед операндом (префиксная форма), так и после операнда (постфиксная форма), например: ++х или х++, —а или а—. Три следующих оператора дают один и тот же результат:
Различие проявляется при использовании префиксной и постфиксной форм в выражениях. Проиллюстрируем это на примерах. Первый пример:
В результате выполнения переменные получат следующие значения: а = 4, b = 3, с= 6. Второй пример:
Результаты будут такими: а = 4, b = 3, с=12.
Объяснение следующее: при использовании постфиксной формы операции ++ и — — выполняются после того, как значение переменной было использовано в выражении, а префиксные операции — до использования. Поэтому в первом примере значение переменной с вычислялось как произведение 3 на 2, а во втором — как произведение 4 на 3.
По убыванию старшинства арифметические операции расположены в следующем порядке:
Одинаковые по старшинству операции выполняются в порядке слева направо. Д ля изменения порядка выполнения операций в выражениях могут применяться круглые скобки.
Операции отношения . В Си используется тот же набор операций отношения .
<= меньше или равно,
>= больше или равно, равно,
Как уже говорилось раньше, в стандарте Си нет логического типа данных. Поэтому результатом операции отношения является целое число: если отношение истинно — то 1, если ложно — то 0.
Результатом второго и третьего отношений будет 0 — ложь; результат четвертого отношения равен 1 — истина; результат первого отношения зависит от значения переменной а.
Логические операции . Три основные логические операции в языке Си:
! операция отрицания (НЕ),
&& конъюнкция, логическое умножение (И),
| | дизъюнкция, логическое сложение (ИЛИ).
Например, логическое выражение, соответствующее системе неравенств 0 < x < 1 в программе на Си запишется в виде следующего логического выражения:
Обратите внимание на то обстоятельство, что здесь не понадобились круглые скобки для выделения операций отношения. В Си операции отношения старше конъюнкции и дизъюнкции. По убыванию приоритета логические операции и операции отношения расположены в следующем порядке:
Помимо рассмотренных в Си имеются поразрядные логические операции. Эти операции выполняются над каждой парой соответствующих двоичных разрядов внутреннего представления операндов. Их еще называют битовыми логическими операциями. Знаки битовых логических операций:
& поразрядная конъюнкция (И),
| поразрядная дизъюнкция (ИЛИ),
^ поразрядное исключающее ИЛИ,
поразрядное отрицание (НЕ).
Битовые логические операции вместе с операциями поразрядного сдвига влево (<<) и вправо (>>) позволяют добраться до каждого бита внутреннего кода. Чаще всего такие действия приходится выполнять в системных программах.
Операция присваивания. Знак операции присваивания =. Следствием отмеченного факта является то, что присваивание, как любой другой знак операции, может несколько раз входить в выражение. Например:
Присваивание имеет самый низкий приоритет (ниже только у операции «запятая»). Кроме того, операция присваивания — правоассоциативная. Это значит, что несколько подряд расположенных присваиваний выполняются справа налево. Поэтому в приведенном выше выражении первой выполнится операция сложения, затем переменной с присвоится значение суммы, затем это значение присвоится переменной b и в конце — переменной а.
В языке Си имеются дополнительные операции присваивания, совмещающие присваивание с выполнением других операций. Среди них: +=, -=, /=, *=, %=. Приоритет у них такой же, как и у простого присваивания. Примеры использования этих операций:
а+=2 эквивалентно а=а+2,
х-=а+ b эквивалентно х=х-(а+ b ),
р/=10 эквивалентно р=р/10,
m*=n эквивалентно m=m*n,
г%=5 эквивалентно г=г%5.
Заметим, что вместо выражения а=а+2 предпочтительнее писать в программе а+=2, поскольку второе выражение будет вычисляться быстрее.
Операция явного преобразования типа (операция «тип»). Применение этой операции имеет следующий формат:
Операндом могут быть константа, переменная, выражение. В результате значение операнда преобразуется к указанному типу. Примеры использования преобразования типа:
(long) 8, (float) 1 , (int) x%2
По поводу последнего выражения заметим, что приоритет операции «тип» выше деления (и других бинарных арифметических операций), поэтому сначала значение переменной х приведется к целому типу (отбросится дробная часть), а затем выполнится деление по модулю.
Следующий фрагмент программы иллюстрирует одну из практических ситуаций, в которой потребовалось использовать преобразование типа:
В результате переменная с получит значение 0,5. Без преобразования типа ее значение стало бы равно 0.
Операция sizeof . Эта операция имеет две формы записи:
sizeof (тип) и sizeof (выражение)
Результатом операции является целое число, равное количеству байтов, которое занимает в памяти величина явно указанного типа или величина, полученная в результате вычисления выражения. Последняя определяется также по типу результата выражения. Хотя по форме записи это похоже на функцию, однако sizeof является именно операцией. Ее приоритет выше, чем у бинарных арифметических операций, логических операций и отношений. Примеры использования операции:
sizeof (int) результат — 2
sizeof (1) результат — 2
sizeof (0.1) результат — 8
sizeof (1L) результат — 4
sizeof (char) результат — 1
sizeof (‘ a’) результат — 2
Операция «запятая». Эта необычная операция используется для связывания нескольких выражений в одно. Несколько выражений, разделенных запятыми, вычисляются последовательно слева направо. В качестве результата такого совмещенного выражения принимается значение самого правого выражения. Например, если переменная х имеет тип int, то значение выражения (х=3, 5*х) будет равно 15, а переменная х примет значение 3.
Операция “ условие ?: ” . Это единственная операция, которая имеет три операнда. Формат операции:
выражение1 ? выражение2 : выражение 3
Данная операция реализует алгоритмическую структуру ветвления. Алгоритм ее выполнения следующий: первым вычисляется значение выражения 1, которое обычно представляет собой некоторое условие. Если оно истинно, т.е. не равно 0, то вычисляется выражение 2 и полученный результат становится результатом операции. В противном случае в качестве результата берется значение выражения 3.
Пример 1. Вычисление абсолютной величины переменной X можно организовать с помощью одной операции:
Пример 2. Выбор большего значения из двух переменных аи Ь:
Пример 3. Заменить большее значение из двух переменных аи b на единицу:
Правила языка в данном случае позволяют ставить условную операцию слева от знака присваивания.
Операции ( ) и [ ]. В языке Си круглые и квадратные скобки рассматриваются как операции, причем эти операции имеют наивысший приоритет. Их смысл будет раскрыт позже.
Подведем итог всему разговору об операциях Си/Си++, сведя их в общую табл. 2 и расположив по рангам. Ранг операции — это порядковый помер в ряду приоритетов. Чем больше ранг, тем ниже приоритет. В таблице отражено еще одно свойство операций — ассоциативность. Если одна и та же операция, повторяющаяся в выражении несколько раз, выполняется в порядке расположения слева направо, то она называется левоассоциа-тивной; если выполняется справа налево, то операция правоассоциативная. В таблице эти свойства отображены стрелками влево и вправо. Некоторые операции, присутствующие в таблице, пока не обсуждались.