c++/ 자료구조&알고리즘 개념 복습하기 - 20 / 시프트 연산자, 비트마스킹

< 왼쪽 시프트 연산자 >

• 왼쪽 시프트 연산자 << 는 수를 왼쪽으로 이동하는 것
• 1 << n 형태 = 2의 n승
• 1 << 2 = 이진수 형태 0001 에서 0100 이 되는 것

---

int main()
{
    int a = 8;
    int b = 1 << 1;

    int c = a | b; // or 연산
    int d = a | a;

    cout << c << "\n";
    cout << d << "\n";

    return 0;
}

//출력
10
8

---

< 특정 자릿수에 1 존재하는지 확인하기 >

• &연산 활용!

int main()
{
    int a = 12; // = 1100
    int inx1 = 0; 
    int inx2 = 3;

    if(a & (1 << inx1))  // = 0001
    {
        cout << "inx1\n";
    }

    if (a & (1 << inx2)) // = 1000
    {
        cout << "inx2\n";
    }
    
    cout << (a & (1 << inx2));

    return 0;
}

//출력
inx2
8 (1100, 1000 & 연산 결과!)

---

< 비트마스킹 >

• boolean 배열의 역할을 하는 '하나의 숫자' 를 만들어서 '비트 연산자' 를 통해 탐색, 수정 등의 작업을 수행
  
  

< 모든 경우의 수 >

• 각 원소별로 선택/미선택 2가지 선택지 존재 -> 2^n 가지 경우의 수
• & 연산자를 활용해서 해당 위치의 원소가 포함된 경우인지 아닌지 판별한다

 int arr[5] = {1, 2, 3, 4, 5};

    for(int i = 0; i < (1 << 5); i++) {
        string str = "선택 목록 : ";
        for(int j = 0; j < 5; j++) {
            if(i & (1 << j)) {
                str += to_string(arr[j]);
                str += " ";
            }
        }
        cout << str << "\n";
    }
    
// 출력
선택 목록 : 
선택 목록 : 1 
선택 목록 : 2 
선택 목록 : 1 2 
선택 목록 : 3 
선택 목록 : 1 3 
선택 목록 : 2 3 
선택 목록 : 1 2 3 
선택 목록 : 4 
선택 목록 : 1 4 
선택 목록 : 2 4 
선택 목록 : 1 2 4 
선택 목록 : 3 4 
선택 목록 : 1 3 4 
선택 목록 : 2 3 4 
선택 목록 : 1 2 3 4 
선택 목록 : 5 
선택 목록 : 1 5 
선택 목록 : 2 5 
선택 목록 : 1 2 5 
선택 목록 : 3 5 
선택 목록 : 1 3 5 
선택 목록 : 2 3 5 
선택 목록 : 1 2 3 5 
선택 목록 : 4 5 
선택 목록 : 1 4 5 
선택 목록 : 2 4 5 
선택 목록 : 1 2 4 5 
선택 목록 : 3 4 5 
선택 목록 : 1 3 4 5 
선택 목록 : 2 3 4 5 
선택 목록 : 1 2 3 4 5 

---