📖 비트 연산

---

💬 비트(bit)

• 컴퓨터에서 자료를 표현하기 위해 비트 사용
• 1bit = 0 또는 18bits = 1byte

💬 비트 연산자

• 6가지 비트 연산자

비트 연산자	의미	설명	a = 0b1010, b = 0b0100
&	AND	모두 1이면 1	a & b = 0b0000
/	OR	하나만 1이라도 1	a
^	XOR	서로 다르면 1	a ^ b = 0b1110
~	NOT	해당값 반전 1→0, 0→1	~a = 0b0101
<<	왼쪽 Shift	비트 열을 왼쪽으로 이동	a << n = a * (2^n)
>>	오른쪽 Shift	비트열을 오른쪽으로 이동	a >> n = a * (2^-n)

• 비트 연산의 우선순위에 주의
• 비트 연산은 논리 연산보다 우선순위가 높으나 비교 연산보단 낮음
• 비교 연산(==, > 등) > 비트 연산 > 논리 연산( &&, || 등)
• 따라서 아래 코드는 주의 필요

if (x & y == 0)// if (x & (y == 0)) 과 같음

◾ 1 << n

• 2^n의 값을 가짐
• 원소가 n일 경우 모든 부분 집합(Power Set)의 수 의미

◾ i & (1 << j)

• i라는 변수의 j번째 비트 조회
  

public class 비트연산자 {
    
    public static void main(String[] args) {
    	for (int i = -5; i < 6; i++) {
    		System.out.print(i + " ");
    		printBit(i);
    		System.out.println();
    	}
    }
    
    private static void printBit(int n) {
    	for (int i = 7; i >= 0; --i) {
    		// 비트마스크: 원소의 포함 여부 확인
    		// 1일때 1출력
    		if((n & (1 << i)) == (1 << i)) System.out.print(1);
    		else System.out.print(0);
    	}
    }
}

// 출력
-5 11111011
-4 11111100
-3 11111101
-2 11111110
0 00000000
1 00000001
2 00000010
3 00000011
4 00000100
5 00000101

응용 문제 풀이 : SWEA 이진수 표현

• 두 가지 함수를 구현했는데, 속도는 비슷했음

import java.io.*;
import java.util.*;
public class swea이진수표현 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		for(int t = 1; t <= T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
 			int n = Integer.parseInt(st.nextToken());
 			int m = Integer.parseInt(st.nextToken());

// 			bitwise(n, m, t);
 			bitmasking(n, m, t);
 			
		}

	}
	
	private static void bitwise(int n, int m, int t) {
		for(int i = n-1; i >= 0; --i) {
				if((m & (1 << i)) != (1 << i)) { // m의 i번째 비트가 1인가
					System.out.println("#"+t+" OFF");
					return;
				}
			}
			System.out.println("#"+t+" ON");
	}

	private static void bitmasking(int n, int m, int t) {
		int val = (1 << n) - 1; // 2^n(1<<n)에서 -1하면 모두 1인 n개비트
		if((val & m) != val) { // &연산을 통해 나온 값 -> 둘다 같다면 그대로 나옴
			System.out.println("#"+t+" OFF");
			return;
		}
		System.out.println("#"+t+" ON");
	}

}

◾ 비트를 이용한 부분 집합 생성

• 원소 수에 해당하는 N개의 비트를 이용
• n번째 비트 값이 1이면 n번째 원소 포함 의미

public class 비트연산자_부분집합 {

	public static void main(String[] args) {
		char[] data = {'A', 'B', 'C', 'D'};
		printSubSet(data, 4);
	
	
	}

	private static void printSubSet(char[] data, int n) {
		
		for(int i = 0; i < (1<<n); ++i) { // 공집합 포함이라 0부터, n=4니까 2^4 = 16
			System.out.print("( ");
			for(int j = 0; j < n; ++j) {
				if((i & (1<<j)) == (1<<j)) // 1일때 출력
					System.out.print(data[j] + " ");
			}
			System.out.print(")");
			System.out.println();
		}
	}

}

// 출력
( )
( A )
( B )
( A B )
( C )
( A C)
( B C )
( A B C )
( D )
( A D )
( B D )
( A B D )
( C D )
( A C D )
( B C D )
( A B C D )