[스터디] 비트조작 , 완전탐색

비트 조작

---

비트 연산자

AND

• 둘 다 1이면 1, 둘 중 하나라도 0이면 0이다.
• 1010 AND 1110 = 1010
• 연산자 : &

OR

• 둘 중 하나라도 1이면 1, 둘다 0이면 0이다.
• 1010 OR 1110 = 1110
• 연산자 : |

NOT

• 모든 bit값을 반대로 바꾼다
• NOT ( 1010 ) = 0101
• 연산자 : ~

XOR

• 값이 같으면 0, 다르면 1이다.
• 1010 XOR 1110 = 0100
• 연산자 : ^

비트 시프트

• 산술 우측 시프트
  • 값을 2로 나눈 것과 같다.
  • 연산자 : >>
  • 부호 비트는 바뀌지 않음.
• 논리 우측 시프트
  • 일반적으로 비트를 옮길 때 처럼 동작한다.
  • 연산자 : >>>
  • 비트를 우측으로옮긴 후에, 최상위 비트에 0을 넣는다.

추가 정보

• 0s : 모든 bit가 0
• 1s : 모든 bit가 1

2의 보수, 음수

• 컴퓨터는 일반적으로 정수를 2의 보수 형태로 저장한다.
• 음수에 대해서는, 부호비트를 1로 세팅한 후 2의 보수를 취한 형태로 표현한다.
• n비트 숫자에 대한 2의 보수는, 2의 n승에 대한 보수와 같다.

C++ 에서의 비트 조작

• std::bitset을 사용하려면, header를 포함해야 한다.

비트 조작 알고리즘

• 코딩 인터뷰 준비에서 능숙한 비트조작 능력은 중요하다.

Get

• 특정 위치에 있는 bit값을 가져온다.
• idx = 0은, LSB의 위치를 의미한다.

bool getBit(int num, int idx){
    return (1<<idx)& num != 0;
}

• 입력

  대상 숫자, bit를 가져오고자 하는 위치

• 출력

  0 or 1 (boolean value)

  이 때 값을 가져오고자 하는 위치는 LSB에서 0이다.

Set

• 특정 위치의 bit값을 1로 설정한다.

int setBit(int num, int idx){
    return num | (1 << idx);
}

Clear

• 특정 위치의 bit값을 지운다. (0으로 설정한다.)

int clearBit(int num, int idx){
    int mask = ~(1 << idx);
    return num & mask;
}

• 한 개가 아닌, 특정 범위의 비트 여러개를 지우고 싶을 때

int clearBits(int num, int start, int end){
    int headMask = (~0 >> start) << start;
    //32비트 정수이기 때문에 31
    int tailMask = (~0 << (31-end)) >> (31 - end);

    int mask = headMask & tailMask;
    return num & mask;
}

Update

• 특정 위치의 bit를 원하는 값으로 갱신할 수 있다.
• 특정 위치의 bit을 clear한 후에, 다시 원하는 value로 set하면 된다.

int updateBit(int num, int idx, int val){
    return (num & ~(1 << idx)) | (val << idx);
}

Toggle

• 0 -> 1, 1 -> 0으로 바꾸어 주는 것.
• xor연산을 통해 할 수 있다

int Toggle(int num, int idx){
    return num ^ (1 << idx);
}

MSB, LSB

• Serial Communication을 할 때, 하나의 단위시간에 하나의 비트만 보낼 수 있기 때문에, 어떤 위치의 bit 부터 전송되는지를 알아야 한다.

  MSB부터 보내는지, LSB부터 보내는지를 아는 것은 매우 중요하다.

  송수신측에서 이 부분을 통일하지 못하면 수신이 잘못된다.

• LSB

  Least Significant Bit의 약자.

  하나의 데이터 형에서 가장 낮은 위치의 bit을 의미한다.

  2의 0승 자리

bool getLSB(int num){ 
    int mask = ~(num) + 1; return num & mask; 
}

• MSB

  Most Significant Bit의 약자.

  하나의 데이터 형에서 가장 높은 위치의 bit을 의미한다.

  unsinged char type에서 MSB는 2의 7승위치의 값을 의미한다.

  signed char type에서 MSB는 부호 자리를 나타낸다. 따라서 MSB로 해당 수가 음수인지 양수인지 알 수 있다.

bool getMSB(int num){
    return num >> 31; 
}

참고자료

https://iamsjy17.github.io/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98_%EA%B8%B0%EC%B4%88/2019/05/09/bitop.html

https://m.blog.naver.com/PostView.nhn?blogId=ansdbtls4067&logNo=220886567257&proxyReferer=https:%2F%2Fwww.google.com%2F

https://m.blog.naver.com/PostView.nhn?blogId=yhjeong89&logNo=220770224996&proxyReferer=https:%2F%2Fwww.google.com%2F

완전 탐색

---

재귀 호출

• 재귀 함수

  함수 내에서 자기 자신을 다시 호출하는 형태의 함수를 말한다.

  • 커다란 문제를 유사한 여러 작은 조각으로 쪼갠 뒤, 한 조각을 수행하고 나머지를 자기 자신을 호출해서 실행하는 함수

  void recurFunction(void){
      recurFunction();
  }

  • 위의 코드처럼 함수 내부에 자기 자신을 다시 호출하는 형태이면 되지만, 위의 코드는 정상적인 사례가 아니다. base case가 없기 때문이다.

  • base case

    • 더 이상 쪼갤 수 없는 가장 작은 작업. (최소한의 작업)

      재귀호출을 하지 않고 바로 return하는 조건문에 포함된다

    • base case가 존재하지 않는 재귀 함수는 영원히 종료되지 않아 오류를 일으킨다.

    • base case를 선택할 때는, 모든 경우의 수에 대해 항상 base case를 이용해 계산될 수 있도록 고려해서 선택해야 한다.

완전 탐색

• brute - force (무식하게 푼다)라고도 불린다.

• 컴퓨터의 빠른 계산 속도를 이용해 어떤 문제에 대해 가능한 모든 경우의 수를 전부 만들어보는 알고리즘을 뜻한다.

• 코딩 테스트에서 주어진 제한 시간과 해당 문제의 시간 복잡도 및 가능한 모든 경우의 수를 비교해서 완전탐색으로 풀어도 괜찮을지 판단해야 한다.

• 예를들어 4자리 숫자로 이루어진 비밀번호를 맞춰야 하는 문제에서, 0000 ~ 9999의 모든 경우를 다 집어넣어 보는 방식을 말한다.

완전 탐색 방법

1. 반복문 사용
   • 반복문을 중첩해서 모든 경우를 탐색한다
2. 비트 마스크
   • 정수를 비트열로 표현하면 집합을 나타낼 수 있다.
   • 5자리 비트로 이루어진 정수로 5명의 item에 대한 모든 집합을 나타낼 수 있다.
   • n번째 원소를 포함하고 싶으면 n번째 bit를 1로 설정하고, 제외하고 싶으면 0으로 설정하면 된다.
   • 위에 있는 비트 조작 연산을 이용하여 풀 수 있다.
3. 순열, 조합 사용
   • 순열, 조합 함수를 직접 구현해서 사용해도 되지만, C++의 경우 STL의 algorithm에 해당 함수가 구현되어 있다.
     • next_permutation
     • prev_permutation
4. 재귀 함수 사용

참고자료

https://ikso2000.tistory.com/75

https://twpower.github.io/82-next_permutation-and-prev_permutation