비트 연산에 대한 간단한 활용

비트 연산을 사용하면 빠르거나 간결한 코드를 작성할 수 있다.
이 외에도 활용 방안은 무궁무진하다. 앞으로 생각나는대로 추가할 생각이다.



* 2의 거듭제곱과 관련된 수를 곱하거나 나눌 경우에 Shift(>>, <<) 연산을 사용할 수 있다.

Example
a /= 2;      <->     a >>= 1;
a *= 16;     <->     a <<= 4;





* 나머지 연산을 And(&) 연산으로 대체할 수 있는 경우가 있다.
2^n - 1에 해당 하는 숫자보다 작으면, 이를 나머지 연산으로 사용할 수 있다.
왜냐하면 이진수로 나타내었을 때, 모든 자리의 숫자가 1이기 때문이다.

Example
b = 3, m = 4;
if (b % 15)     <->     if (b & 15)     <->     if (b & ((1<<m)-1))





* 어떤 숫자가 2의 거듭제곱인지 알고 싶을 때 And(&) 연산으로 간단하게 확인 가능하다.

Example
if (n & (n-1) == 0)
    return true;





* Swap 기능을 XOR(^) 연산으로 대체할 수 있는 경우가 있다.
정수형으로 나타낼 수 있는 자료형일 때만 가능하다.

Example
tmp = a;          <->        a ^= b;
a = b;                          b ^= a;
b = tmp;                      a ^= b;

Example
check = true;                        <->     check ^= true;
check = check ? false : true;





* 조합의 수를 구하는 경우나 집합에서도 활용할 수 있다.
왜냐하면 구하는 방법 자체가 2의 거듭제곱과 관련되어 있기 때문이다.

Example
가능한 모든 조합의 수 : nC0 + nC1 + ... + nCn = 2^n
공집합을 제외한 부분집합의 개수 : 2^n - 1