Интернет магазин китайских планшетных компьютеров

Компьютеры - Битовые операции - В теории сложности алгоритмов

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

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

Связь с другими науками

Битовые операции и математическая логика

Битовые операции очень близки логическим связкам в классической логике. Бит можно рассматривать как логическое суждение — его значениями являются 1 «истина» и 0 «ложь». При такой интерпретации известные в логике связки конъюнкции, дизъюнкции, импликации, отрицания и другие имеют представление на языке битов. И наоборот, битовые операции легко описываются на языке исчисления высказываний.

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

Обобщение операций на булеву алгебру

Вместо одиночных битов мы можем рассмотреть векторы из фиксированного количества битов, например, байты. В программировании регистры рассматривают как двоичное разложение целого числа: b = b₀ + 2b₁ + 2b₂ + ... + 2b_{N − 1}, где N — количество битов в регистре.

Тем не менее, ничто не мешает рассматривать эти регистры именно как битовые векторы и проводить булевые операции покомпонентно. Кстати, математически говоря, булевы операции распространяются таким образом на произвольную булеву алгебру. Таким образом мы получаем операции побитового И, ИЛИ, НЕ, искл. ИЛИ и т. д. Как арифметические, данные операции не обладают хорошими свойствами за исключением побитового НЕ, которое для чисел в дополнительном коде совпадает с вычитанием из −1. Однако, они очень полезны в программировании.

2-адическая интерпретация

Целое число, записанное в бесконечный двоичный регистр является естественным объектом для теории p-адических чисел при p = 2. Множество целых 2-адических чисел может быть рассмотрено как булева алгебра точно так же как и множество значений битового регистра конечной длины. Все вышеперечисленные битовые операции оказываются непрерывными отображениями. Хотя практическое программирование не располагает регистрами бесконечной длины, это не мешает использовать данный теоретический факт в криптографии для создания быстродействующих алгоритмов шифрования.

Битовые операции как основа цифровой техники

Битовые операции лежат в основе обработки цифровых сигналов. А именно, посредством них мы можем из одного или нескольких сигналов на входе получить новый сигнал, который в свою очередь может быть подан на вход одной или нескольким таким операциям. По сути, именно битовые операции в сочетании с запоминающими элементами реализуют всё богатство возможностей современной цифровой техники.