비트연산
요약
~
- 비트를 반전시킨다.
&
- 대응되는 비트가 모두 1일 때 1이다.
|
- 대응되는 비트가 모두 0일 때 0이다.
^
- 두 개의 비트가 달라야 1이다.
<<
- 지정한 수만큼 왼쪽으로 비트들을 이동시킨다.
>>
- 지정한 수만큼 오른쪽으로 비트들을 이동시킨다.
개념
두 피연산자의 대응되는 비트(bit)끼리 연산해서 그 결과를 리턴
장점: 일반 산술 연산보다 훨씬 빠르다. (수배 ~ 수십배)
종류
~
- 비트 부정 == 비트 NOT 연산자
- 비트를 반전시킨다.
&
- 논리곱 == 비트 AND 연산자
- 대응되는 비트가 모두 1일 때 1이다.
|
- 논리합 == 비트 OR 연산자
- 대응되는 비트가 모두 0일 때 0이다.
^
- 배타적 논리합 == 비트 XOR 연산자
- 두 개의 비트가 달라야 1이다.
<<
- 비트 왼쪽 쉬프트 연산자
- 지정한 수만큼 비트들을 왼쪽으로 이동시킨다.
>>
- 비트 오른쪽 쉬프트 연산자
- 지정한 수만큼 비트들을 오른쪽으로 이동시킨다.
특징
- ~만 단항 연산자고, 나머지는 모두 2개의 피연산자를 취하는 이항 연산자
- 비트 연산은 정수 수준에서만 의미가 있기 때문에 피연산자는 모두 정수형 or 정수로 자동 변환될 수 있는 타입이어야 한다.
- 실수나 포인터 등은 비트 연산자와 함께 사용할 수 없다.
비트 연산 진리표
숫자를 들어가며 비트 연산을 해보자.
~ 부정
0x59의 ~ 연산 결과는 비트를 모두 뒤집은 0xa6이 되는데, 이 두 수는 1의 보수 관계다.
& 논리곱, | 논리합
& 연산은 0과 &되는 비트는 그 값에 상관없이 무조건 0이 되고, 1과 &되는 비트는 원래 비트값을 그대로 유지하는 특성이 있다.
이진수 00001111과 & 연산을 하면 상위 4비트는 0이 되며 하위 4비트만 값을 유지한다.
이런 식으로 특정 비트를 강제로 0으로 만드는 연산을 마스크 오프(mask off)라고 한다.
1과 | 되는 비트는 무조건 1이 되고, 0과 | 되는 비트는 원래 값을 유지한다.
이렇게 비트를 강제로 1로 만드는 연산을 마스크 온(mask on)이라고 한다.
^ 배타적 논리합
지정한 비트를 반전시킨다.
비트가 서로 다를 때만 1이 되고 같으면 0이 된다.
이를 마스크 반전이라 한다.
반전된 값은 다시 반전시키면 원래대로 돌아온다.
이미지의 이동이나 반복적인 점멸 처리에 사용한다.
«, » 쉬프트 연산
쉬프트(Shift) 연산자는 비트들을 좌우로 이동시킨다.
”»”: 오른쪽으로 비트 이동
제일 왼쪽 비트는 0으로 채워짐.
”«”: 왼쪽으로 비트 이동
제일 오른쪽 비트는 0으로 채워진다.
쉬프트 연산은 고속의 그래픽 처리가 필요할 때 램을 직접 엑세스하기 위해서 사용한다.
쉬프트 연산의 피연산자는 주로 부호없는 정수형.
부호 있는 정수형은 가능은 하지만, 부호 비트는 쉬프트 대상에서 제외된다.
이외 실제 코딩에 자주 이용되는 사례: 곱셈, 나눗셈의 대용
#include <iostream>
using namespace std;
int main()
{
int num = 16;
cout << (num << 1) << '\n';
cout << (num << 2) << '\n';
cout << (num >> 1) << '\n';
cout << (num >> 2) << '\n';
}
32
64
8
4
비트를 왼쪽으로 한 칸 이동시키면 모든 자릿수의 지수가 1이 올라간다.
즉, 2배가 된다.
그 반대는 당연히 1/2배다.
즉, 쉬프트 연산은 2의 제곱에 대한 곱셈 및 나눗셈 연산을 빠르게 실행할 수 있다.
(a << b) == a * 2^b
다만 정수형 타입처럼 홀수는 절반으로 줄어들 경우 오차가 생긴다. (
ex.
(7 >> 1) == 3)
또한 다른 수의 곱셈에도 능히 활용할 수 있다.
3배 : a << 1 + a;
9배 : a << 3 + a;
15배 : a << 4 - a;
60배 : a << 6 - a << 2;
#include <iostream>
using namespace std;
int main()
{
int num = 4;
cout << ((num << 1) + num) << '\n';
cout << ((num << 3) + num) << '\n';
cout << ((num << 4) - num) << '\n';
cout << ((num << 6) - (num << 2)) << '\n';
}
12
36
60
240
추가로, 비트 연산자는 [], ->, +, ++ 등 보다 연산자 우선순위가 높지 않기 때문에
왠만하면 피연산자 밖에 (a « 2) 소괄호를 넣어 사용하자.
활용 - 프로그래머스 Level 1. 비밀지도
처음 다른 사람의 풀이를 봤을 때 충격적이었던 문제.
처음에 전혀 비트 연산을 사용하지 못했지만,
비트 연산을 조금 공부해 다음과 같이 풀었다.
이외에도 비트마스킹 관련 문제는 백준에 특히 많은 것 같다.
더 연습해 코테에도 활용해보자.
참고
※ 틀리거나 개선할 부분이 있다면 알려주세요.
댓글남기기