부분집합 bitwise 표현

• i != 1,
• V = {v1, v2, v3, v4},
• A는 v1을 포함하지않는 V의 부분집합, {v2, v3, v4} = 111

1. vi 가 A에 포함되는가?

A & (1 << (i-2)) != 0 ? True : False

A = {v2, v3} -> 011

v2가 A에 포함되는가? v2 -> i = 2

1 << (2-2) = 1 << 0 = 1 = 001

011 & 001 = 001 != 0 

따라서 v2는 A에 포함된다.

 

2. A - {vi}  = A & ~(1 << (j-2)) ? True : False

A = {v2, v4} = 101

A - {v2} = ?

v2 -> j = 2

~(1 << (2-2)) = ~(1 << 0) = ~1 = ~001 = 110

101 & 110 = 100 = {v4}

 

3. K vertex를 포함하는가?

if ((A & (1 << (i-2))) != 0)

1을 한칸씩 shift하면서 001, 010, 100을 차례로 A의 bitwise와 &연산한다.

ex)

A = {v2, v3}이라면 bitwise는 011이된다. 이것을 001, 010, 100과 차례로 &하면 다음과 같다

A & 001 = 011 & 001 = 001 != 0. 따라서 v2는 포함한다.

A & 010 = 011 & 010 = 010 != 0. v3포함

A & 100 = 011 & 100 = 0 == 0. v4는 포함하지 않는다.