10진수를 2로 계속 나누면서 더 이상 나누어 지지않을 때까지 순서대로 밑에서 부터 위로 나머지를 나열하기
코드로 나타내면 다음과 같다.
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n;
vector<int> bit;
int main(){
cin>>n;
while(n>0){
bit.push_back(n%2); //2로 나눈 나머지를 저장
n/=2; //n이 0이 되기 전까지 계속 나누어 준다.
}
reverse(bit.begin(),bit.end()); //나머지의 역순으로 저장해준다.
for(auto i:bit){
cout<<i; //비트 값들을 출력
}
}
비트 연산자
연산자
활용
&
두 비트 값이 1이면 True
|
두 비트 값 중 하나가 1이면 True
~
비트 값을 1을 0으로 0을 1으로 바꾸고 1을 더해준다.
^
비트가 서로 다르면 True
<<
모든 비트를 오른쪽으로 올김
>>
모든 비트를 왼쪽으로 옮김
&연산자(and)
#include<iostream>
using namespace std;
int n;
int main(){
if(1&1) cout<<"1&1: "<<"True"<<"\n";
if(1&0) cout<<"1&0: "<<"True"<<"\n";
if(0&1) cout<<"0&1: "<<"True"<<"\n";
if(0&0) cout<<"0&0: "<<"True"<<"\n";
}
1&1: True
|연산자(or)
#include<iostream>
using namespace std;
int n;
int main(){
if(1|1) cout<<"1|1: "<<"True"<<"\n";
if(1|0) cout<<"1|0: "<<"True"<<"\n";
if(0|1) cout<<"0|1: "<<"True"<<"\n";
if(0|0) cout<<"0|0: "<<"True"<<"\n";
}
1|1: True
1|0: True
0|1: True
~연산(Not연산)
#include<iostream>
using namespace std;
int n;
int main(){
cout<<~(5);
}
-6
~연산을 적용했을 때 비트로 보았을 때 5는 0101에 적용하면 .... 1111 1010으로 되지만 2의 보수법을 적용한다면 값에 1을 더하고 음수로 전환한 값이 나오게 된다.
비트 연산자 활용하기
인덱스에 해당하는 비트를 끄기
n&=~(1<<i) (i: i 번쨰 인덱스)
1. 1<<i는 i번쨰 인덱스의 비트를 1로 만드는 것이다. 2. 1<<i 에 ~연산을 적용하는 것은 i번째 비트를 제외하고 나머지의 비트를 켜는 것이다. 3. &연산을 하는 것은 비트가 둘다 1인 경우에만 1을 반환해주기 때문에 i번째 비트를 제외한 나머지 상위 비트만 유지해준다.
ex) 1010(2)이 있다고 하자 1. 2번째 인덱스를 끄고 싶다고 하면 1<<2 연산을 하여서 0010을 만들어 준다. 2. ~연산을 적용해주면 1101이 된다. 3. 마지막으로 1010과 1101에 &연산을 적용하면 1000이 된다.
최하위에 켜저있는 비트 찾기
i=(n&~n)
1. n&~n의 경우에서 ~n은 최하위 비트를 제외한 나머지 비트를 바꾸기 때문에 최하위 비트만 켤 수 있다.
ex) 1100(2)으로 예시를 들어보자 1. ~(1100)은 0011+1=0100이고 1100과 0100에 &연산을 적용하면 켜져 있는 인덱스를 찾을 수 있다.
크기가 s인 비트를 모두 켜기
(1<<s)-1
1. 1<<s는 s+1번 쨰의 비트를 켜는 것이다. 2. (1<<s)-1은 s+1번 째 비트를 끄고 나머지 하위 비트를 모두 켜게 된다.
ex) 크기가 4인 모든 비트가 켜진 집합만들기 1. 1<<s를 하면 1 0000이 된다. 2. (1<<s)-1은 1111이 된다.
i번 쨰 비트를 켜기
n|=(1<<i)
1. 1<<i로 i번째 비트를 켜준다. 2. |연산은 두 비트가 0인 것을 제외하면 1을 반환해주기 때문에 i번쨰 비트를 켜준다.
ex) 1010을 예시로 들어보자 1. 2번쨰 비트를 켠다면 0100이 된다. 2. 1010과 0100을 |연산을 한다면 1110이 되므로 2번째 비트를 켜게 된다.
