비트 연산의 실제 적용

비트 연산의 실제 적용

---

1. 비트 연산을 무엇에 사용 했습니까?
2. 왜 그렇게 편리할까요?
3. 누군가 아주 간단한 튜토리얼을 추천 해 주시겠습니까?

---

모든 사람이 플래그 사용 사례에 매료 된 것처럼 보이지만 비트 연산자의 유일한 응용 프로그램은 아닙니다 (가장 일반적 일지라도). 또한 C #은 다른 기술이 거의 사용되지 않을만큼 충분히 높은 수준의 언어이지만 여전히 알아 두어야 할 가치가 있습니다. 내가 생각할 수있는 것은 다음과 같습니다.

---

<<그리고 >>당신이 정말로 모든 마이크로를 통해 초조해하는 경우 사업자는 빠르게 증식 물론 2의 힘으로, 닷넷 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
}

---

나는 당신이 생각하는 스도쿠를 해결하는 것이 얼마나 실용적인지 모르겠지만 그것이 있다고 가정합시다.

보드를 보여주고 퍼즐을 직접 풀 수 있지만 동작이 합법적인지 확인하는 스도쿠 해결사 또는 단순한 프로그램을 작성하고 싶다고 상상해보십시오.

보드 자체는 아마도 다음과 같은 2 차원 배열로 표현 될 것입니다.

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 비트를 사용하여 숫자에서 비트 패턴으로의 매핑은 매우 간단합니다.

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

C #에서는 다음과 같이 비트 패턴을 계산할 수 있습니다 ( valueis an uint).

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

위의 줄 1u에서 비트 패턴에 해당하는 것은 00000000 00000000 00000000 00000001왼쪽으로 이동합니다 value - 1. 예를 들어 value == 5다음과 같은 경우

00000000 00000000 00000000 00010000

처음에 각 행, 열 및 상자의 마스크는 0입니다. 보드에 숫자를 입력 할 때마다 마스크를 업데이트하므로 새 값에 해당하는 비트가 설정됩니다.

행 3에 값 5를 삽입한다고 가정합니다 (행과 열은 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이 아니면 값이 이미 행에있는 것입니다. 결과가 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 값 추출.

너무 많은 것들

---

They can be used for a whole load of different applications, here is a questions I have previously posted here, which uses bitwise operations:

Bitwise AND, Bitwise Inclusive OR question, in Java

For other examples, have a look at (say) flagged enumerations.

In my example, I was using bitwise operations to change the range of a binary number from -128...127 to 0..255 (changing it's representation from signed to unsigned).

the MSN article here ->

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

is useful.

And, although this link:

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

is very technical, it is covering everything.

HTH

---

Anytime you have an option of 1 or more in combination of items then bitwise is usually an easy fix.

Some examples include security bits (waiting on Justin's sample..), scheduling days, etc.

---

I would have to say one of the most common uses is modifying bitfields to compress data. You mostly see this in programs attempting to be economical with packets.

Example of network compression using bitfields

---

One of the most frequent things I use them for in C# is producing hashcodes. There's some reasonably good hashing methods that use them. E.g. for a co-ordinate class with an X an Y that were both ints I might use:

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

This quickly generates a number that is guaranteed to be equal when produced by an equal object (assuming that equality means both X and Y parameters are the same in both objects compared) while also not producing clashing patterns for low-valued objects (likely to be most common in most applications).

Another is combining flag enumerations. E.g. RegexOptions.Compiled | RegexOptions.CultureInvariant | RegexOptions.IgnoreCase

There are some low-level operations that are more commonly not necessary when you are coding against a framework like .NET (e.g. in C# I won't need to write code to convert UTF-8 to UTF-16, it's there for me in the framework), but of course somebody had to write that code.

There are a few bit-twiddling techniques, like rounding up to the nearest binary number (e.g. round up 1010 to 10000):

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

Which are useful when you need them, but that tends not to be very common.

Finally, you can also use them to micro-optimise mathematics such as << 1 instead of * 2 but I include that only to say it's generally a bad idea as it hides the intent of the real code, saves almost nothing in performance, and can hide some subtle bugs.

---

1. They can be used for passing in many arguments to a function through one limited size variable.
2. Advantages are low memory overhead, or low memory cost: Therefore increased performance.
3. I can't write a tutorial on the spot, but they are out there I'm sure.

---

Binary sort. There were issues where the implementation was using a division operator instead of a bitshift operator. This caused BS to fail after the collection got to sizes above 10,000,000

---

You'll use them for various reasons:

• storing (and checking!) option flags in a memory efficient way
• if doing computational programming, you may want to consider optimizing some of your operations by using bitwise operations instead of mathematical operators (beware of side-effects)
• Gray Code!
• creating enumerated values

I'm sure you can think of others.

That being said, sometimes you need to ask yourself: is the memory and performance boost worth the effort. After writing that sort of code, let it rest for a while and come back to it. If you struggle with it, rewrite with a more maintainable code.

On the other hand, sometimes it does make perfect sense to use bitwise operations (think cryptography).

Better yet, have it read by someone else, and document extensively.

---

Games!

Back in the days, I used it to represent a Reversi player's pieces. It's 8X8 so it took me a long type, and than, for example if you want to know where are all piece on board - you or both players pieces.
If you want all possible steps of a player, say to the right - you >> the player's pieces representation by one , and AND it with the opponent's pieces to check if there are now common 1's (that means there is an opponent piece to your right). Then you keep doing that. if you get back to your own pieces - no move. If you get to a clear bit - you can move there, and capture all the pieces on the way.
(This technique is broadly used, in many kinds of board games, including chess)

참고URL : https://stackoverflow.com/questions/3883384/practical-applications-of-bitwise-operations