비트연산 활용

모두들 비트연산은 그냥 안배우고 넘어가셨겟죠.(그렇다고 말해줘요)

비트연산은 &, |, ^, ~, <<, >>가 있습니다.

식상한 설명

&	AND	둘 다 1이면 1
|	OR	하나만 1이면 1
^	XOR	다르면 1
~	NOT	1이면 0, 0이면 1
<<	LEFT SHIFT	왼쪽으로 비트이동
>>	RIGHT SHIFT	오른쪽으로 비트이동

비트란 말이 생소하다면.

32비트 정수형 변수라고 불리는 int는 32자리의 2진수로 구성되어있습니다.

4102100 = 11 1110 1001 0111 1101 0100

비트연산은 이진수에대한 숫자놀음과 같습니다.

&

• 원하는 비트만 변경

만약 32비트에서 4번째와 16번째 비트만 1로 만들고 싶을 땐

a=0x10010000

0x는 16진수를 나타내고 0x10010000는 2진수로 0001 0000 0000 0001 0000 0000 0000 0000입니다.

4번째 비트랑 16번째 비트만 1이죠.

예)

   0011 1100 0011 1011 1001 1000 0001 1111

& 0001 0000 0000 0001 0000 0000 0000 0000

= 0001 0000 0000 0001 0000 0000 0000 0000

• 공통부분 구하기

이건 약간 제한된 경우지만 에라토스테네스의 체를 이용하여 소수를 구할 때 처럼 배열에 1과 0만 넣어 참, 거짓을 구별할 때 if문을 사용하는 것 보다 빠르게 작업을 해냅니다.

//a, b, c후보숫자 배열의 교집합부분을 구함 void samesame(int *a, int *b, int *c) { int i; for(i=1; i<=9;i++) a[i]=a[i]&b[i]&c[i]; //셋 다 1이면 1저장, 하나라도 0이면 0저장 }

이 함수는 C언어 스도쿠 자동풀이 프로그램에서 아주 자알 사용되었습니다.

|

• 원하는 비트를 1로 바꾸고 싶을 때

&연신처럼 사용하세요.

^

• 값 교환 (이건 느리다고 하네요.)

a^=b;

b^=a;

a^=b;

이 세 번의동작을 하면 a와 b의 값이 바뀝니다.

#include <stdio.h> void swap(int *a, int *b) { *a^=*b; *b^=*a; *a^=*b; } int main() { int a,b; scanf("%d %d", &a, &b); swap(&a,&b); printf("%d %d",a,b); }

0으로 초기화할 때

a^=a 를 하면 a가 0으로 초기화됩니다. (쓸 일이 없어요.)

~

• 정수형 변수의 최댓값을 구하고 싶을 때

#include <stdio.h> int main() { int a=1; char b=1; __int64 c=1; a<<=31; b<<=7; printf("%d %d",~a, ~b); }

가장 오른쪽의 비트를 가장 왼쪽으로 이동시키고 ~연산으로 가장 왼쪽비트만 빼고 전부 1로 만들어 최대값을 출력합니다. (부호있는 변수는 가장 왼쪽의 비트는 음수를 나타낼 때 사용됩니다.)

<<, >>

• << 2ⁿ으로 곱할 때 (빨라요.)
• >> 2ⁿ으로 나눌 때

10진수를 예로 설명한다면

00000020(이십)을 왼쪽으로 2칸 옮기면 00002000(이천)이 되죠. 10진수에선 10ⁿ만큼 곱해지거나 나누어집니다.

21로 계속 곱하는 소스 

  #include <stdio.h> int main() { int a=1, ctr; for(ctr=0; ctr<31; ctr++) { printf("%d\n", a); a<<=1; } }