практическое применение поразрядных операций [закрыто]

1. Для чего вы использовали побитовые операции?
2. почему они такие удобные?
3. может кто-нибудь порекомендовать ОЧЕНЬ простой учебник?

Хотя кажется, что все зацепились за использование флагов, это не единственное применение побитовых операторов (хотя, вероятно, наиболее распространенное). Кроме того, C # является языком достаточно высокого уровня, поэтому другие методы, вероятно, будут использоваться редко, но их все же стоит знать. Вот что я могу думать:

Операторы <<и >>могут быстро умножаться на степень 2. Конечно, оптимизатор .NET JIT, вероятно, сделает это за вас (и любой достойный компилятор другого языка также), но если вы действительно беспокоитесь каждую микросекунду, вы просто мог бы написать это для уверенности.

Еще одно распространенное использование этих операторов - вставка двух 16-разрядных целых чисел в одно 32-разрядное целое число. Подобно:

int Result = (shortIntA << 16 ) | shortIntB;

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

И, конечно же, эти операторы полезны, когда вы хотите запутать неопытных, например, при ответе на вопрос домашнего задания. :)

Однако в любом реальном коде вам будет гораздо лучше, если вместо этого использовать умножение, потому что он имеет гораздо лучшую читаемость, а JIT оптимизирует его shlи shrинструкции в любом случае, поэтому нет потери производительности.

С ^оператором (XOR) связано немало любопытных уловок . На самом деле это очень мощный оператор из-за следующих свойств:

• A^B == B^A
• A^B^A == B
• Если вы знаете, A^Bто невозможно сказать, что Aи Bесть, но если вы знаете одно из них, вы можете вычислить другое.
• Оператор не страдает переполнениями типа умножения / деления / сложения / вычитания.

Я видел несколько приемов с использованием этого оператора:

Замена двух целочисленных переменных без промежуточной переменной:

A = A^B // A is now XOR of A and B
B = A^B // B is now the original A
A = A^B // A is now the original B

Двусвязный список с одной дополнительной переменной для каждого элемента. Это мало пригодится в C #, но может пригодиться для низкоуровневого программирования встроенных систем, где важен каждый байт.

Идея в том, что вы отслеживаете указатель на первый элемент; указатель на последний элемент; и для каждого отслеживаемого вами объекта pointer_to_previous ^ pointer_to_next. Таким образом, вы можете перемещаться по списку с любого конца, но накладные расходы вдвое меньше, чем у традиционного связного списка. Вот код C ++ для обхода:

ItemStruct *CurrentItem = FirstItem, *PreviousItem=NULL;
while (  CurrentItem != NULL )
{
    // Work with CurrentItem->Data

    ItemStruct *NextItem = CurrentItem->XorPointers ^ PreviousItem;
    PreviousItem = CurrentItem;
    CurrentItem = NextItem;
}

Чтобы пройти с конца, вам просто нужно изменить самую первую строку с FirstItemна LastItem. Это еще одна экономия памяти прямо здесь.

Еще одно место, где я ^регулярно использую оператор в C #, - это когда мне нужно вычислить HashCode для моего типа, который является составным типом. Подобно:

class Person
{
    string FirstName;
    string LastName;
    int Age;

    public int override GetHashCode()
    {
        return (FirstName == null ? 0 : FirstName.GetHashCode()) ^
            (LastName == null ? 0 : LastName.GetHashCode()) ^
            Age.GetHashCode();
    }
}

Я использую побитовые операторы для безопасности в своих приложениях. Я буду хранить разные уровни внутри Enum:

[Flags]
public enum SecurityLevel
{
    User = 1, // 0001
    SuperUser = 2, // 0010
    QuestionAdmin = 4, // 0100
    AnswerAdmin = 8 // 1000
}

А затем назначьте пользователю их уровни:

// Set User Permissions to 1010
//
//   0010
// | 1000
//   ----
//   1010
User.Permissions = SecurityLevel.SuperUser | SecurityLevel.AnswerAdmin;

А затем проверьте разрешения в выполняемом действии:

// Check if the user has the required permission group
//
//   1010
// & 1000
//   ----
//   1000
if( (User.Permissions & SecurityLevel.AnswerAdmin) == SecurityLevel.AnswerAdmin )
{
    // Allowed
}

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

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

Сама плата, скорее всего, будет представлена ​​двумерным массивом вроде:

uint [, ] theBoard = new uint[9, 9];

Значение 0означает, что ячейка все еще пуста, а значения из диапазона [1u, 9u] являются фактическими значениями на плате.

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

Вы можете поддерживать массивы битовых масок, в которых хранится информация о числах, которые уже вставлены в каждую строку, каждый столбец a и каждое поле 3x3.

uint [] maskForNumbersSetInRow = new uint[9];

uint [] maskForNumbersSetInCol = new uint[9];

uint [, ] maskForNumbersSetInBox = new uint[3, 3];

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

1 -> 00000000 00000000 00000000 00000001
2 -> 00000000 00000000 00000000 00000010
3 -> 00000000 00000000 00000000 00000100
...
9 -> 00000000 00000000 00000001 00000000

В C # вы можете вычислить битовый шаблон следующим образом ( valueэто uint):

uint bitpattern = 1u << (int)(value - 1u);

В строке выше 1uсоответствующий битовый шаблон 00000000 00000000 00000000 00000001сдвинут влево на value - 1. Если, например value == 5, вы получите

00000000 00000000 00000000 00010000

Вначале маска для каждой строки, столбца и поля 0. Каждый раз, когда вы помещаете какое-либо число на плату, вы обновляете маску, поэтому устанавливается бит, соответствующий новому значению.

Предположим, вы вставили значение 5 в строку 3 (строки и столбцы нумеруются от 0). Маска для строки 3 сохраняется в maskForNumbersSetInRow[3]. Предположим также, что до вставки {1, 2, 4, 7, 9}в строке 3 уже были числа . Битовая последовательность в маске maskForNumbersSetInRow[3]выглядит так:

00000000 00000000 00000001 01001011
bits above correspond to:9  7  4 21

Цель состоит в том, чтобы установить бит, соответствующий значению 5 в этой маске. Вы можете сделать это с помощью побитового или оператора ( |). Сначала вы создаете битовый шаблон, соответствующий значению 5

uint bitpattern = 1u << 4; // 1u << (int)(value - 1u)

а затем вы используете, operator |чтобы установить бит в маскеmaskForNumbersSetInRow[3]

maskForNumbersSetInRow[3] = maskForNumbersSetInRow[3] | bitpattern;

или используя более короткую форму

maskForNumbersSetInRow[3] |= bitpattern;

00000000 00000000 00000001 01001011
                 |
00000000 00000000 00000000 00010000
                 =
00000000 00000000 00000001 01011011

Теперь ваша маска показывает, что {1, 2, 4, 5, 7, 9}в этой строке (строка 3) есть значения.

Если вы хотите проверить, находится ли какое-либо значение в строке, вы можете использовать, operator &чтобы проверить, установлен ли соответствующий бит в маске. Если результат этого оператора, примененного к маске и битовому шаблону, соответствующему этому значению, отличен от нуля, значение уже находится в строке. Если результат равен 0, значение отсутствует в строке.

Например, если вы хотите проверить, находится ли значение 3 в строке, вы можете сделать это следующим образом:

uint bitpattern = 1u << 2; // 1u << (int)(value - 1u)
bool value3IsInRow = ((maskForNumbersSetInRow[3] & bitpattern) != 0);

00000000 00000000 00000001 01001011 // the mask
                 |
00000000 00000000 00000000 00000100 // bitpattern for the value 3
                 =
00000000 00000000 00000000 00000000 // the result is 0. value 3 is not in the row.

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

public void insertNewValue(int row, int col, uint value)
{

    if(!isMoveLegal(row, col, value))
        throw ...

    theBoard[row, col] = value;

    uint bitpattern = 1u << (int)(value - 1u);

    maskForNumbersSetInRow[row] |= bitpattern;

    maskForNumbersSetInCol[col] |= bitpattern;

    int boxRowNumber = row / 3;
    int boxColNumber = col / 3;

    maskForNumbersSetInBox[boxRowNumber, boxColNumber] |= bitpattern;

}

Имея маски, вы можете проверить, законен ли ход, вот так:

public bool isMoveLegal(int row, int col, uint value)
{

    uint bitpattern = 1u << (int)(value - 1u);

    int boxRowNumber = row / 3;
    int boxColNumber = col / 3;

    uint combinedMask = maskForNumbersSetInRow[row] | maskForNumbersSetInCol[col]
                        | maskForNumbersSetInBox[boxRowNumber, boxColNumber];

    return ((theBoard[row, col] == 0) && ((combinedMask & bitpattern) == 0u);
}

Десятки примеров битового тидла здесь

Код написан на C, но вы можете легко адаптировать его к C #.

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

Извлечение значений RGB значения пикселя.

Так много вещей

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

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

Побитовое И, побитовое ИЛИ, вопрос в Java

Для других примеров посмотрите (скажем) отмеченные перечисления.

В моем примере я использовал поразрядные операции, чтобы изменить диапазон двоичного числа с -128 ... 127 на 0..255 (изменив его представление с подписанного на беззнаковое).

статья MSN здесь ->

http://msdn.microsoft.com/en-us/library/6a71f45d%28VS.71%29.aspx

Полезно.

И хотя эта ссылка:

http://weblogs.asp.net/alessandro/archive/2007/10/02/bitwise-operators-in-c-or-xor-and-amp-amp-not.aspx

очень технический, он охватывает все.

HTH

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

Некоторые примеры включают биты безопасности (ожидание образца Джастина ..), дни планирования и т. Д.

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

Пример сжатия сети с использованием битовых полей

Одна из самых частых вещей, которые я использую в C #, - это создание хэш-кодов. Есть несколько достаточно хороших методов хеширования, которые их используют. Например, для координационного класса с X и Y, которые были обеими int, я мог бы использовать:

public override int GetHashCode()
{
  return x ^ ((y << 16) | y >> 16);
}

Это быстро генерирует число, которое гарантированно будет равным при создании равным объектом (при условии, что равенство означает, что параметры X и Y одинаковы в обоих сравниваемых объектах), а также не создает конфликтующих шаблонов для объектов с низким значением (вероятно, будет наиболее часто встречается в большинстве приложений).

Другой - комбинирование перечислений флагов. НапримерRegexOptions.Compiled | RegexOptions.CultureInvariant | RegexOptions.IgnoreCase

Есть некоторые низкоуровневые операции, которые обычно не нужны, когда вы пишете код в среде, такой как .NET (например, в C # мне не нужно писать код для преобразования UTF-8 в UTF-16, он есть для меня в фреймворк), но, конечно, этот код нужно было написать.

Есть несколько приемов перестановки битов, например округление до ближайшего двоичного числа (например, округление от 1010 до 10000):

        unchecked
        {
            --x;
            x |= (x >> 1);
            x |= (x >> 2);
            x |= (x >> 4);
            x |= (x >> 8);
            x |= (x >> 16);
            return ++x;
        }

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

Наконец, вы также можете использовать их для микрооптимизации математики, например, << 1вместо, * 2но я включаю это только для того, чтобы сказать, что это вообще плохая идея, поскольку она скрывает намерение реального кода, почти ничего не сохраняет в производительности и может скрыть некоторые тонкие ошибки. .

Бинарная сортировка. Были проблемы, когда реализация использовала оператор деления вместо оператора битового сдвига. Это привело к отказу BS после того, как коллекция достигла размеров более 10 000 000

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

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

Я уверен, что вы можете думать о других.

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

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

А еще лучше пусть кто-нибудь прочтет его и подробно документирует.

Игры!

В свое время я использовал его для изображения фигур игрока Реверси. Это 8X8, так что мне потребовался longтип, а затем, например, если вы хотите знать, где все фигуры на доске - вы orоба игрока фигуры.
Если вам нужны все возможные шаги игрока, скажем вправо - вы >>представляете фигуры игрока по одной, а ANDэто с фигурами противника, чтобы проверить, есть ли теперь общие единицы (это означает, что справа от вас есть фигура противника). Потом продолжай это делать. если вы вернетесь к своим фигурам - нет хода. Если вы дойдете до четкого участка - вы можете двигаться туда и захватывать все фигуры на пути.
(Этот прием широко используется во многих видах настольных игр, включая шахматы)