알고리즘 - 비트연산 응용

입력한 수가 2^n 꼴인지 확인하시오

 

비트연산자를 응용한다.

 

2^n 꼴의 수는 2진법으로 표현하면 비트에서 무조건 한자리만 1이고 나머지는 전부 0이다.

 

비트연산자는 이진수에 대해 비트단위로 적용되는 연산이다.

 

NOT : 비트 반전. 0은 1로 1은 0으로 반전한다.

OR : 두 이진비트중 하나라도 1이면 1. 둘다 0 이면 0

AND : 두 이진비트 둘다 1이여야 1. 하나라도 0이면 0

XOR : 두 이진비트가 서로 달라야 1. 같으면 0

 

SHIFT : 입력한 자리수만큼 전체 비트를 좌 or 우로 민다.

 

단항연산자 - : 부호 반전. 이진수에 NOT 연산을 한뒤 1을 더하는 연산.

 

2^n 꼴을 판단하기 위해서는 자기 자신의 부호반전 값과 AND 연산을 한 경우를 따진다.

 

ex)

34 의 2진법 표현 

00101100

NOT

11010011

+1

11010100

 

34 & -34

 

00101100

&

11010100

=

00000100

 

32 

00100000

NOT

11011111

+1

11100000

 

32 & -32

00100000

&

11100000

=

00100000

 

 

예를 보면 2^n  꼴은 연산 결과가 기존의 자기 자신과 같게 나오고

나머지 수는 같게 나올수 없는 구조이다.

 

 

비트 연산을 응용한 플래그 선택.

일반 변수보다 비트연산이 훨씬 빠름.

 

flag = flag | 2^n;

n+1번째 비트를 켠다 라는 의미의 연산. 여기에서의 2^n은 마스크라고 부른다.

flag = flag & -(2^n) 

위의 반대로 비트를 끈다 라는 의미.

 

플래그와의 & 연산으로 자리수 별 1개의 값을 할당하면됨.

8비트 라고 할때 

각 자리별로 1개씩 8개의 조건을 제어할 수 있다.

 

토글

flag = flag ^ (2^n)

해당 자리의 비트가 켜져있다면 끄고 꺼져있다면 켜는 연산.