보통 우리가 짝수, 홀수를 구분한다면 코드를 이렇게 짤 것이다.
num 의 짝, 홀수 구분코드
if(num % 2 == 0){} → num 이 짝수면 true
if(num % 2 == 1){} → num 이 홀수면 true
여기서, 위의 홀수 코드는
if(num % 2 != 0){} → num 이 홀수면 true
이 코드가 더 좋다. 왜냐?
컴퓨터에서 0이랑 비교할 수 있으면 비교하는게 무조건 더 좋기 때문. (속도가 좀 더 빠르다. 근데 그렇게 큰 차이x)
이걸 비트 연산으로도 짝, 홀수를 구분할수가 있다.
2진수의 맨 오른쪽 비트가 0이면 짝수, 1이면 홀수임을 활용한것이다.
if( (num & 0x1) == 0){} → num 이 짝수 즉 2^0 자리가 0이면 AND 연산으로 인하여 true가 됨. 즉 짝수라는 거임
if( (num & 0x1) != 0){} → 마찬가지로 num이 홀수면 true 다.
위의 두 식처럼 이러한 것을 비트 마스킹(bit masking) 이라고 함.
양수 / 음수 판단
마찬가지로, 위의 비트 마스킹을 활용하여 양수, 음수도 구분할 수 있다.
보통 signed 형일때 최상위 비트가 0이면 양수, 1이면 음수라고 이미 배웠다.
이걸 비트마스킹을 활용하자면
int형 기준 1000 0000 0000 0000 0000 0000 0000 0000
여기에 1000 0000 0000 0000 0000 0000 0000 0000 을 AND 연산하면 최상위 비트가 1이 되므로 음수라 할 수 있음.
양수역시 0000 0000 0000 0000 0000 0000 0000 0000 을
1000 0000 0000 0000 0000 0000 0000 0000 과 AND 연산시 최상위 비트가 0이 되므로 양수로 할 수 있다.
코드로 표현시 16진수로 변환하여
if ( num & 0x80000000 == 0 ){} 이 조건이 참이면 num은 양수라는 뜻
if ( num & 0x80000000 != 0 ){} 이 조건이 참이면 num은 음수라는 뜻이 된다.
비트 플래그
비트 필드가 여러개 모인걸 말하는데 보통 bool 을 대신하여 사용함
bool 의 자료형 크기가 c# 기준 4byte 인데, 단순히 true와 false 만을 표현하는거 치고는 데이터크기를
많이 잡아먹어서 비트 플래그를 사용한다.
int 를 기준으로 총 32bit 각각에 true 와 false 의 상태를 저장할 수 있음.(총 32개의 상태 저장가능)
즉, 1 byte 의 경우 총 8개의 상태를 저장할 수 있다.
근데 각각의 상태를 어떻게 바꾸나?
바로 비트 마스크를 이용하여 각각의 상태를 바꿀 수 있다.
그냥 단순히 어떤 상태들이 저장된 1byte 비트 플래그 0110 0001 이 있다고 치자.
여기서 3번째 비트를 1로 on 하고 싶으면
0000 0100 이 비트 마스크를 만들어 둘이 OR 연산을 하면 된다.
0110 0001 | 0000 0100
그러면 3번째 비트만 1로 바뀐다.
반대로, 비트를 0 즉 off 하고 싶다면 AND 연산을 해주면 된다.
위의 비트플래그에서 1인 6번째 비트를 0으로 바꾸고자 할때
6번째를 제외한 모든 비트가 1인 1101 1111 비트 마스크를 만든뒤
둘이 AND 연산을 하면 0110 0001 & 1101 1111
0100 0001 이렇게 6번째 비트만 0으로 바뀐다.
특정 플래그를 토글(Toggle) 하는 방법도 있는데(토글이란 켜진상태면 끄고 꺼진상태면 켜는걸 말함)
XOR 연산을 활용한다.
ex) 1010 1010 이 있는데 3번째 비트를 토글하고자하면
1010 1010 ^ 0000 0100 = 1010 1110
토글하고자 하는 비트를 1로 하고 나머지는 0인 비트 마스크를 만들어 XOR 연산을 해주면 된다.
데이터 패킹((비트 플래그가 어떤 의미에서 보면 데이터를 막 한곳에다 꾸겨넣은 거와 비슷한데 이걸 패킹이라함)
bool 형이 아닌 그외의 자료형 데이터들을 한 곳에 저장할 수 있음.
ex) 어떤 물건을 고를때 기준이 색상 16가지 모양 8가지 무게 2가지 라고 할때
각각의 경우의 수는 2^4, 2^3, 2^1 이므로 4비트, 3비트, 1비트로 표현할 수 있음.
이 총 8비트를 하나의 변수에 저장할 수 있다.(8비트짜리 변수에 저장가능)
데이터 패킹을 사용하는 이유?
비트 플래그와 같은 메모리 용량 절약 효과를 위해서 뿐만 아니라 속도면에서도 이득이 있기 때문
ex) 각각 기준을 차례대로 정렬을 한다 칠때 데이터 패킹을 사용시 정렬 속도가 올라감
정렬을 색상, 모양, 무게 이 순서대로 정렬하고자 할시 데이터 저장도
색상 4비트- 모양 3비트 - 무게 1비트 이 순서대로 저장하면 됨.
ex) 색이 1101 파랑색이고, 모양이 100 네모이고, 무게가 0 50그램일때 표현
1101 100 0
비트 마스킹을 이용한 대소문자 변환
비트 마스킹을 이용해 대소문자도 변환 가능하다.
아스키코드의 영문자가 그 예인데, A의 경우 65이고 a의 경우 97 즉 32비트의 간격이 있음.
여기서 32비트는 2^5승 이므로
A : 64 + 1 : 0100 0001 인데
a : 64 + 32 + 1 : 0110 0001
A에 32비트 자리인 2^5번째가 1로 바뀐 형태이다.
여기서 알수 있는점은 비트가 1개만 있으면 2의 승수라는 것이다!!( 64, 32, 16, 8같은걸 말함 2의 배수를 말하는거아님)
문자 A에서 5번째 비트가 1로 바뀐 형태와 같으므로 비트마스크를 사용한 XOR연산을 사용하면
A 를 a로, a를 A로 자유자재로 변환할 수가 있다. 물론 다른 영문자들도 적용가능함.
2의 승수 판별하기
앞서 2의 승수는 1인 비트가 1개만 있으면 2의 승수라고 했는데 그말은 2의 승수에 2를 계속 곱해도 2의 승수이고
2로 나누어서 마지막이 1이고 나머지가 0인 경우에도 2의 승수라고 할 수 있다.
'이산수학' 카테고리의 다른 글
| 수학적 귀납법과 재귀, 분할 정복 (0) | 2021.05.12 |
|---|---|
| 실수를 표현하기 위한 IEEE 754 방식의 부동소수점 (1) | 2021.04.06 |