비트마스킹을 이해해보자

DOMTokenList.toggle

이 DOM 메서드의 경우 toggle 말 그대로 계속 유지되는 것이 아닌 일시적인 속성을 추가할 경우 사용하기에 적합한 메서드입니다. 예를 들어 특정 키가 입력 되는 순간에만 active 라는 class 를 classList에 추가할때 toggle 을 사용하면 유리합니다.

toggle(token)
toggle(token, force)

force 값의 경우 이미 classList에 추가하고자 하는 속성이 있을 경우 무시할 것인지 아닌지를 결정 짓는 요소입니다.

가르침

1. 비트마스킹

이 문제는 비트마스킹을 사용하여 문제를 해결하는 방법입니다. 이전에는 비트마스킹이라는 개념이 너무 어려웠지만 이 문제를 통해서 조금이나마 이해할 수 있게 되었습니다.

비트 마스킹을 Set 이라고 생각하고 해결한다면 조금이나마 이해하기 쉬웠습니다. Set은 객체에 값을 저장하고 해당 값들을 비교하며 중복을 제거하는 방식을 사용합니다. 하지만 비트 마스킹은 정수의 이진수 비트 하나하나를 Boolean 배열 처럼 사용하는 기법입니다.

예를 들어 알파벳을 기준으로 생각해보겠습니다. 알파벳은 총 26자이고 이를 아스키코드로 변환하면 문자열을 정수로 표현이 가능해집니다.

0번 비트: 'a' -> 96 - 96
1번 비트: 'b' -> 97 - 96
...
25번 비트: 'z' -> 121 - 96

이제 문자열의 집합을 예를 들어 설명해보겠습니다. 예를 들어 {'a', 'c'}라는 집합을 비트를 이용해 표현해보겠습니다.

• a는 0번째 $\rightarrow 1 \ll 0 = 1_{(2)}$
• c는 2번째 $\rightarrow 1 \ll 2 = 100_{(2)}$
• 둘을 합치면 $\rightarrow 101_{(2)} = 5_{(10)}$ 이 된다.

위의 정수 5가 곧 {'a', 'c'}라는 집합을 의미하는 것과 같습니다. 이제 비트마스크가 어떤 것을 표현하려는 것인지는 알았습니다. 집합 내의 요소들을 비교하기 위한 핵심 비트 연산자에 대해서 이야기해보겠습니다.

2. 핵심 비트 연산자

1. 원소 추가 (OR 연산 |)

let mask = 0;
mask |= (1 << n)

위의 연산인 |= 이 mask에 특정 n번째 알파벳을 추가할때 사용이 됩니다. 실제 예시를 들어서 설명해보겠습니다. 예를 들어 "aca"라는 단어를 처리할때를 이야기해보겠습니다.

let bit = 0 //...00000

let aBit = 'a'.charCodeAt(0) - 96
bit |= 1 << aBit

위 연산을 수행한 결과는 00000 | 00001 를 수행해야 하므로 00001 이 됩니다. 비트 연산에서 |(OR) 연산자는 서로 비트가 같은 경우에는 똑같이 작성하지만 비트가 서로 다른 경우에는 1인 비트의 연산자를 기록하기 때문입니다.

let cBit = 'c'.charCodeAt(0) - 96
bit |= 1 << cBit

합치기를 수행할 경우 00001 | 00100 $\rightarrow$ 00101 가 되며 현재 상태는 { 'a', 'c' } 상태인 집합입니다.

aBit = 'a'.charCodeAt(0) - 96
bit |= 1 << aBit

마지막 글자인 "a" 를 처리할 경우입니다. 이때 이미 집합의 상태가 { 'a', 'c' } 이고 이미 "a"가 포함이 되어 있는 상태입니다. 그렇기 때문에 비트 1 << 0 $\rightarrow$ 00001 를 합연산을 수행하면 00101 | 00001 이므로 결과는 00101 이 나오게 됩니다. 이미 "a" 는 포함이 되어 있기 때문에 변화가 없습니다.

위에서 볼 수 있듯이 Set 에서 자동으로 중복되는 값을 제거하는 것과 같이 비트마스킹 또한 자동으로 중복을 제거하는 것을 확인할 수 있습니다.

2. 포함 여부 확인 (AND 연산 &)

현재 상태 mask에 $n$번째 알파벳이 있는지 확인할 수 있습니다. 이 경우 다음과 같이 사용합니다.

if ((mask & (1 << n)) !== 0) { // 같은 경우
	doSomething()
}

(mask & (1 << n) 의 값이 0이 아니면 포함된 것으로 간주합니다. 이 식은 Set.has(element)와 똑같은 역할입니다. 이 또한 예를 들어 설명해보겠습니다.

현재 집합이 {"a", "c"} 인 상태 비트로는 101 인 상태라고 가정해보겠습니다. 이 비트마스크에서 우리는 "c"가 포함되었는지를 알고 싶습니다. 이 경우 mask & (1 << 2) 를 수행하게 되면 101 & 100 을 수행하게 됩니다. AND 연산자의 경우 비교하는 두 비트의 값이 1이어야만 1이 될수 있기 떄문에 101 & 100 의 결과는 100이 됩니다.

• mask & (1 << 2) $\rightarrow$ 101 & 100
• 결과: 100 (4라는 숫자)
• 4 !== 0 인가? 참(True). $\rightarrow$ "이미 c를 배웠구나!"

라는 결론을 내리게 됩니다. 이제는 없는 글자인 "b"를 찾아보겠습니다. "b"의 경우 010의 비트를 갖으므로 mask & (1 << 1) 은 101 & 010 이 됩니다. 연산을 수행하면

• mask & (1 << 1) $\rightarrow$ 101 & 010
• 결과: 000 (0)
• 0 !== 0 인가? 거짓(False). $\rightarrow$ "b는 아직 안 배웠구나!"

라는 결과가 나오게 되므로 아직 "b"는 포함이 되어 있지 않다는 사실을 알 수 있는 것입니다.

3. 부분 집합 확인

내가 배운 글자 목록(learnMask)으로 특정 단어(wordMask)를 읽을 수 있는지 확인할 때는 다으모가 같은 식을 사용합니다.

if ((wordMask & learnMask) === wordMask) {
	doSomething()
}

즉, 단어에 필요한 모든 비트가 배운 글자 비트에 포함되어 있어야 합니다. & (AND) 연산: 두 비트가 모두 1일 때만 1을 반환합니다. 즉, 공통된 글자만 남깁니다. 만약 내가 단어에 필요한 모든 글자를 다 배웠다면, (단어 ∩ 내 지식) = 단어가 되어야 합니다.

예를 들어 보렜습니다. 목표 단어(wordBit)를 "ac" 라고 가정하고 내 지식(mask)을 "abc" 라고 가정해보겠습니다. 이 경우 계산을 수행하면 다음과 같습니다.

• 계산 가능한 경우:

1. wordBit & mask $\rightarrow$ "ac" & "abc" $\rightarrow$ 101 & 111

   • 첫째 자리(a): 둘 다 1 $\rightarrow$ 1
   • 둘째 자리(b): 단어엔 없는데(0) 난 앎(1) $\rightarrow$ 0 (교집합이므로)
   • 셋째 자리(c): 둘 다 1 $\rightarrow$ 1
   • 결과: 101

2. 결과(101)가 원래 단어(101)와 같은가?

   • 같음! $\rightarrow$ 읽을 수 있다.

• 반대 예시 (못 읽는 경우) 목표 단어 = "ac"

1. wordBit & mask $\rightarrow$ "ac" & "ab" $\rightarrow$ 101 & 011

   • 첫째 자리(a): 단어엔 없는데(0) 난 앎(1) $\rightarrow$ 0 (교집합이므로)
   • 둘째 자리(b): 단어엔 없는데(0) 난 앎(1) $\rightarrow$ 0 (교집합이므로)
   • 셋째 자리(c): 둘 다 1 $\rightarrow$ 1
   • 결과: 001

2. 결과(001)가 원래 단어(101)와 같은가?

   • 다름! $\rightarrow$ 못 읽는다.