Какого типа будет результат операции 4 2
Перейти к содержимому

Какого типа будет результат операции 4 2

  • автор:

Типы данных результатов оператора (Visual Basic)

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

Диапазоны типов данных

Диапазоны соответствующих типов данных в порядке от наименьшего до наибольшего:

  • Логическое значение — два возможных значения.
  • SByte, Byte — 256 возможных целочисленных значений
  • Short, UShort — 65 536 (6,5. E+4) возможных целочисленных значений
  • Integer, UInteger — 4 294 967 296 (4,2. E+9) возможные целочисленные значения
  • Long, ULong — 18 446 744 073 709 551 615 (1,8. E+19) возможные целочисленные значения
  • Decimal — 1,5. E+29 возможных целочисленных значений, максимальный диапазон 7,9. E+28 (абсолютное значение)
  • Один — максимальный диапазон 3,4. E+38 (абсолютное значение)
  • Double — максимальный диапазон 1,7. E+308 (абсолютное значение)

Дополнительные сведения о типах данных Visual Basic см. в разделе Типы данных.

Если операнд имеет значение Nothing, арифметические операторы Visual Basic считают его нулевым.

Десятичная арифметика

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

Если один из операндов + операции , – , * , / или Mod имеет значение Decimal , а другой — нет Single или Double , Visual Basic расширяет другой операнд до Decimal . Он выполняет операцию в Decimal , а результирующий тип данных — Decimal .

Floating-Point арифметика

Visual Basic выполняет большинство арифметических операций с плавающей запятой в Double, который является наиболее эффективным типом данных для таких операций. Однако если один операнд имеет значение Single , а другой — нет Double , Visual Basic выполняет операцию в Single . Он расширяет каждый операнд по мере необходимости до соответствующего типа данных перед операцией, и результат имеет этот тип данных.

Операторы / и ^

Оператор / определяется только для типов данных Decimal, Single и Double . Visual Basic расширяет каждый операнд по мере необходимости до соответствующего типа данных перед операцией, и результат имеет этот тип данных.

В следующей таблице показаны типы результирующих данных для / оператора . Обратите внимание, что эта таблица является симметричной; Для заданного сочетания типов данных операндов результирующий тип данных является одинаковым независимо от порядка операндов.

Decimal Single Double Любой целочисленный тип
Decimal Decimal Single Double Decimal
Single Single Single Double Single
Double Double Double Double Double
Любой целочисленный тип Decimal Single Double Double

Оператор ^ определяется только для Double типа данных. Visual Basic расширяет каждый операнд по мере необходимости до Double перед операцией, а результирующий тип данных всегда Double имеет значение .

Целочисленная арифметика

Тип результирующих данных целочисленной операции зависит от типов данных операндов. Как правило, Visual Basic использует следующие политики для определения типа результирующих данных:

  • Если оба операнда двоичного оператора имеют одинаковый тип данных, результат имеет этот тип данных. Исключением является Boolean , который принудительно используется для Short .
  • Если неподписанный операнд участвует в подписанном операнде, результат имеет тип со знаком, по крайней мере с таким же большим диапазоном, как и любой из операндов.
  • В противном случае результат обычно имеет больший из двух типов данных операнда.

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

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

Унарные операторы + и –

В следующей таблице показаны типы результирующих данных для двух унарных операторов и + – .

Boolean SByte Byte Short UShort Integer UInteger Long ULong
Унарные + Short SByte Byte Short UShort Целочисленный тип UInteger Long ULong
Унарные – Short SByte Short Short Целочисленный тип Целое число Long Long Decimal

В следующей таблице показаны типы результирующих данных для двух операторов битового сдвига и > . Visual Basic рассматривает каждый оператор битового сдвига как унарный оператор в левом операнде (шаблон бита, который необходимо сдвинуть).

Boolean SByte Byte Short UShort Integer UInteger Long ULong
> Short SByte Byte Short UShort Целочисленный тип UInteger Long ULong

Если левый операнд имеет значение , , или , Visual Basic пытается Long преобразовать его в до операции, а результирующий тип данных — Long . String Double Single Decimal Правый операнд (число битовых позиций для сдвига) должен быть Integer или типом, расширяющимся до Integer .

Бинарные операторы +, –, *и Mod

В следующей таблице показаны типы результирующих данных для двоичных + операторов и – операторов * и и Mod . Обратите внимание, что эта таблица является симметричной; Для заданного сочетания типов данных операндов результирующий тип данных является одинаковым независимо от порядка операндов.

Boolean SByte Byte Short UShort Integer UInteger Long ULong
Boolean Short SByte Short Short Целочисленный тип Целое число Long Long Decimal
SByte SByte SByte Short Short Целочисленный тип Целое число Long Long Decimal
Byte Short Short Byte Short UShort Целочисленный тип UInteger Long ULong
Short Short Short Short Short Целочисленный тип Целое число Long Long Decimal
UShort Целочисленный тип Целое число UShort Целое число UShort Целочисленный тип UInteger Long ULong
Integer Целочисленный тип Целочисленный тип Целочисленный тип Целочисленный тип Целочисленный тип Целое число Long Long Decimal
UInteger Long Long UInteger Long UInteger Long UInteger Long ULong
Long Long Long Long Long Long Long Long Long Decimal
ULong Decimal Decimal ULong Decimal ULong Decimal ULong Decimal ULong

Оператор \

В следующей таблице показаны типы результирующих данных для \ оператора . Обратите внимание, что эта таблица является симметричной; Для заданного сочетания типов данных операндов результирующий тип данных является одинаковым независимо от порядка операндов.

Boolean SByte Byte Short UShort Integer UInteger Long ULong
Boolean Short SByte Short Short Целочисленный тип Целое число Long Long Long
SByte SByte SByte Short Short Целочисленный тип Целое число Long Long Long
Byte Short Short Byte Short UShort Целочисленный тип UInteger Long ULong
Short Short Short Short Short Целочисленный тип Целое число Long Long Long
UShort Целочисленный тип Целое число UShort Целое число UShort Целочисленный тип UInteger Long ULong
Integer Целочисленный тип Целочисленный тип Целочисленный тип Целочисленный тип Целочисленный тип Целое число Long Long Long
UInteger Long Long UInteger Long UInteger Long UInteger Long ULong
Long Long Long Long Long Long Long Long Long Long
ULong Long Long ULong Long ULong Long ULong Long ULong

Если операнд \ оператора имеет значение Decimal, Single или Double, Visual Basic пытается преобразовать его в long перед операцией, а результирующий тип данных — Long .

Реляционные и побитовые сравнения

Результирующий тип данных реляционной операции ( = , <> , < , >, = ) всегда Boolean является логическим типом данных. То же самое верно для логических операций ( And , , Not AndAlso , Or , OrElse , Xor ) с Boolean операндами.

Тип результирующих данных побитовой логической операции зависит от типов данных операндов. Обратите внимание, что AndAlso и OrElse определяются только для Boolean , а Visual Basic преобразует каждый операнд по мере необходимости Boolean в перед выполнением операции.

Операторы =, <>, = =

Если оба операнда имеют значение Boolean , Visual Basic считает True , что меньше False . Если числовой тип сравнивается с String , Visual Basic пытается преобразовать в String Double перед операцией. Операнд Char или Date можно сравнить только с другим операндом того же типа данных. Результирующий тип данных всегда Boolean имеет значение .

Оператор Bitwise Not

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

Boolean SByte Byte Short UShort Integer UInteger Long ULong
Not Логический SByte Byte Short UShort Целочисленный тип UInteger Long ULong

Если операнд имеет значение , , или String , Visual Basic пытается Long преобразовать его в до операции, а результирующий тип данных — Long . Double Single Decimal

Побитовые операторы And, Or и Xor

В следующей таблице показаны типы результирующих данных для побитовых And операторов , Or и Xor . Обратите внимание, что эта таблица симметричная; Для заданного сочетания типов данных операндов результирующий тип данных является одинаковым независимо от порядка операндов.

Boolean SByte Byte Short UShort Integer UInteger Long ULong
Boolean Логический SByte Short Short Целочисленный тип Целое число Long Long Long
SByte SByte SByte Short Short Целочисленный тип Целое число Long Long Long
Byte Short Short Byte Short UShort Целочисленный тип UInteger Long ULong
Short Short Short Short Short Целочисленный тип Целое число Long Long Long
UShort Целочисленный тип Целое число UShort Целое число UShort Целочисленный тип UInteger Long ULong
Integer Целочисленный тип Целочисленный тип Целочисленный тип Целочисленный тип Целочисленный тип Целое число Long Long Long
UInteger Long Long UInteger Long UInteger Long UInteger Long ULong
Long Long Long Long Long Long Long Long Long Long
ULong Long Long ULong Long ULong Long ULong Long ULong

Если операнд имеет значение , , или String , Visual Basic пытается преобразовать его Long в до операции, а результирующий тип данных будет таким же, как если бы этот операнд уже был Long . Double Single Decimal

Прочие операторы

Оператор & определяется только для объединения String операндов. Visual Basic преобразует каждый операнд по мере необходимости String в до операции, а результирующий тип данных всегда String имеет значение . Для целей & оператора все преобразования в String считаются расширяющимися, даже если Option Strict имеет значение On .

Операторы Is и IsNot требуют, чтобы оба операнда были ссылочного типа. Выражение TypeOf . Is требует, чтобы первый операнд был ссылочного типа, а второй — имя типа данных. Во всех этих случаях результирующий тип данных — Boolean .

Оператор Like определяется только для сопоставления шаблонов String операндов. Visual Basic пытается преобразовать каждый операнд по мере необходимости в String перед операцией. Результирующий тип данных всегда Boolean имеет значение .

См. также раздел

  • Типы данных
  • Операторы и выражения
  • Арифметические операторы в Visual Basic
  • Comparison Operators in Visual Basic
  • Операторы
  • Порядок применения операторов в Visual Basic
  • Список операторов, сгруппированных по функциональному назначению
  • Арифметические операторы
  • Операторы сравнения
  • Оператор Option Strict

Совместная работа с нами на GitHub

Источник этого содержимого можно найти на GitHub, где также можно создавать и просматривать проблемы и запросы на вытягивание. Дополнительные сведения см. в нашем руководстве для участников.

Ввод-вывод, оператор присваивания, арифметические операции

Язык программирования Паскаль. Знакомство со средой программирования Турбо Паскаль. Основные понятия. Первая программа

Паскаль — язык профессионального программирования, который назван в честь французского математика и философа Блеза Паскаля (1623-1662) и разработан в 1968-1971 гг. Никлаусом Виртом. Первоначально был разработан для обучения, но вскоре стал использоваться для разработки программных средств в профессиональном программировании.

Паскаль популярен среди программистов по следующим причинам:

  1. Прост для обучения.
  2. Отражает фундаментальные идеи алгоритмов в легко воспринимаемой форме, что предоставляет программисту средства, помогающие проектировать программы.
  3. Позволяет четко реализовать идеи структурного программирования и структурной организации данных.
  4. Использование простых и гибких структур управления: ветвлений, циклов.
  5. Надежность разрабатываемых программ.

Турбо Паскаль — это система программирования, созданная для повышения качества и скорости разработки программ (80-е гг.). Слово Турбо в названии системы программирования — это отражение торговой марки фирмы-разработчика Borland International (США).

Систему программирования Турбо Паскаль называют интегрированной (integration — объединение отдельных элементов в единое целое) средой программирования, т.к. она включает в себя редактор, компилятор, отладчик, имеет сервисные возможности.

Основные файлы Турбо Паскаля:

Turbo.exe — исполняемый файл интегрированной среды программирования;

Turbo.hlp — файл, содержащий данные для помощи;

Turbo.tp — файл конфигурации системы;

Turbo.tpl — библиотека стандартных модулей, в которых содержатся встроенные процедуры и функции (SYSTEM, CRT, DOS, PRINTER, GRAPH, TURBO3, GRAPH3).

Запуск интегрированной среды программирования

Для запуска интегрированной среды программирования нужно установить текущим каталог с Турбо Паскалем (TP7\BIN) и ввести команду: turbo.exe.

Задание. Запустите среду программирования и рассмотрите экран. Перед вами полоса меню, область окна и строка статуса. Нажмите клавишу F10 — теперь вам доступны все опции меню. Используя клавиши управления курсором, рассмотрите меню. С командами меню мы будем знакомиться постепенно. Нажмите клавишу Esc (вы вышли из меню). Перемещая курсор в окне, следите за строкой статуса. Какая информация отражается в этой строке?

Почти все, что вы видите и делаете в среде Турбо Паскаль, происходит в окнах.

Окно — это область экрана, которую можно перемещать, изменять в размере, перекрывать, закрывать и открывать.

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

Активное окно – это окно, с которым вы в настоящий момент работаете.

Общие горячие клавиши:

F2 — сохраняет файл активного окна;

F3 — появление диалогового окна и возможность открыть файл;

F4 — запускает программу до строки, на которой стоит курсор;

F5 — масштабирует диалоговое окно;

F6 — переходит к следующему открытому окну;

F7 — запускает программу в режиме отладки с заходом внутрь процедур;

F8 — запускает программу в режиме отладки, минуя вызов процедур;

F9 — компилирование программы в текущем окне;

F10 — возвращение в меню.

Мы начнем изучение меню с наиболее важных и необходимых режимов.

Как войти в меню? Всего есть три возможности:

С помощью клавиш управления курсором подсветите слово FILE и нажмите клавишу «Enter». Что вы видите?

Появилась вертикальная таблица со списком команд, называемая выпадающим меню. Познакомимся с ним.

Open-F3 — открыть существующий файл (при активизации этой опции появляется окно со списком файлов, где можно выбрать необходимый),

New — создать новый файл (очищает память редактора и переводит в режим создания нового файла, которому присваивается имя Noname.pas; имя можно изменить при записи файла на диск),

Save-F2 — сохранить файл (переписывает файл из памяти редактора на диск),

Save as — сохранить с новым именем,

Save all — сохранить все в окнах (записывает содержимое всех окон редактора в соответствующие файлы),

Change dir — смена каталога (позволяет изменить установленный по умолчанию диск или каталог),

Print — печать файла,

Get info — выдача информации о текущем состоянии программы и используемой памяти,

DOS Shell — выход в DOS без выгрузки из памяти (для возврата ввести команду exit),

Exit — выход и выгрузка из памяти.

Программы на языке Паскаль имеют блочную структуру:

1. Блок типа PROGRAM — имеет имя, состоящее только из латинских букв и цифр. Его присутствие не обязательно, но рекомендуется записывать для быстрого распознавания нужной программы среди других листингов.

2. Программный блок, состоящий в общем случае из 7 разделов:

    раздел описания модулей (uses);

Общая структура программы на языке Паскаль следующая:

Начнем знакомство с Паскалем с программы, которая складывает два числа и выводит сумму на экран.

Откройте файл, в который Вы запишите эту программу. Для этого нажмите клавишу F10, чтобы выйти в главное меню, затем клавишами перемещения курсора выберите опцию File, а в выпавшем меню команду New.

Примечание. Обратите внимание на оформление текста программы.

    Найдите в этой программе заголовок, раздел описания переменных, признак начала программы, признак конца программы, тело программы, комментарий.

А теперь подведем итог вашим размышлениям.

Имя этой программы Summa2. Заметим, что требования к имени выполняются: оно отражает содержание программы, а также не содержит недопустимых символов.

Далее идет специально выделенный комментарий, в котором вы должны записать подробно условие задачи и указать, кто написал эту программу и когда.

Из разделов описаний имеется лишь один — раздел переменных. Он начинается со служебного слова Var. Мы описали три переменные: number1, number2, result. Все они переменные целого типа. Поэтому мы перечислили их через запятую, поставили двоеточие и указали тип переменных. Подобные объявления разделяются между собой точкой с запятой.

После описательной части идет раздел операторов, начинающийся со служебного слова Begin, после которого идут операторы языка.

Недостатком этой программы является то, что значения переменных постоянны. А нам нужно научиться писать такие программы, которые решают поставленные задачи в общем виде, т. е. для любых значений переменных. Для этого мы научимся запрашивать значения у пользователя, анализировать их и выдавать соответствующий результат.

Какого типа будет результат операции 4 2

Как мы уже упоминали, для каждого типа данных определены действия, применимые к его значениям. Например, если переменная относится к порядковому типу данных , то она может фигурировать в качестве аргумента стандартных функций Ord () , Pred () и Succ () (см. п. « Совместимость типов данных » ниже). А к вещественным типам эти функции применить невозможно.

Итак, поговорим теперь об операциях — стандартных действиях, разрешённых для переменных того или иного базового типа данных. Основу будут составлять арифметические операции , но, конечно же, мы не забудем и о логическом типе данных (операции, определённые для значений символьного типа , будут подробно рассмотрены в лекции 5 ).

Замечание: Все перечисленные ниже операции (за исключением унарных «-» , «+» и not ) требуют двух операндов.

    Логические операции (and, or, not, xor) применимы только к значениям типа Boolean . Их результатом также служат величины типа Boolean . Приведём таблицы значений для этих операций:

Оператор Операнд 1 Операнд 2 Результат
not False True
True False
and False False False
False True False
True False False
True True True
or False False False
False True True
True False True
True True True
xor False False False
False True True
True False True
True True False

a div b — деление а на b нацело (не нужно, наверное, напоминать, что деление на 0 запрещено, поэтому в таких случаях операция выдаёт ошибку). Результат будет принадлежать к типу данных, общему для тех типов, к которым принадлежат операнды. Например, (ShortInt div Byte = Integer). Пояснить это можно так: Integer — это минимальный тип, подмножествами которого являются одновременно и Byte , и ShortInt . a mod b — взятие остатка при делении а на b нацело. Тип результата, как и в предыдущем случае, определяется типами операндов, а 0 является запрещённым значением для b. В отличие от математической операции mod, результатом которой всегда является неотрицательное число, знак результата «программистской» операции mod определяется знаком её первого операнда. Таким образом, если в математике (-2 mod 5) = 3, то у нас (-2 mod 5) = -2. a shl k — сдвиг значения а на k битов влево (это эквивалентно умножению значения переменной а на 2 k ). Результат операции будет иметь тот же тип, что и первый её операнд (а). a shr k — сдвиг значения а на k битов вправо (это эквивалентно делению значения переменной а на 2 k нацело). Результат операции будет иметь тот же тип, что и первый её операнд (а). and, or, not, xor — операции двоичной арифметики , работающие с битами двоичного представления целых чисел, по тем же правилам, что и соответствующие им логические операции .

Другие операции

Помимо арифметических, существуют и другие операции, специфичные для значений некоторых стандартных типов данных языка Pascal. Эти операции мы рассмотрим в соответствующих разделах:

Стандартные арифметические функции

К арифметическим операциям примыкают и стандартные арифметические функции . Их список с кратким описанием мы приводим в таблице.

Описание Тип аргумента Тип результата 1
Abs (x) Абсолютное значение (модуль) числа Арифметический Совпадает с типом аргумента
ArcTan (x) Арктангенс (в радианах) Арифметический Вещественный
Cos (x) Косинус (в радианах) Арифметический Вещественный
Exp (x) Экспонента (e x ) Арифметический Вещественный
Frac (x) Взятие дробной части числа Арифметический Вещественный
Int (x) Взятие целой части числа Арифметический Вещественный
Ln (x) Натуральный логарифм (по основанию e) Арифметический Вещественный
Odd (x) Проверка нечётности числа Целый Boolean
Pi Значение числа π Вещественный
Round (x) Округление к ближайшему целому Арифметический Целый
Trunc (x) Округление «вниз» — к ближайшему меньшему целому Арифметический Целый
Sin (x) Синус (в радианах) Арифметический Вещественный
Sqr (x) Возведение в квадрат Арифметический Совпадает с типом аргумента
Sqrt (x) Извлечение квадратного корня Арифметический Вещественный
Арифметические выражения

Все арифметические операции можно сочетать друг с другом — конечно, с учётом допустимых для их операндов типов данных.

В роли операндов любой операции могут выступать переменные, константы, вызовы функций или выражения, построенные на основе других операций. Всё вместе и называется выражением . Определение выражения через выражение не должно вас смущать, ведь рекурсивное задание конструкций вообще свойственно программированию (см. лекцию 9 ).

(x < 0) and (y > 0) — выражение, результат которого принадлежит к типу Boolean ;

z shl Abs (k) — вторым операндом является вызов стандартной функции;

(x mod k) + Min(a,b) + Trunc (z) — сочетание арифметических операций и вызовов функций;

Odd ( Round (x / Abs (x))) — «многоэтажное» выражение.

Полнота вычислений
if (x 

то для случая, когда x положительно, этих сложных вычислений можно избежать.

Порядок вычислений

Если в выражении расставлены скобки, то вычисления производятся в порядке, известном всем ещё с начальной школы: чем меньше глубина вложенности скобок, тем позже вычисляется заключённая в них операция. Если же скобок нет, то сначала вычисляются значения операций с более высоким приоритетом , затем — с менее высоким. Несколько подряд идущих операций одного приоритета вычисляются в последовательности «слева направо».

Таблица 2.1. Приоритеты (для всех) операций языка Pascal Операции Приоритет
Унарные 2 операции+, -, not, @, ^, #Первый(высший)
Операции, эквивалентные умножению*, /, div, mod, and, shl, shrВторой
Операции, эквивалентные сложению+, -, or, xorТретий
Операции сравнения=, <>, >, =, inЧетвёртый

Замечание: Вызов любой функции имеет более высокий приоритет, чем все внешние относительно этого вызова операции. Выражения, являющиеся аргументами вызываемой функции, вычисляются в момент вызова (см. лекцию 8 ).

Примеры выражений (с указанием последовательности вычислений) для целых чисел:

страницы: 1 2 3

Побитовые операции

Побитовые операции (англ. bitwise operations) — операции, производимые над цепочками битов. Выделяют два типа побитовых операций: логические операции и побитовые сдвиги.

Принцип работы

Логические побитовые операции

Битовые операторы И [math](AND,\ \&)[/math] , ИЛИ [math](OR,\ \mid)[/math] , НЕ [math](NOT,\ \sim)[/math] и исключающее ИЛИ [math](XOR,\ $\textasciicircum$,\ \oplus)[/math] используют те же таблицы истинности, что и их логические эквиваленты.

Побитовое И

Побитовое И используется для выключения битов. Любой бит, установленный в [math]0[/math] , вызывает установку соответствующего бита результата также в [math]0[/math] .

&
11001010
11100010
11000010
Побитовое ИЛИ

Побитовое ИЛИ используется для включения битов. Любой бит, установленный в [math]1[/math] , вызывает установку соответствующего бита результата также в [math]1[/math] .

|
11001010
11100010
11101010
Побитовое НЕ

Побитовое НЕ инвертирует состояние каждого бита исходной переменной.

~
11001010
00110101
Побитовое исключающее ИЛИ

Исключающее ИЛИ устанавливает значение бита результата в [math]1[/math] , если значения в соответствующих битах исходных переменных различны.

^
11001010
11100010
00101000

Побитовые сдвиги

Операторы сдвига [math]\lt \lt [/math] и [math]<\gt \gt >[/math] сдвигают биты в переменной влево или вправо на указанное число. При этом на освободившиеся позиции устанавливаются нули (кроме сдвига вправо отрицательного числа, в этом случае на свободные позиции устанавливаются единицы, так как числа представляются в двоичном дополнительном коде и необходимо поддерживать знаковый бит).

Сдвиг влево может применяться для умножения числа на два, сдвиг вправо — для деления.

x = 7 // 00000111 (7) x = x >> 1 // 00000011 (3) x = x // 00000110 (6) x = x // 11000000 (-64) x = x >> 2 // 11110000 (-16) 

В языке программирования Java существует также оператор беззнакового битового сдвига вправо [math]\gt \gt \gt [/math] . При использовании этого оператора на освободившиеся позиции всегда устанавливаются нули.

x = 7 // 00000111 (7) x = x // 11100000 (-32) x = x >>> 2 // 00111000 (56) 

Применение

Сложные операции

Определение знака числа

Пусть дано число [math]x[/math] . Поскольку при сдвиге вправо на освобождающиеся позиции устанавливается бит знака, знак числа [math]x[/math] можно определить, выполнив сдвиг вправо на всю длину переменной:

int32 getSign(x: int32): if x != 0: mask = 1 else: mask = 0 return mask | (x >> 31) // результатом будет -1, 0, или +1 // для отрицательного, равного нулю и положительного числа x соответственно 

Используя побитовые операции можно также узнать, различны ли знаки двух переменных [math]x[/math] и [math]y[/math] . Если числа имеют различный знак, то результат операции XOR, произведенной над их знаковыми битами, будет единицей. Поэтому неравенство [math](x \oplus y) \lt 0[/math] будет верно в том случае, если числа [math]x[/math] и [math]y[/math] разного знака.

Вычисление модуля числа без использования условного оператора

Пусть дано число [math]x[/math] . Если [math]x[/math] положительно, то [math]mask = 0[/math] , и [math](x + mask) \oplus mask = x[/math] . В случае, если [math]x[/math] отрицательно, [math]mask = -1[/math] . Тогда получается, что мы работаем с числом [math]x[/math] так, как будто оно представлено в коде со сдвигом с тем отличием, что у нас знаковый бит принимает значение [math]1[/math] для отрицательных чисел, а [math]0[/math] — для положительных.

int32 abs1(x: int32): mask = x >> 31 return (x + mask) XOR mask int32 abs2(x: int32): mask = x >> 31 return (x + mask) XOR mask
Нахождение минимума и максимума из двух чисел без использования условного оператора

Этот способ корректен только если можно утверждать, что величина [math](x - y)[/math] лежит между граничными значениями типа int.

Пусть даны числа [math]x[/math] и [math]y[/math] разрядности [math]n[/math] . Тогда если [math]x \lt y[/math] , то [math]((x - y) \gt \gt (n - 1)) = -1[/math] , а если [math]x \geqslant y[/math] , то [math]((x - y) \gt \gt (n - 1)) = 0[/math] . Выражение [math]((x - y) \& ((x - y) \gt \gt (n - 1))[/math] принимает значение [math]0[/math] , если [math]x \geqslant y[/math] , и [math](x - y)[/math] , если [math]x \lt y[/math] .

int32 min(x, y: int32): return y + ((x - y) & ((x - y) >> 31)) int32 max(x, y: int32): return x - ((x - y) & ((x - y) >> 31))
Проверка на то, является ли число степенью двойки

Пусть дано число [math]x[/math] . Тогда, если результатом выражения [math](x\ \&\&\ !(x\ \&\ (x - 1)))[/math] является единица, то число [math]x[/math] — степень двойки.

Правая часть выражения [math](!(x\ \&\ (x - 1)))[/math] будет равна единице, только если число [math]x[/math] равно [math]0[/math] или является степенью двойки. Если число [math]x[/math] является степенью двойки, то в двоичной системе счисления оно представляется следующим образом: [math]1\underbrace_[/math] , где [math]n[/math] — показатель степени. Соответственно, выражение [math](x - 1)[/math] будет иметь вид [math]\underbrace_[/math] , и [math]x\ \&\ (x - 1)[/math] равно [math]0[/math] .

Операция логического И в данном выражении отсекает тот случай, когда [math](x = 0)[/math] и не является степенью двойки, но при этом правая часть [math](!(x\ \&\ (x - 1)))[/math] равна единице.

Нахождение младшего единичного бита

Пусть дано число [math]x[/math] и необходимо узнать его младший единичный бит.

Применим к числу [math]x[/math] побитовое отрицание, чтобы инвертировать значения всех его бит, а затем прибавим к полученному числу единицу. У результата первая часть (до младшего единичного бита) не совпадает с исходным числом [math]x[/math] , а вторая часть совпадает. Применив побитовое И к этим двум числам, получим степень двойки, соответствующую младшему единичному биту исходного числа [math](x\ \&\ (\sim x + 1))[/math] .

К такому же результату можно прийти, если сначала отнять от числа [math]x[/math] единицу, чтобы обнулить его младший единичный бит, а все последующие разряды обратить в [math]1[/math] , затем инвертировать результат и применить побитовое И с исходным числом [math](x\ \&\ \sim (x - 1))[/math] .

Нахождение старшего единичного бита

Пусть дано число [math]x[/math] и необходимо узнать его старший единичный бит.

Рассмотрим некоторое число, представим его как [math]0\dots01b \dots b[/math] , где [math]b[/math] — любое значение бита. Тогда, если совершить битовый сдвиг этого числа вправо на [math]1[/math] и произвести побитовое ИЛИ результата сдвига и исходного числа, мы получим результат [math]0\dots011b \dots b[/math] . Если мы повторим эту последовательность действий над полученным числом, но устроим сдвиг на [math]2[/math] , то получим [math]0\dots01111b \dots b[/math] . При каждой следующей операции будем увеличивать модуль сдвига до следующей степени двойки. После некоторого количества таких операций (зависит от разрядности числа) мы получим число вида [math]0\dots01\dots1[/math] . Тогда результатом выполнения действий [math]x - (x \texttt< \gt \gt >1)[/math] будет число, состоящее только из старшего бита исходного числа.

int32 greatestBit(x: int32): power = 1 for i = 1 [math] \ldots\log_2[/math]: x |= x >> power power return x - (x >> 1)
Циклический сдвиг

Пусть дано число [math]x[/math] и надо совершить циклический сдвиг его битов на величину [math]d[/math] . Желаемый результат можно получить, если объединить числа, полученные при выполнении обычного битового сдвига в желаемую сторону на [math]d[/math] и в противоположном направлении на разность между разрядностью числа и величиной сдвига. Таким образом, мы сможем поменять местами начальную и конечную части числа.

int32 rotateLeft(x, d: int32): return (x >> (32 - d)) int32 rotateRight(x, d: int32): return (x >>> d) | (x 
Подсчет количества единичных битов

Для подсчета количества единичных битов в числе [math]x[/math] можно воспользоваться следующим алгоритмом:

// Для чисел других разрядностей необходимо использовать соответствующие константы. int16 setBitsNumber(x: int16): x = x - ((x >>> 1) & 0x5555) x = (x & 0x3333) + ((x >>> 2) & 0x3333) x = (x + (x >>> 4)) & 0x0F0F return (x * 0x0101) >>> 8

Поскольку [math]5555_[/math] равно [math]01010101 01010101_[/math] , результатом операции [math]x\ \&\ 5555_[/math] является число, в котором все нечетные биты соответствуют нечетным битам числа [math]x[/math] . Аналогично, результатом операции [math](x\ \texttt<\gt \gt \gt >\ 1)\ \&\ 5555_[/math] является число, в котором все нечетные биты соответствуют четным битам [math]x[/math] . Четные биты результата в обоих случаях равны нулю.

Мысленно разобьем двоичную запись нашего числа [math]x[/math] на группы по [math]2[/math] бита. Результатом операции [math]x\ \&\ 5555_ + (x\ \texttt<\gt \gt \gt >\ 1)\ \&\ 5555_[/math] будет такое число, что если разбить его двоичную запись на группы по два бита, значение каждой группы соответствует количеству единичных битов в соответствующей паре битов числа [math]x[/math] .

Аналогично, число [math]3333_[/math] равно [math]00110011 00110011_[/math] и операция [math]x = (x\ \&\ 3333_) + (x\ \texttt<\gt \gt \gt >\ 2\ \&\ 3333_)[/math] , примененная к результату, полученному на первом этапе, выполняет подсчет количества единичных битов в блоках по [math]4[/math] . В свою очередь, число [math]\texttt_[/math] равно [math]00001111 00001111_[/math] и операция [math]x = (x\ \&\ \texttt_) + (x\ \texttt<\gt \gt \gt >\ 4\ \&\ \texttt_)[/math] позволяет подсчитать число единичных бит в блоках по [math]8[/math] .

Теперь необходимо просуммировать числа, записанные в блоках по [math]8[/math] битов, чтобы получить искомую величину. Это можно сделать, домножив результат на [math]0101_[/math] [math](1 00000001_)[/math] . Ответ на задачу будет находиться в первых восьми битах произведения. Выполнив сдвиг вправо на [math]8[/math] (для шестнадцатибитных чисел), мы получим долгожданный ответ.

int16 setBitsNumber(x: int16): x = (x & 0x5555) + ((x >>> 1) & 0x5555) x = (x & 0x3333) + ((x >>> 2) & 0x3333) x = (x & 0x0F0F) + ((x >>> 4) & 0x0F0F) return (x * 0x0101) >>> 8

Заметим, что операция [math]x\ \&\ 55_ + (x\ \texttt<\gt \gt \gt >\ 1)\ \&\ 55_[/math] равносильна операции [math]x - (x\ \texttt<\gt \gt \gt >\ 1)\ \&\ 55_[/math] , в чем легко убедиться, рассмотрев все числа из двух бит.

В свою очередь, операцию [math](x\ \&\ \texttt_) + ((x\ \texttt<\gt \gt \gt >\ 4)\ \&\ \texttt_)[/math] можно заменить на [math](x + (x\ \texttt<\gt \gt \gt >\ 4))\ \&\ \texttt_[/math] . Эта замена не повлияет на результат, так как максимальное значение в любой группе из четырех битов данного числа равно четырем, то есть требует только трех битов для записи, и выполнение суммирования не повлечет за собой переполнения и выхода за пределы четверок.

Таким образом, мы получили код, приведенный в начале раздела.

Разворот битов

Чтобы получить биты числа [math]x[/math] , записанные в обратном порядке, применим следующий алгоритм.

// Для чисел других разрядностей нужны соответствующие константы. int16 reverseBits(x: int16): x = ((x & 0x5555) >> 1) & 0x5555) // Четные и нечетные биты поменялись местами. x = ((x & 0x3333) >> 2) & 0x3333) // Биты "перетасовываются" группами по два. x = ((x & 0x0F0F) >> 4) & 0x0F0F) // Биты "перетасовываются" группами по четыре. x = ((x & 0x00FF) >> 8) & 0x00FF) // Биты "перетасовываются" группами по восемь. return x

Более подробно про то, что за константы выбраны для данного алгоритма, можно прочитать в разделе подсчет количества единичных битов.

Применение для решения задач

Работа с битовыми масками

Для работы с подмножествами удобно использовать битовые маски. Применяя побитовые операции легко сделать следующее: найти дополнение [math](\sim mask)[/math] , пересечение [math](mask_1\ \&\ mask_2)[/math] , объединение [math](mask_1 \mid mask_2)[/math] множеств, установить бит по номеру [math](mask \mid (1\ \texttt<\lt \lt >\ x))[/math] , снять бит по номеру [math](mask\ \&\ \sim(1\ \texttt<\lt \lt >\ x))[/math] .

Битовые маски используются, например, при решении некоторых задач [1] динамического программирования.

Алгоритм Флойда

Основная статья: Алгоритм Флойда

Алгоритм Флойда–Уоршелла (англ. the Floyd–Warshall algorithm) — алгоритм для нахождения длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе. Работает корректно, если в графе нет циклов отрицательной величины, а если же такой цикл есть, позволяет найти хотя бы один такой цикл. Асимптотическая сложность алгоритма [math] \Theta(n^3) [/math] , также требует [math] \Theta(n^2) [/math] памяти.

Дерево Фенвика

Основная статья: Дерево Фенвика

Дерево Фенвика (англ. Binary indexed tree) — структура данных, которая может выполнять следующие операции:

  • изменять значение любого элемента в массиве,
  • выполнять некоторую ассоциативную, коммутативную, обратимую операцию [math] \circ [/math] на отрезке [math] [i, j] [/math] .

Данная структура требует [math] O(n) [/math] памяти, а выполнение каждой операции происходит за [math] O(\log n) [/math] .

Функция, позволяющая делать операции вставки и изменения элемента за [math] O(\log n) [/math] , задается следующей формулой [math] F(i) = (i \And (i + 1)) [/math] . Пусть дан массив [math] A = [a_0, a_1, \ldots, a_][/math] . Деревом Фенвика называется массив [math] T [/math] из [math] n [/math] элементов: [math] T_i = \sum\limits_^ a_k[/math] , где [math] i = 0\ldots n - 1 [/math] и [math] F(i) [/math] — функция, которую мы определили ранее.

См. также

  • Определение булевой функции
  • Сумматор
  • Триггеры

Примечания

Источники информации

  • Онлайн справочник программиста на С и С++
  • Побитовые операторы
  • Bit Twiddling Hacks by Sean Eron Anderson
  • Habrahabr — Алгоритмы поиска старшего бита
  • STP's blog — Counting the number of set bits in an integer

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *