Для чего нужны битовые операторы? [закрыто]

19

Языки программирования часто поставляются с различными битовыми операторами (например, битовое смещение влево и вправо, битовое AND, OR, XOR ...). Они не привыкают, хотя очень, или, по крайней мере, таков мой опыт. Они иногда используются в задачах программирования или на собеседованиях, или решение может потребовать их, например:

  • Не используя оператор равенства, создайте функцию, которая возвращает, trueкогда два значения равны
  • Не используя третью переменную, меняйте значение двух переменных

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

Почему такие встречаются в большинстве языков программирования? Какие-нибудь реальные случаи использования?

Анто
источник
@ Anto - простой пример - отправка клиенту данных объемом 256 КБ со скоростью 256 слов за раз (4096 байт).
Ramhound
1
«Не используя оператор равенства, создайте функцию, которая возвращает истину, когда два значения равны» - в C return !(x-y);:? Я не знаю
Эндрю Арнольд
@Andrew: Это решение, но вы можете сделать это и с помощью побитовых операторов.
Anto
19
«К этому не привыкла, хотя и очень сильно» - уверены в этом? Я использую их все время. Мы не все работаем в вашей проблемной области.
Эд С.
2
Недостаточно для полного ответа, но попробуйте прочитать первые 4 бита байта, не думая о них, а затем подумайте, что некоторые форматы данных очень плотно упакованы.
Брендан Лонг

Ответы:

53

Нет, они имеют много реальных приложений и являются основными операциями на компьютерах.

Они используются для

  • Жонглирование блоков байтов вокруг, которые не вписываются в типы данных языков программирования
  • Переключение кодировки назад и вперед от большого к младшему.
  • Упаковка 4 6-битных частей данных в 3 байта для некоторого последовательного или USB-соединения
  • Многие форматы изображений имеют различное количество битов, назначенных для каждого цветового канала.
  • Все, что связано с IO-выводами во встроенных приложениях
  • Сжатие данных, которое часто не имеет данных, соответствует хорошим 8-битным границам. \
  • Алгоритмы хеширования, CRC или другие проверки целостности данных.
  • шифрование
  • Генерация псевдослучайных чисел
  • Raid 5 использует побитовый XOR между томами для вычисления четности.
  • Тонны больше

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

как зовут
источник
1
+1 за ваш довольно полный список, который вы, кажется, даже добавляете
Anto
28
+1. @ Анто: Этот список далеко не полный. Полный список вариантов использования для побитовых операторов в системном программировании будет таким же, как и полный список SQL-запросов в бизнес-приложениях. Интересный факт: я все время использую побитовые операции, но не писал SQL-выражения годами ;-)
nikie
4
@nikie: И я пишу SQL все время, но годами не использовал побитовые операторы! :)
FrustratedWithFormsDesigner
3
Я работаю во встраиваемых системах - побитовые операторы - это пустяки. Используется каждый день без каких-либо мыслей.
quick_now
9
Если я иногда использую сдвиг в битах в SQL, получу ли я приз?
Муравей
13

Потому что они фундаментальные операции.

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

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

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

Например:

// Given a 30-bit RGB color value as a 32-bit int
// A lot of image sensors spit out 10- or 12-bit data
// and some LVDS panels have a 10- or 12-bit format
b = (color & 0x000003ff);
g = (color & 0x000ffc00) >> 10;
r = (color & 0x3ff00000) >> 20;

// Going the other way:
color = ((r << 20) & 0x3ff00000) | ((g << 10) & 0x000ffc00) | (b & 0x000003ff);

Для декодирования инструкций ЦП для ЦП типа RISC (например, при эмуляции другой платформы) требуется извлечь части большого значения, как указано выше. Иногда выполнение этих операций с умножением и делением, а также по модулю и т. Д. Может быть в десять раз медленнее, чем эквивалентные побитовые операции.

greyfade
источник
12

Типичным примером является извлечение отдельных цветов из 24-битного значения RGB и обратно.


РЕДАКТИРОВАТЬ: из http://www.docjar.com/html/api/java/awt/Color.java.html

    value =  ((int)(frgbvalue[2]*255 + 0.5))    |
                (((int)(frgbvalue[1]*255 + 0.5)) << 8 )  |
                (((int)(frgbvalue[0]*255 + 0.5)) << 16 ) |
                (((int)(falpha*255 + 0.5)) << 24 );

источник
Показать этот пример на практике? Фрагмент кода?
Anto
Лучшим примером может быть обработка 16-битных (4,5 бит / с) или 30-битных (10 бит / с) значений RGB.
Greyfade
@grey, не стесняйтесь добавлять такие примеры.
6

Вот реальный пример, который вы найдете в Quake 3, Quake 4. Doom III. Все те игры, которые использовали движок Q3 .

float Q_rsqrt( float number )
{
        long i;
        float x2, y;
        const float threehalfs = 1.5F;

        x2 = number * 0.5F;
        y  = number;
        i  = * ( long * ) &y;                       // evil floating point bit level hacking [sic]
        i  = 0x5f3759df - ( i >> 1 );               // what the fuck? [sic]
        y  = * ( float * ) &i;
        y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//    y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

        return y;
}

(Чтобы понять этот код, вам нужно понять, как хранятся числа с плавающей запятой, я определенно не могу это подробно описать)

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

Крис С
источник
+1 За эти комментарии, даже если они не ваши. Заставил меня посмеяться
Басинатор
4

Сдвиг быстрее, чем умножение или деление на степень двух. Например, a << = 2 умножает a на 4. И наоборот, a >> = 2 делит a на четыре. Можно также передавать битовые данные на устройство, используя побитовые операторы. Например, мы можем отправлять N последовательных потоков данных из N-контактного порта, используя операции shift, xor и «and» внутри N циклов. Все, что может быть достигнуто в цифровой логике, также может быть реализовано в программном обеспечении и наоборот.

бит-бездельник
источник
1
Просто будьте осторожны при делении с округлением вверх или вниз и т. Д. Сдвиг не учитывает этого, поэтому я обнаружил, что на самом деле лучше использовать разделение в коде, когда я имею в виду разделение и позволить компилятору оптимизировать его в сдвиг и добавить для меня.
Daemin
@Daemin: я использую целые числа, когда использую эту технику. Поведение по умолчанию для целочисленного деления в C и C ++ - усечение до нуля; следовательно, смещение целого числа вправо на степень два приводит к тому же результату, что и деление целого числа на степень два.
bit-twiddler
1
@ bit-twiddler Сдвиг вправо не работает так же, как деление для отрицательных чисел.
Daemin
@Daemin: Вы, кажется, одержимы доказательством того, что я неправ. Сначала вы выбрасываете проблему округления. Когда я отвергаю это утверждение, заявляя, что деление в C и C ++ усекается до нуля, вы выбрасываете целочисленную проблему со знаком. Где я сказал, что применяю оператор сдвига к отрицательным целым числам со знаком дополнения до двух? При этом можно использовать оператор сдвига для деления на степень два. Однако, поскольку C и C ++ выполняют арифметическое смещение вправо вместо простого старого смещения вправо, необходимо сначала проверить, является ли значение отрицательным. Если значение отрицательное,
bit-twiddler
1
Соблюдайте осторожность при использовании сдвига в качестве замены для умножения и деления, поскольку есть небольшие различия. Ни больше ни меньше.
Daemin
3

Давным-давно, битовые операторы были полезны. Сегодня они менее так. О, они не совсем бесполезны, но я давно не видел ни одного использованного, который следовало бы использовать.

В 1977 году я был программистом на ассемблере. Я был убежден, что ассемблер был единственным верным языком. Я был уверен, что такой язык, как Паскаль, предназначен для академических фигур, которым никогда не приходилось делать что-то реальное .

Затем я прочитал «Язык программирования Си» Кернигана и Ричи. Это полностью изменило мое мнение. Причина? Это было немного операторов! Это был язык ассемблера! Просто у него был другой синтаксис.

В те дни я не мог представить себе код без ands, ors, shifts и rotate. В настоящее время я почти никогда не использую их.

Итак, короткий ответ на ваш вопрос: «Ничего». Но это не совсем справедливо. Так что более длинный ответ: «В основном ничего».

Дядя Боб.
источник
xkcd.com/378 приходит на ум.
Макс.
Битовые операторы полезны по сей день. Тот факт, что в вашем домене они не используются, не делает его неиспользованным или даже не очень часто используемым. Вот простой пример: попробуйте реализовать AES без битовых операторов. Это один из примеров того, что делается на большинстве компьютеров ежедневно сотни или тысячи раз в день.
ТОЛЬКО МОЕ правильное мнение
Кодирование / декодирование данных без использования побитовых операторов в лучшем случае является болезненным. Например, добавление MIME-вложений к сообщению требует, чтобы мы могли обрабатывать кодирование данных «три-четыре» (кодирование radix64).
bit-twiddler
2

шифрование

Я предлагаю взглянуть на очень маленький фрагмент алгоритма шифрования DES :

temp = ((left >>> 1) ^ right) & 0x55555555; right ^= temp; left ^= (temp << 1);
temp = ((right >>> 8) ^ left) & 0x00ff00ff; left ^= temp; right ^= (temp << 8);
temp = ((right >>> 2) ^ left) & 0x33333333; left ^= temp; right ^= (temp << 2);
temp = ((left >>> 16) ^ right) & 0x0000ffff; right ^= temp; left ^= (temp << 16);
temp = ((left >>> 4) ^ right) & 0x0f0f0f0f; right ^= temp; left ^= (temp << 4);
Скотт Уитлок
источник
Хотя не уверен, что DES рекомендуется в эти дни: P
Armand
@Alison: нет, но алгоритмы шифрования, которые заменили его, включают в себя еще больше операций с битами, я думаю. :-)
Carson63000
@Alison - конечно, но TripleDES - это просто DES, выполненный 3 раза с 3-кратными битами ключа.
Скотт Уитлок
2

Много хороших ответов, поэтому я не буду повторять это.

Я довольно часто использую их в управляемом коде (C # / .Net), и это не имеет ничего общего с алгоритмами экономии места, высокой производительности или умного сдвига битов. Иногда некоторая логика просто подходит для хранения данных таким способом. Я часто использую их, когда у меня есть перечисление, но экземпляры могут одновременно принимать несколько значений из этого перечисления. Я не могу опубликовать пример кода с работы, но быстрый поиск Google для «Flags enum» («Flags» - это способ определения enum для побитового использования в C #) дает хороший пример: http: // www.dotnetperls.com/enum-flags .

Стив
источник
2

Также есть битовые параллельные вычисления. Если ваши данные только 1 и 0, вы можете упаковать 64 из них в длинное слово без знака и получить 64-параллельные параллельные операции. Генетическая информация состоит из двух битов (представляющих кодирование ДНК AGCT), и если вы можете выполнять различные вычисления в параллельной форме, вы можете сделать гораздо больше, чем если бы вы этого не делали. Не говоря уже о плотности данных в памяти, если память, или емкость диска, или пропускная способность связи ограничены, подразумевается, что следует учитывать сжатие / декомпрессию. Даже целочисленные числа с низкой точностью, которые проявляются в таких областях, как обработка изображений, могут использовать преимущества сложных параллельных вычислений. Это целое искусство для себя.

Омега Центавра
источник
1

Почему они найдены?

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

Каковы их использования?

На самом деле есть только много вариантов использования имен, поэтому я просто приведу недавнее, хотя и сильно локализованное, использование. Я много работаю со сборкой 6502, и я работал над небольшим приложением, которое преобразует адреса памяти, значения, сравнивают значения и т. Д. В коды, которые можно использовать для устройства GameGenie (в основном, чит-приложение для NES). Коды создаются с помощью некоторых битовых манипуляций.


источник
1

Многие программисты в наши дни привыкли к компьютерам с почти бесконечной памятью.

Но некоторые из них по-прежнему программируют крошечные микроконтроллеры, в которых учитывается каждый бит (например, если у вас всего 1 Кбайт или меньше ОЗУ), а побитовые операторы позволяют программисту использовать эти биты по одному за раз вместо того, чтобы тратить много больше времени на программирование. объект абстракции, который может потребоваться для хранения состояния, требуемого алгоритмом. IO на этих устройствах также может потребовать чтения или управления на побитовой основе.

В «реальном мире» этих крошечных микроконтроллеров гораздо больше, чем серверов или ПК.

Для чисто теоретических типов CS машины Тьюринга - все о битах состояния.

hotpaw2
источник
1

Еще одно из многих возможных применений побитовых операторов ...

Побитовые операторы также могут помочь сделать ваш код более читабельным. Рассмотрим следующее объявление функции ....

int  myFunc (bool, bool, bool, bool, bool, bool, bool, bool);

...

myFunc (false, true, false, false, false, true, true, false);

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

/* More descriptive names than MY_FLAGx would be better */
#define MY_FLAG1    0x0001
#define MY_FLAG2    0x0002
#define MY_FLAG3    0x0004
#define MY_FLAG4    0x0008
#define MY_FLAG5    0x0010
#define MY_FLAG6    0x0020
#define MY_FLAG7    0x0040
#define MY_FLAG8    0x0080

int  myFunc (unsigned myFlags);

...

myFunc (MY_FLAG2 | MY_FLAG6 | MY_FLAG7);

С более наглядными именами флагов он становится намного более читабельным.

Спарки
источник
1

Если вы знаете что-нибудь о Unicode , вы, вероятно, знакомы с UTF-8. Он использует кучу битовых тестов, сдвигов и масок, чтобы упаковать 20-битную кодовую точку в 1 - 4 байта.

MSalters
источник
0

Я не часто их использую, но иногда они пригодятся. Обработка Enum приходит на ум.

Пример:

enum DrawBorder{None = 0, Left = 1, Top = 2, Right = 4, Bottom = 8}

DrawBorder drawBorder = DrawBorder.Left | DrawBorder.Right;//Draw right & left border
if(drawBorder & DrawBorder.Left == DrawBorder.Left)
  //Draw the left border
if(drawBorder & DrawBorder.Top == DrawBorder.Top)
  //Draw the top border
//...
Карра
источник
0

Не уверен, что это использование было отмечено еще:

Я вижу ИЛИ довольно много при работе с исходным кодом illumos (openSolaris), чтобы уменьшить множество возвращаемых значений до 0 или 1, например

int ret = 0;
ret |= some_function(arg, &arg2); // returns 0 or 1
ret |= some_other_function(arg, &arg2); // returns 0 or 1
return ret;
Awalias
источник