[C++] 비트마스킹, 비트마스크, 비트연산자

2018. 3. 28에 쓰여진 글입니다.

---

정말 정말 정말 더럽게 중요한 개념인데 매번 간과하고 대충공부하다가 점점 중요성을 깨닫게 되고 조금씩 공부중..

진짜 C 첨배울때 비트연산자 이딴걸 왜배우나 했는데 다 쓸모가 있었음.

개념보다는 문제풀이용 위주로 짧고 간단하게 정리해봄. (내 복습용이라서..)

1. SHIFT연산자 ( << , >>) : 모든 비트를 해당 방향으로 밀어줌

- 비트를 시프트 해줌으로써 곱셈과 나눗셈의 효과를 얻을수 있음

 

#include <iostream>
 
using namespace std;
 
int main()
{
    int number = 1;            //0000 0001
    cout << "원래숫자 " << endl << number << endl;
    
    number = number << 1;    //0000 0010
    cout << "왼쪽으로 1칸 시프트" << endl << number << endl;
 
    number = number << 4;    //0010 0000
    cout << "왼쪽으로 4칸 더 시프트" << endl << number << endl;
 
    number = number >> 1;    //0001 0000
    cout << "오른쪽으로 1칸 시프트" << endl << number << endl;
 
    return 0;
}

 

보시는거와 같이 

왼쪽으로 1칸 시프트하게되면 2를 곱해준 효과가 됨.

2칸 시프트하면 4

3칸 시프트하면 8

4칸 시프트하면 16

5칸 시프트하면 32 ... 

 

이런식으로 2의 제곱꼴을 곱해준 형태가 되고

반대로 오른쪽으로 시프트하게되면 내가 밀어준 거만큼 2의 n제곱을 나눠주는 효과가 됨

- 부분집합을 구할때도 사용함

1<<N 은 2^N인데 이게 부분집합의 갯수를 구하는 공식임(공집합포함)

구하는 자세한 방법은 이전 포스팅 참조

https://royhelen.tistory.com/29

[C++] 모든 부분집합을 출력하기

 

2. AND 연산자 ( & ) , OR 연산자 ( | ) , XOR 연산자 ( ^ ) , NOT 연산자 ( ~ )

#include <iostream>
 
using namespace std;
 
int main()
{
    int number1 = 1;                    //0000 0001
    int number2 = 3;                    //0000 0011
 
    //AND ( & ) 연산을 하면 둘다 1인것만 1이됨
    int AND_Answer = number1&number2;    //0000 0001
    cout << "AND연산" << endl << AND_Answer << endl;
 
    //OR ( | ) 연산을 하면 둘중 하나라도 1이면 1이됨
    int OR_Answer = number1 | number2;    //0000 0011
    cout << "OR연산" << endl << OR_Answer << endl;
                        
    //XOR ( ^ ) 연산을 하면 같으면 0, 다르면 1이됨
    int XOR_Answer = number1 ^ number2;    //0000 0010
    cout << "OR연산" << endl << XOR_Answer << endl;
 
 
    return 0;
}

 

개념은 이런데 이걸 어디다 쓰냐구여?

https://blog.naver.com/kms32123/221238682781

[백준/BOJ] 1194번 달이 차오른다, 가자. 풀이 (C++)

 

요 문제에다가 씀.

n개의 열쇠를 가지고 문을 여는데 n번째 열쇠가 나한테 있나없나 체크해주는 용도로 비트마스크를 사용하는 용도..

또 xor 연산을 이용하면 swap을 할수도있죠

https://royhelen.tistory.com/31

[C++] xor 연산을 이용한 swap

 

비트를 이용해서 해결할수있는 문제도 많고 

특히 달이 차오른다 저 문제에서는 꼭 필요한 개념인듯..

또 부분집합 구할때 필수적으로 쓰이고해서 알아놓으면 매우 좋을듯.

내 복습용이니까 내맘대로 끝 

(부족한 내용은 나중에 또 추가하겠음)