1. 비트마스킹

각 비트를 하나의 flag로 활용하기

-> 자료 저장 및 집합 표현 용이

 

생각해보기1

사람 -> 0 ~ 31 사이의 번호가 매겨져 있고, 사람 A의 친구 목록과 B의 친구 목록이 있을 때.

1. A, B 모두와 친구인 사람은? A & B

2. A 또는 B 와 친구인 사람은? A | B

 

친구 목록을 사람 번호로 저장하지 않고, x번째 사람이 내 친구라면,

x번째 비트를 1로 표시하는 방식으로 생각하기

생각해보기2

가장 큰 수임을 판단하는 방법?

예시로, 해당 수 == (1 << 32 - 1) 

: 2의 32제곱 -1

 

---

실습1

새로운 불면증 치료법

package review;

import java.util.Scanner;

public class Solution {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		for (int tc=1; tc<=T; tc++) {
			int n = sc.nextInt();
			
			int cnt = 0; // 횟수 
			int bit = 0; // 비트 마스크 
			
			while(bit != (1<<10) -1) {
				cnt++;
				
				int tmp = cnt * n;
                
                // 각 자리 비트마스킹해주기 
				while (tmp > 0) {
					int digit = tmp % 10;
					bit = bit | (1 << digit);
					tmp /= 10;
				}
			}
			
			System.out.println("#" + tc + " " + n * cnt);
		}
		
	}

}

---

실습2

이진수 표현

import java.util.Scanner;

public class Solution {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		for (int tc=1; tc<=T; tc++) {
			// m의 이진수 표현의 마지막 n비트가 모두 1로 켜져있는지 아닌지 판별 
			int n = sc.nextInt();
			int m = sc.nextInt();
			
			// 마지막 n개의 비트가 모두 1인지 확인할 아이 
			int mask = (1 << n) - 1;
			
			System.out.print("#" + tc + " ");
			
			// 이 둘을 & 연산했을 때 mask랑 같다면 모두 1로 켜져있는 것이므로 
			System.out.println((m & mask) == mask? "ON" : "OFF");
		}
		
	}

}