1. Bit 연산자

• AND (&) : 특정 비트를 추출하거나 삭제하고 싶을 때

• OR (|) : 특정 비트를 강제로 켜고 싶을 때

• XOR (^) : 두 비트의 차이를 저장 또는 비트를 반전시킬 때

• NOT (~) : 모든 상태를 뒤집을 때

n & (1 << i)	// i번째 비트가 켜져 있는지 확인 (Masking)
n & ~(1 << i)	// i번째 비트를 0으로 설정
n | (1 << i)	// i번째 비트를 1로 설정
n ^ (1 << i)	// i번째 비트를 반전 (0→1, 1→0)
n & -n			// 가장 오른쪽에 있는 '1' 비트만 추출

2. 2의 배수

• 어떤 숫자가 2의 배수인지를 알고 싶다면 &를 사용하면 된다

if ((n & 1) == 0) 
{
    cout << "Even Number";
}

3. Hamming Weight

• n = n & (n - 1)

• 비트에서 가장 우측에 있는 1을 0으로 바꿔주는 알고리즘

• 따라서, 어떤 비트에 n개의 1이 들어있다면, 이 알고리즘을 n번 반복시 해당 비트는 0이된다

• 비트 하나씩 보며 1인지 세는 것보다 훨씬 효율적

int count = 0;
while (n != 0)
{
    n &= (n - 1);  // 가장 오른쪽의 1을 제거
    count++;   	   // 제거할 때마다 숫자를 셈
}
return count;

// n = 11 (1011₂)
// 첫 번째 연산: 1011 & 1010 = 1010 (가장 오른쪽 1 제거) → Count: 1
// 두 번째 연산: 1010 & 1001 = 1000 (다음 1 제거) → Count: 2
// 세 번째 연산: 1000 & 0111 = 0000 (마지막 1 제거) → Count: 3
// 종료: n이 0이 되었으므로 멈춤.

4. 2의 지수인 정수

• 마찬가지로 이 알고리즘을 통해, 어떤 정수가 2의 지수인지를 빠르게 알 수 있다

• 2의 지수인 정수의 비트는 오직 1개의 1만을 가지게 된다

• 따라서, 해밍 웨이트를 한 번만 실행하고 값이 0이 되는지를 확인하면 된다

n &= (n - 1); 
if (n == 0)
{
	cout << "power of 2";
}

5. XOR의 특징

• 비트가 서로 다를 때 1이 되는 연산

• 자기 자신과 XOR 하면 0이 된다 (비트가 똑같으므로) a ^ a == 0

• 0과 XOR 하면 자기 자신이 된다 (0과의 차이값이므로) a ^ 0 == a

• 순서가 바뀌어도 상관없다 (교환법칙) a ^ b ^ a == a ^ a ^ b

6. 짝이 없는 정수 찾기

• 정수 배열이 하나 있다.

• 단 하나의 숫자를 제외한 모든 숫자는 자신의 짝이 있다 (2개, 4개...)

• 이 배열에서 딱 한 번만 등장하는 그 숫자를 찾아내는 방법은?

• XOR은 교환법칙이 성립한다.
  짝이 있는 숫자끼리 XOR을 해버리면 0이 나오게 된다.
  0과 자기 자신을 XOR하면 자기자신이 나온다.
  그러므로 배열의 모든 숫자를 XOR하면 홀로 존재하는 정수가 나오게 된다

7. Swap

• 보통 정렬하기 위해 두 변수를 swap하는 경우, temp라는 임시변수를 만들었었음

auto temp = a;
a = b;
b = temp;

• 하지만, XOR을 이용하면 temp없이 Swap이 가능함

• XOR하면 두 비트간의 차이가 저장됨(다르면 1, 같으면 0)

• 그래서 XOR해서 나온 결과값에 다시 하나의 비트를 XOR해주면 상대비트가 나옴

a ^= b
b ^= a
a ^= b

• a ^ b를 하면 해당 결과값은 두 비트간의 차이 정보 (a에 저장)

• 따라서 이 비트차이(a)에 대해서 b를 XOR하면 a가 나옴(b에 저장)

• 그리고 이 비트차이(a)에 대해서 b를 XOR하면(기존 a값) b가 나옴(a에 저장)