🔵 brute force - 비트 마스크 사용하기

안녕하세요 :) 오늘은 비트 연산 사용하는 BF 알고리즘에 대해 알아보겠습니다. 비트 연산을 잘 사용하면 정수로 집합을 표현할 수 있어, 공간 복잡도를 낮출 수 있게됩니다. 그럼 오늘도 화이팅 입니다🌿

비트연산이란 ?

하나의 정수로 집합을 나타내어, 집합 연산을 하는 방법입니다. 비트연산으로 집합 연산이 가능한 이유는, 집합엔 중복된 원소가 없고, 각 원소들에 대해 유무의 상태만 표현하기 때문입니다. 바로 이 집합의 개념을 2진수로 표현한 것이 비트 연산의 핵심입니다. 0과 1의 경우의 수만 가지는 2진수로 집합의 원소 유무를 나타냅니다. 즉,

집합의 각 원소 값 n → 비트의 자리 수로 표현, 2진수의 n번째 자리의 1로 표현
집합 → 하나의 정수로 표현, 해당 2진수를 10진수로 표현한 값

으로 나타내게 되는 것입니다. 이를 숫자로 예시를 들어보면 아래와 같습니다.

{1,3,4,5,9} → 570 = 2^1 + 2^3 + 2^4 + 2^5 + 2^9

또한, 비트연산을 사용하여 공간 복잡도를 크게 낮출 수 있습니다.

N크기의 집합 S 표현하는 경우에 기존 배열로 표현하는 방식과 비트로 표현하는 방식을 비교한다면 N만큼의 공간 복잡도 차이가 발생하게 됩니다.

N크기의 int형 배열 vs int형 변수 하나 → N만큼의 공간 복잡도 차이

---

비트연산 방법

and (&), or (|), xor (^)

• 두 수를 비트 연산 하는 경우엔, 가장 뒤의 자리부터 하나씩 연산을 수행하면 됩니다.

  0011011 & 1010011 = 0010011

  0011011 | 1010011 = 1011011

  0011011 ^ 1010011 = 1001000

not (~)

• 자료형에 따라 2진수의 자리수가 달라지고, 자리수에 따라 not연산의 결과가 달라지게 되므로 주의가 필요합니다. (int vs longlong)

  A = 01010011

  ~A (8비트, int) = 10101100

  ~A (32비트, longlong) = 11111111 11111111 11111111 10101100

• unsigned, signed에 따라선 값이 달라지진 않지만, 보여지는 값이 달라지므로 주의가 필요합니다.

shift left (<<), shift right (>>)

• A << B : A를 왼쪽으로 B비트만큼 민다.

  • A << B : $A * 2^B$

    1 << 0 = 1

    1 << 2 = 4 = 100

• A >> B : A를 오른쪽으로 B비트만큼 민다.

  • A << B : $A / 2^B$

    (a+b)/2 == (a+b)>>1

---

비트연산을 사용할 대상

• 0부터 N-1까지 정수로 이루어진 집합을 나타낼 때 사용합니다.
  • 1부터 N까지인 경우에는, 아래의 이유 때문에, 0부터 N-1까지로 변환하여 사용하는 것이 좋습니다.
    • 사용하지않는 0번째 비트 때문에, 공간이 2배 더 필요하게 됩니다.
    • 각종 연산을 변형해서 사용해야합니다.

---

비트연산 활용

집합 S와 원소 a에 대하여,

S에 a를 추가하기

S | (1 << a)

• 이미 갖고 있는 원소에 대한 처리는 무시되어야하므로, 더하기가 아니라 or연산을 합니다.

570 | $2^1$ = 570 | (1<<1) = 570 ($1000111010_2$)

570 | $2^2$ = 570 | (1<<2) = 574 ($1000111110_2$)

S에서 a를 제거하기

S & ~(1<<a)

• a에 해당하는 자리에 0, 나머지는 모두 1을 둔 것과 and 연산을 합니다.

  570 & ~$2^1$ = 570 & ~(1<<1) = 568 ($1000111000_2$)

  570 & ~$2^2$ = 570 & ~(1<<2) = 570 ($1000111010_2$)

S에 a가 있는지 검사하기

S & (1<<a)

• 위 식의 결과가 0인지 아닌지에 따라, S에 a가 있는지 알 수 있습니다.

  S가 a를 포함하지 않는 경우
  570 & $2^0$ = 570 & (1<<0) = 0

  S가 a를 포함하는 경우
  570 & $2^1$ = 570 & (1<<1) = 2

S의 a에 대해 토글하기

S ^ (1 << a)

• 토글이란 0을 1로, 1을 0으로 변환하는 것을 의미합니다.
• xor 연산은 서로 다른 수, 즉 0과 1에 대한 연산 결과만 1이므로, 특정 자리수의 값을 토글할 수 있습니다.
  • a 자리수가 0일땐, 0 ^ 1로, 결과가 1이 됩니다.
  • a 자리수가 1일땐, 1 ^ 1로, 결과가 0이 됩니다.
• 이를 통해 집합의 원소의 유무를 제어할 수 있습니다.

570 ^ $2^1$ = 570 ^ (1<<1) = 568 ($1000111000_2$)

570 ^ $2^2$ = 570 ^ (1<<2) = 574 ($1000111110_2$)

전체 집합 표현하기

(1 << N)-1

공집합 표현하기

0

• 공집합은 제외하라는 조건은, 탐색 반복문의 시작을 1부터 하여 만족시킬 수 있습니다.

---

비트연산 주의사항

• 1 << N - 1은 연산자 우선순위에 의해 1 << (N-1)과 같은 결과가 됩니다. 만약 (1 << N) -1과 같은 결과를 의도한다면, 괄호를 사용해야합니다.

• 자료형에 따라, 2진수의 자리수가 달라져, 비트연산에 영향을 줄 수 있다는 점을 명심해야합니다.

---