Реальные случаи использования побитовых операторов [закрыто]

Каковы реальные случаи использования следующих побитовых операторов?

• И
• XOR
• НЕ
• ИЛИ
• Сдвиг влево / вправо

• Битовые поля (флаги)
  Это наиболее эффективный способ представления чего-либо, состояние которого определяется несколькими свойствами «да или нет». ACL являются хорошим примером; если у вас есть, скажем, 4 дискретных разрешения (чтение, запись, выполнение, изменение политики), лучше хранить их в 1 байте, а не в пустой 4. Они могут быть сопоставлены с типами перечисления во многих языках для дополнительного удобства.

• Связь через порты / сокеты
  всегда включает в себя контрольные суммы, четность, стоп-биты, алгоритмы управления потоком и т. Д., Которые обычно зависят от логических значений отдельных байтов, а не от числовых значений, поскольку носитель может передавать только один бит в время.

• Сжатие, шифрование
  Оба они сильно зависят от побитовых алгоритмов. Посмотрите на алгоритм deflate для примера - все в битах, а не в байтах.

• Конечные автоматы
  Я говорю в первую очередь о типах, встроенных в некоторые аппаратные средства, хотя их можно найти и в программном обеспечении. Это комбинаторный характер - они могут буквально получать «скомпилированный» вниз на кучу логических вентилей, поэтому они должны быть выражены как AND, OR, NOTи т.д.

• Графика Здесь едва ли достаточно места, чтобы попасть в каждую область, где эти операторы используются в графическом программировании. XOR(или ^) здесь особенно интересно, потому что применение одного и того же ввода во второй раз приведет к отмене первого. Старые графические интерфейсы использовались для подсветки выбора и других наложений, чтобы исключить необходимость дорогостоящих перерисовок. Они все еще полезны в медленных графических протоколах (например, удаленный рабочий стол).

Это были только первые несколько примеров, которые я привел - это далеко не полный список.

Это странно?

(value & 0x1) > 0

Это делится на два (даже)?

(value & 0x1) == 0

Вот некоторые распространенные идиомы, касающиеся флагов, хранящихся в виде отдельных битов.

enum CDRIndicators {
  Local = 1 << 0,
  External = 1 << 1,
  CallerIDMissing = 1 << 2,
  Chargeable = 1 << 3
};

unsigned int flags = 0;

Установите флаг Chargeable:

flags |= Chargeable;

Снимите флажок CallerIDMissing:

flags &= ~CallerIDMissing;

Проверьте, установлены ли CallerIDMissing и Chargeable:

if((flags & (CallerIDMissing | Chargeable )) == (CallerIDMissing | Chargeable)) {

}

Я использовал побитовые операции при реализации модели безопасности для CMS. У него были страницы, к которым могли обращаться пользователи, если они были в соответствующих группах. Пользователь может быть в нескольких группах, поэтому нам нужно было проверить, нет ли пересечения между группами пользователей и группами страниц. Таким образом, мы присвоили каждой группе уникальный идентификатор степени 2, например:

Group A = 1 --> 00000001
Group B = 2 --> 00000010
Group C = 3 --> 00000100

Мы ИЛИ эти значения вместе, и храним значение (как один int) со страницей. Например, если к странице могут обращаться группы A и B, мы сохраняем значение 3 (двоичное значение 00000011) в качестве контроля доступа к страницам. Во многом таким же образом мы храним значение идентификаторов групп ORed вместе с пользователем, чтобы представлять, в каких группах они находятся.

Таким образом, чтобы проверить, может ли данный пользователь получить доступ к данной странице, вам просто нужно объединить значения AND и проверить, не является ли это значение ненулевым. Это очень быстро, поскольку эта проверка реализована в одной инструкции, без зацикливания, без обходов базы данных.

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

volatile uint32_t *register = (volatile uint32_t *)0x87000000;
uint32_t          value;
uint32_t          set_bit   = 0x00010000;
uint32_t          clear_bit = 0x00001000;

value = *register;            // get current value from the register
value = value & ~clear_bit;   // clear a bit
value = value | set_bit;      // set a bit
*register = value;            // write it back to the register

Кроме того , htonl()и htons()реализуются с использованием &и |операторов (на машинах , у которых порядок байт (Byte заказ) не соответствует сетевой заказ):

#define htons(a) ((((a) & 0xff00) >> 8) | \
                  (((a) & 0x00ff) << 8))

#define htonl(a) ((((a) & 0xff000000) >> 24) | \
                  (((a) & 0x00ff0000) >>  8) | \
                  (((a) & 0x0000ff00) <<  8) | \
                  (((a) & 0x000000ff) << 24))

Я использую их, например, для получения значений RGB (A) из упакованных значений цвета.

Когда у меня есть куча логических флагов, мне нравится хранить их все в int.

Я получаю их, используя побитовое И Например:

int flags;
if (flags & 0x10) {
  // Turn this feature on.
}

if (flags & 0x08) {
  // Turn a second feature on.
}

и т.п.

& = AND:
маскировать определенные биты.
Вы определяете конкретные биты, которые должны отображаться или не отображаться. 0x0 & x очистит все биты в байте, в то время как 0xFF не изменит x. 0x0F отобразит биты в нижнем клочке.

Преобразование:
чтобы преобразовать более короткие переменные в более длинные с идентификатором бита, необходимо отрегулировать биты, потому что -1 в int равно 0xFFFFFFFF, а -1 в длинном 0xFFFFFFFFFFFFFFFF. Для сохранения идентичности вы применяете маску после конвертации.

| = ИЛИ
Установить биты. Биты будут установлены независимо, если они уже установлены. Многие структуры данных (битовые поля) имеют флаги, такие как IS_HSET = 0, IS_VSET = 1, которые могут быть установлены независимо. Чтобы установить флаги, вы применяете IS_HSET | IS_VSET (в Си и сборке это очень удобно читать)

^ = XOR
Найти биты, которые являются одинаковыми или разными.

~ = НЕ
переворачивать биты.

Можно показать, что с помощью этих операций могут быть реализованы все возможные локальные битовые операции. Поэтому, если хотите, вы можете реализовать инструкцию ADD только с помощью битовых операций.

Несколько замечательных хаков:

http://www.ugcs.caltech.edu/~wnoise/base2.html
http://www.jjj.de/bitwizardry/bitwizardrypage.html

Шифрование - это все побитовые операции.

Вы можете использовать их как быстрый и грязный способ хэширования данных.

int a = 1230123;
int b = 1234555;
int c = 5865683;
int hash = a ^ b ^ c;

Я просто использовал bitwise-XOR ( ^) около трех минут назад, чтобы вычислить контрольную сумму для последовательной связи с ПЛК ...

Побитовый & используется для маскировки / извлечения определенной части байта.

1 байтовая переменная

 01110010
&00001111 Bitmask of 0x0F to find out the lower nibble
 --------
 00000010

Специально оператор сдвига (<< >>) часто используется для расчетов.

Это пример для чтения цветов из растрового изображения в байтовом формате.

byte imagePixel = 0xCCDDEE; /* Image in RRGGBB format R=Red, G=Green, B=Blue */

//To only have red
byte redColour = imagePixel & 0xFF0000; /*Bitmasking with AND operator */

//Now, we only want red colour
redColour = (redColour >> 24) & 0xFF;  /* This now returns a red colour between 0x00 and 0xFF.

Я надеюсь, что эти крошечные примеры помогут ....

В отвлеченном мире современного современного языка не так уж много. Файловый ввод-вывод является простым, который приходит на ум, хотя он выполняет побитовые операции над чем-то уже реализованным и не реализует то, что использует побитовые операции. Тем не менее, в качестве простого примера, этот код демонстрирует удаление атрибута только для чтения в файле (чтобы его можно было использовать с новым FileStream, указывающим FileMode.Create) в c #:

//Hidden files posses some extra attibutes that make the FileStream throw an exception
//even with FileMode.Create (if exists -> overwrite) so delete it and don't worry about it!
if(File.Exists(targetName))
{
    FileAttributes attributes = File.GetAttributes(targetName);

    if ((attributes & FileAttributes.ReadOnly) == FileAttributes.ReadOnly)
        File.SetAttributes(targetName, attributes & (~FileAttributes.ReadOnly));

    File.Delete(targetName);
}

Что касается пользовательских реализаций, вот недавний пример: я создал «центр сообщений» для отправки защищенных сообщений из одной установки нашего распределенного приложения в другую. По сути, это аналог электронной почты, в комплекте с папками «Входящие», «Исходящие», «Отправленные» и т. Д., Но также гарантированная доставка с квитанциями о прочтении, поэтому есть дополнительные подпапки, помимо «Входящие» и «Отправленные». То, что это означало, было требованием для меня, чтобы в общем определить, что находится «во входящих» или «в отправленной папке». Из отправленной папки мне нужно знать, что прочитано, а что непрочитано. Из того, что непрочитано, мне нужно знать, что получено, а что нет. Я использую эту информацию для построения динамического предложения where, которое фильтрует локальный источник данных и отображает соответствующую информацию.

Вот как составляется перечисление:

    public enum MemoView :int
    {
        InboundMemos = 1,                   //     0000 0001
        InboundMemosForMyOrders = 3,        //     0000 0011
        SentMemosAll = 16,                  //     0001 0000
        SentMemosNotReceived = 48,          //     0011
        SentMemosReceivedNotRead = 80,      //     0101
        SentMemosRead = 144,                //     1001
        Outbox = 272,                       //0001 0001 0000
        OutBoxErrors = 784                  //0011 0001 0000
    }

Вы видите, что это делает? Используя and & со значением перечисления Inbox InboundMemos, я знаю, что InboundMemosForMyOrders находится в папке входящих.

Вот развернутая версия метода, который создает и возвращает фильтр, который определяет представление для выбранной в данный момент папки:

    private string GetFilterForView(MemoView view, DefaultableBoolean readOnly)
    {
        string filter = string.Empty;
        if((view & MemoView.InboundMemos) == MemoView.InboundMemos)
        {
            filter = "<inbox filter conditions>";

            if((view & MemoView.InboundMemosForMyOrders) == MemoView.InboundMemosForMyOrders)
            {
                filter += "<my memo filter conditions>";
            }
        }
        else if((view & MemoView.SentMemosAll) == MemoView.SentMemosAll)
        {
            //all sent items have originating system = to local
            filter = "<memos leaving current system>";

            if((view & MemoView.Outbox) == MemoView.Outbox)
            {
                ...
            }
            else
            {
                //sent sub folders
                filter += "<all sent items>";

                if((view & MemoView.SentMemosNotReceived) == MemoView.SentMemosNotReceived)
                {
                    if((view & MemoView.SentMemosReceivedNotRead) == MemoView.SentMemosReceivedNotRead)
                    {
                        filter += "<not received and not read conditions>";
                    }
                    else
                        filter += "<received and not read conditions>";
                }
            }
        }

        return filter;
    }

Чрезвычайно простая, но аккуратная реализация на уровне абстракции, которая обычно не требует побитовых операций.

Кодировка Base64 является примером. Кодировка Base64 используется для представления двоичных данных в виде печатных символов для отправки по электронной почте (и для других целей). Кодирование Base64 преобразует серию 8-битных байтов в 6-битные индексы поиска символов. Битовые операции, сдвиг и «или», «нет» очень полезны для реализации битовых операций, необходимых для кодирования и декодирования Base64.

Это, конечно, только 1 из бесчисленных примеров.

Я удивлен, что никто не выбрал очевидный ответ для эпохи Интернета. Расчет действительных сетевых адресов для подсети.

http://www.topwebhosts.org/tools/netmask.php

Обычно побитовые операции выполняются быстрее, чем умножение / деление. Поэтому, если вам нужно умножить переменную x на 9, вы будете делать x<<3 + xэто на несколько циклов быстрее, чемx*9 . Если этот код находится внутри ISR, вы сэкономите на времени отклика.

Точно так же, если вы хотите использовать массив как циклическую очередь, было бы быстрее (и более элегантно) обрабатывать циклические проверки с помощью побитовых операций. (размер вашего массива должен быть степенью 2). Например: вы можете использовать tail = ((tail & MASK) + 1)вместоtail = ((tail +1) < size) ? tail+1 : 0 , если вы хотите вставить / удалить.

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

Также n-битное растровое изображение может быть действительно классной и компактной структурой данных. Если вы хотите выделить пул ресурсов размера n, мы можем использовать n-бит для представления текущего состояния.

Кажется, никто не упомянул математику с фиксированной точкой.

(Да, я старый, хорошо?)

Является ли число xстепенью 2? (Полезно, например, в алгоритмах, где счетчик увеличивается, а действие должно выполняться только логарифмически число раз)

(x & (x - 1)) == 0

Какой старший бит целого числа x? (Это, например, может использоваться, чтобы найти минимальную мощность 2, которая больше, чем x)

x |= (x >>  1);
x |= (x >>  2);
x |= (x >>  4);
x |= (x >>  8);
x |= (x >> 16);
return x - (x >>> 1); // ">>>" is unsigned right shift

Какой младший 1бит целого числа x? (Помогает найти количество раз, делимое на 2.)

x & -x

Битовые операторы полезны для циклических массивов, длина которых равна степени 2. Как уже упоминалось, побитовые операторы чрезвычайно полезны и используются в флагах , графике , работе в сети , шифровании . Не только это, но они очень быстро. Мой личный фаворит использование в цикле массив без условными . Предположим, у вас есть массив с нулевым индексом (например, индекс первого элемента равен 0), и вам нужно его бесконечно зацикливать. Под неопределенным временем я имею в виду переход от первого элемента к последнему и возвращение к первому. Один из способов реализовать это:

int[] arr = new int[8];
int i = 0;
while (true) {
    print(arr[i]);
    i = i + 1;
    if (i >= arr.length) 
        i = 0;
}

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

int[] arr = new int[8];
int i = 0;
while (true) {
    print(arr[i]);
    i = i + 1;
    i = i % arr.length;
}

Недостатком этих двух методов является то, что оператор модуля является дорогим, поскольку он ищет остаток после целочисленного деления. И первый метод выполняет оператор if на каждой итерации. Однако с помощью побитового оператора, если длина вашего массива является степенью 2, вы можете легко сгенерировать последовательность 0 .. length - 1, используя &оператор (побитовый и), как это i & length. Так зная это, код сверху становится

int[] arr = new int[8];
int i = 0;
while (true){
    print(arr[i]);
    i = i + 1;
    i = i & (arr.length - 1);
}

Вот как это работает. В двоичном формате каждое число, являющееся степенью 2, вычитаемое из 1, выражается только единицами. Например, 3 в двоичном виде 11, 7 - это 11115, 1111и т. Д., Вы поняли. Теперь, что произойдет, если вы &против любого числа, состоящего только из двоичных чисел? Допустим, мы делаем это:

num & 7;

Если numоно меньше или равно 7, результат будет numпотому, что каждый бит &с 1 равен самому себе. Если значение numбольше 7, во время &работы компьютер будет считать ведущие нули 7, которые, конечно, останутся нулями после &операции, останется только последняя часть. Как в случае с 9 & 7двоичным

1001 & 0111

результат будет 0001, который равен 1 в десятичном виде и обращается ко второму элементу в массиве.

Я использую их для нескольких вариантов выбора, таким образом я сохраняю только одно значение вместо 10 или более

это также может быть полезно в реляционной модели sql, скажем, у вас есть следующие таблицы: BlogEntry, BlogCategory

Традиционно вы можете создать отношения nn между ними, используя таблицу BlogEntryCategory или, если записей BlogCategory не так много, вы можете использовать одно значение в BlogEntry для ссылки на несколько записей BlogCategory, как это делается с помеченными перечислениями, в большинстве СУБД также есть. очень быстрые операторы для выбора в этом «помеченном» столбце ...

Когда вы хотите изменить только некоторые биты выходов микроконтроллера, но регистр для записи является байтом, вы делаете что-то вроде этого (псевдокод):

char newOut = OutRegister & 0b00011111 //clear 3 msb's
newOut = newOut | 0b10100000 //write '101' to the 3 msb's
OutRegister = newOut //Update Outputs

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

Если вы когда-нибудь захотите рассчитать ваше число мод (%) определенной степенью 2, вы можете использовать yourNumber & 2^N-1, которое в этом случае совпадает сyourNumber % 2^N .

number % 16 = number & 15;
number % 128 = number & 127;

Это, вероятно, полезно только в качестве альтернативы операции с модулем с очень большим дивидендом, равным 2 ^ N ... Но даже в этом случае прирост скорости по сравнению с операцией по модулю в моем тесте на .NET 2.0 незначителен. Я подозреваю, что современные компиляторы уже выполняют такие оптимизации. Кто-нибудь знает больше об этом?

Я видел их в ролевых системах контроля доступа.

В моем вопросе есть реальное применение -
Отвечать только на первое уведомление WM_KEYDOWN?

При использовании сообщения WM_KEYDOWN в Windows C api bit 30 указывает предыдущее состояние ключа. Значение равно 1, если ключ не работает до отправки сообщения, или ноль, если ключ работает

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

Кодировка символов:

if (s <= 0 && (c & ~MBFL_WCSPLANE_MASK) == MBFL_WCSPLANE_KOI8R) {

Структуры данных:

ar_flags = other->ar_flags & ~SPL_ARRAY_INT_MASK;

База данных драйверов:

dbh->transaction_flags &= ~(PDO_TRANS_ACCESS_MODE^PDO_TRANS_READONLY);

Реализация компилятора:

opline->extended_value = (opline->extended_value & ~ZEND_FETCH_CLASS_MASK) | ZEND_FETCH_CLASS_INTERFACE;

Всякий раз, когда я впервые начал программировать на С, я понимал таблицы истинности и все такое, но не все решали, как на самом деле использовать их, пока я не прочитал эту статью http://www.gamedev.net/reference/articles/article1563.asp (который дает примеры из реальной жизни)

Я не думаю, что это считается побитовым, но массив ruby ​​определяет операции над множествами через обычные целочисленные побитовые операторы. Так [1,2,4] & [1,2,3] # => [1,2]. Аналогично для a ^ b #=> set differenceи a | b #=> union.

Линейное решение Tower Of Hanoi использует побитовые операции для решения задачи.

public static void linear(char start, char temp, char end, int discs)
{
    int from,to;
    for (int i = 1; i < (1 << discs); i++) {
        from = (i & i-1) % 3;
        to = ((i | i-1) + 1) % 3;
        System.out.println(from+" => "+to);
    }
}

Объяснение этого решения можно найти здесь