이번 포스팅에서는 2진수의 특성과 비트연산을 활용해서 할수 있는 여러가지 프로그래밍적인 기법을 알아보겠다.
성능을 위해서 실제로 우리가 작성한 코드를 컴파일러 수준에서 앞으로 배울 연산들로 바꿔주는 경우도 있다. 이렇게 2진수를 활용한 여러가지 꼼수(?)들을 사용해서 기계가 어떻게 연산을 처리하는지에 대해 조금 더 잘 이해해보도록 하자.
2진수에서 홀수 짝수 구분하기
- 이진수에서 유일하게 홀수인 부분은 제일 첫번째 비트인
2^0, 즉 1이다. - 이 뜻은 제일 첫번째 비트만 켜져있으면 홀수이고, 꺼져있으면 짝수이다
- 일반적인 홀수 짝수 비교 코드
// 짝수 구분 if (num % 2 == 0) { // do something } // 홀수 구분 1 if (num % 2 == 1) { // do something } // 홀수 구분 2 if (num % 2 != 0) { // do something }- 홀수 구분할때 “홀수 구분 2”로 하는게 더 좋다. 컴퓨터에서 0이 아닌 수와 비교하는거보다 0으로 비교하는게 아주 미세하게 더 빠르다.
- 마지막 비트만 보고 홀수 짝수 비교하는 코드
if ((num & 0x1) == 0) /* 짝수 */ { } if ((num & 0x1) != 0) /* 홀수 */ { }- 원본 변수에
0x1인 마지막 비트만 켜져있는 1을&연산하면 마지막num변수의 마지막 비트만 남게 되고, 마지막 비트만 0인지 아닌지 비교 가능하다 num & 0x1를 통해서num의 값에 있는 첫번째 비트를 제외한 비트들은 전부 &연산을 통해서 0으로 만들어 버렸다. 즉, 마스킹(masking)했다.- 이렇게 필요한 비트만 추출 해 내는것을 비트마스킹이라 한다
- 원본 변수에
비트 마스킹(bit masking) : 음수랑 양수 판단하기
if ((num & 0x80000000) == 0) // 양수
{
}
if ((num & 0x80000000) != 0) // 음수
{
}- 최상위 비트가 1이면 음수, 0이면 양수
- 16진수니깐 마지막비트에 8이온다. 8은 2진수로 바꾸면 1000
(num & 0x80000000) == 0이란 말은 최상위 비트가 세팅이 안되어있다는 말이니깐 양수- 최상위 비트 제외 나머지 비트는 비트마스킹이 된다
비트마스킹 : 대소문자 변경
int main(void)
{
char a = 'A';
char mask = 1 << 5;
a = a ^ mask;
printf("%c\n", a); /* A */
a = a ^ mask;
printf("%c\n", a); /* a */
return 0;
}- 아스키 테이블에서 대문자와 소문자의 차이는 32이다.
- 2의 5승에 해당하는 비트에 1이 들어가면 대문자, 0이들어가면 소문자가 된다
- 마스크
0b00010000을 만들어서 XOR연산을 해주면 대소문자 스위칭 가능하다.
비트 플래그(bit flag) : 불리언 여러개 모아두기
int가 32비트고 0 혹은 1로 불리언을 표현할 수 있기 때문에,int하나에boolean32개 모을수 있다.- 프로그램에서 사용하는 옵션들을 한꺼번에 저장할 수 있다. 모든 boolean 으로 나타낼 수 있는 옵션들을 아래와 같이 같은 자료형에 밀어넣을 수 있다.
- 적은수의 비트로 많은 상태를 표현할 수 있다
- 대신 옵션을 수정하려면 비트연산을 통해서 특정 비트 하나만 키고 꺼야된다
- 이런 점 때문에 CPU안에서도 여러 상태들을 저장하려고 비트 플래그 많이 사용한다.
- 산술연산에서 오버플로우나 언더플로우를 기록한다
- 플래그 켜기
flag = 0b01010101; mask = 0b00000010; flag = flag | mask; /* 1 */mask에서 켜져있는 비트가 OR연산 때문에 1로 바뀐다. 나머지 비트는mask에서 0으로 세팅되어 있어서 OR연산이기 때문에 그대로 간다
- 플래그 끄기
flag = 0b01010111; mask = 0b00000010; flag = flag & ~mask; /* 1 */mask를 NOT연산으로 뒤집으면0b11111101이 된다.0b11111101랑flag랑 AND 연산을 하면 타겟비트가 0으로 세팅되어 있기 때문에 무조건 0이 된다- 나머지 비트는 1로 세팅되어 있기 때문에 원래 값으로 들어온다.
- 플래그 끄고 켜기 한번에(토글하기)
flag = 0b01010111; mask = 0b00000010; flag = flag ^ mask; /* 켜기 */ flag = flag ^ mask; /* 끄기 */flag랑mask를 XOR 연산하면,mask에서 나머지 비트가 전부 0으로 세팅되어 있기 때문에 같은건 0, 다른건 1이 되어서 나머지비트는 원본값으로 들어온다.- 타겟비트 1로 세팅되어 있기 때문에 만약 플래그에서 켜져있다면 같은 값이라서 0으로 만들고 꺼져있다면 다른 값이라서 1로 만든다
- 비트플래그 예시
char property_flags = 0; char mask = 0; char ATTACK_NONE = 0; char ATTACK_FIRE = 1; char ATTACK_ICE = 2; char ATTACK_WIND = 3; char ATTACK_ARCANE = 4; char ATTACK_SIZE = 5; mask = (1 << ATTACK_NONE) | (1 << ATTACK_WIND); property_flags = property_flags ^ mask; /* 켜기, 9 */ property_flags = property_flags ^ mask; /* 끄기, 0 */ property_flags = property_flags | mask; /* 켜기, 9 */ property_flags = property_flags & ~mask; /* 끄기, 0 */ - 비트플래그를 쓰면 값을 비교하기도 편하다.
- 예를들어 플래그들을 char에 저장해두고 다른 플래그를 받아왔을 때, 두 플래그가 같은지 비교하는 상황이 있다
- 원래 플래그가 같은지 비교하려면 for문을 돌면서 하나하나 비교해야 한다. 하지만 비트플래그를 사용하면 그냥 변수 와 변수끼리 비교해서 같은지 다른지 판단 가능하기 때문에 반필요없다
데이터 패킹 : 기수(radix) 정렬
배송방법 2개
색상 16개
모양 8개
- 위와같이 데이터가 있다고 할 때, 32비트
int에 위의 데이터를 다 넣을 수 있다.
- 데이터를 낭비 없이 저장하고자 할 때 사용하거나, 기수정렬을 통해서 비교를 최소화 하고자 할 때 사용한다
- 중요도 순으로 packing 변수에 넣으면 컴퓨터에서 리틀엔디언이던 빅엔디언이던 앞에서부터 비교하기 때문에 앞에 자동으로 기준에 따른 정렬이 된다 → 자리수 위가 더크면 무조건 더 큰 값이기 때문
- 정렬 기준을 바꾸고 싶으면 저장하는 순서를 바꾸면 된다
2의 승수 여부를 판단하는 코드
-
반복문을 돌면서 비트 하나하나 확인
int is_two_squared(int number) { int n = number; if (n == 0) { return FALSE; } while (n != 1) { if (n % 2 != 0) { return FALSE; } n = n / 2; } return TRUE; }- O(n)
- 2의 승수라면 2로 몫이 1일 때까지 나눴을 때까지 나머지가 0이 나온다.
- 2의 승수가 아니라면 2로 끝까지 나눴을 때 나머지가 0이 안나온다.
- 한자리씩 오른쪽으로 shift를 해가면서 나누었을 때 나머지가 얼마인지 확인하는 방법이다
-
2진수의 특징을 이용한 방법
int is_two_squared(int number) { int flag = number - 1; if ((flag & number) == 0) { return TRUE; } return FALSE; }- O(1)
- 2진수에서 덧셈 혹은 뺄셈을 하면 비트가 뒤집히는 원리를 이용
number가 2진수라면 뺐을 때 앞에있는 모든 비트가 1로 바껴있을 것이다- 그리고 원본이랑
&연산을 하면 0이된다
Quit talking, Begin doing