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


  1. для чего вы использовали побитовые операции?

  2. почему они так удобно?

  3. может кто-нибудь порекомендовать очень простой учебник?

861   13  

13 ответов:

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

The << и >> операторы могут быстро умножать на 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. Таким образом, вы можете перемещаться по списку с любого конца, но накладные расходы составляют всего половину от A традиционный связанный список. Вот код 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# - это когда мне нужно вычислить хэш-код для моего типа, который является составным типом. Например:

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();
    }
}
68  
2018-02-15 22:08:44

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

[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
}
59  
2015-04-24 16:56:17

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

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

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

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];

отображение из числа в bitpattern, с одним битом, соответствующим этому набору чисел, очень просто

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

в C#, вы можете вычислить bitpattern таким образом (value это uint):

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

в строку 1u соответствует bitpattern 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 в этой маске. Вы можете сделать это с помощью побитового оператора or (|). Сначала вы создаете битовый шаблон, соответствующий значению 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);
}
15  
2010-10-08 10:59:42

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

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

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

3  
2010-10-07 19:33:54

десятки примеров скручивания бит здесь

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

3  
2010-10-08 02:26:55

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

побитовое и, побитовое включение или вопрос, в 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

2  
2017-05-23 15:18:15

в любое время у вас есть возможность 1 или более в комбинации элементов, то побитовое, как правило, легко исправить.

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

2  
2010-10-07 18:48:42

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

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

2  
2010-10-07 18:53:33

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

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 но я включаю это только для того, чтобы сказать, что это вообще плохая идея, поскольку она скрывает намерение реального кода, почти ничего не сохраняет в производительности и может скрыть некоторые тонкие ошибки.

2  
2010-10-07 18:56:36
  1. они могут использоваться для передачи многих аргументов функции через одну переменную ограниченного размера.
  2. преимущества низкие накладные расходы памяти, или низкая стоимость памяти: поэтому повышенная производительность.
  3. Я не могу написать учебник на месте, но они там, я уверен.
1  
2010-10-07 18:48:19

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

1  
2010-10-07 18:57:21

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

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

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

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

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

еще лучше, пусть это прочитает кто-то другой, и документ широко.

1  
2010-10-07 20:52:26

игры!

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

1  
2010-10-07 21:09:16

Comments

    Ничего не найдено.
Click here to cancel reply.