비트마스크는 정수의 이진수 표현을 자료구조로 쓰는 기법이다.

* 비트마스크

정수의 이진수 표현을 자료구조로 쓰는 기법

장점

빠른 수행시간

간결한 코드

적은 메모리

연관배열을 배열로 대체

비트 연산자

* AND(&)

해당비트가 모두 켜져있을 때만 켜진다.

    1 1 0 0 (12)
    1 0 1 0 (10)
AND -----------
    1 0 0 0 (8)

* OR(|)

해당비트중 하나만 켜져있으면 켜진다.

    1 1 0 0 (12)
    1 0 1 0 (10)
OR  -----------
    1 1 1 0 (14)

* XOR(^)

하나는 켜져있고 하나는 꺼져있을 때만 켜진다.

    1 1 0 0 (12)
    1 0 1 0 (10)
XOR -----------
    0 1 1 0 (6)

* NOT(~)

켜져 있는 비트는 끄고, 꺼져 있는 비트는 켠다.

    ~12 = -13 (부호있는 정수)

* SHIFT(<<,>>,>>>)

우측 쉬프트 연산(>>)은 좌측의 정수를 우측에 입력한 정수 만큼 bit 를 이동시킨다.
좌측 쉬프트 연산(<<)은 남은 부분을 0으로 채운다.
(자바) 우측 쉬프트 연산(>>>) 우측으로 이동 후 나머지는 0으로 채운다.
```
12(1 1 0 0) >> 2 = 3(0 0 1 1)
12(1 1 0 0) << 2 = 48(1 1 0 0 0 0)
```
* 연산자 활용 예제

1. AND(&)와 시프트(<<) 연산을 이용한 십진수에서 이진수 변환 및 출력
```
public static void printBinary(int num) {
      for(int i=31;i>=0;i--) {
          int bit = (num & 1<<i);
          if(bit>0)
              System.out.print(1);
          else 
              System.out.print(0);
      }
  }
```
2. 비트마스킹을 활용한 에라토스테네스의 체 - 기본 원리
```
Arrays.fill(sieve, (char)255);
```
unsigned char는 부호없는 8비트형식(자바에선 2바이트, 즉 16비트이다)으로 0~255까지의 표현범위를 가진다. 아래의 sieve배열은 에라테네토스테네스의체를 통해 인덱스의 수가 소수인지 아닌지 체크를 한 결과를 담고있다.
k가 소수인지 아닌지 확인 방법
```
public static boolean isPrime(int k) {
    return (sieve[k>>>3] & (1<<(k&7))) == 0 ? false : true;
}
```
1. 인덱스 찾기

시프트 연산(k>>>3)으로 숫자 k의 인덱스를 구한다. k&7은 2와 같고 1<<2은 1을 좌측으로 2번 시프트 한것이므로 00000100가 된다. 2. 소수 확인

AND(&) 연산자를 사용했을때 소수라면 자기자신이 나온다. - k가 소수가 아님을 체크하는 방법
```
public static void setComposite(int k) {
    sieve[k>>>3] &= ~(1 << (k&7));
}
```

소수아님기록 전체코드

public class 에라토스테네스의체 {
    public static int LAST_NUM = 20;
    public static char sieve[] = new char[(LAST_NUM + 7)/8 + 1];
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        //에라토스테네스의 체 구하기
        eratosthenes();
        //소수 출력
        for(int i=0;i<=LAST_NUM;i++)
            if(isPrime(i))
                System.out.print(i+" ");
    }
    //k가 소수인지 아닌지 반환
    public static boolean isPrime(int k) {
        return (sieve[k>>>3] & (1<<(k&7))) == 0 ? false : true;
    }
    //k가 소수가 아님을 표시해둠
    public static void setComposite(int k) {
        sieve[k>>>3] &= ~(1 << (k&7));
    }
    public static void eratosthenes() {
        //모든비트를 1로 초기화
        Arrays.fill(sieve, (char)255);
        setComposite(0);
        setComposite(1);
        for(int i=2;i<=Math.sqrt(LAST_NUM);i++)
            if(isPrime(i))
                //i의 배수(j)에 대해 isPrime(j)=false로 둔다.
                for(int j=i*i;j<=LAST_NUM;j+=i)
                    setComposite(j);
    }
}

연산자 우선순위

최우선연산자 ( ., [], () )
단항연산자 ( ++,–,!,~,+/- : 부정, bit변환>부호>증감)
산술연산자 ( *,/,%,+,-,shift) < 시프트연산자 ( >>,<<,>>> ) >
비교연산자 ( >,<,>=,<=,==,!= )
비트연산자 ( &,|,,~ )
논리연산자 (&& , || , !)
삼항연산자 (조건식) ? :
대입연산자 =,*=,/=,%=,+=,-=

비트마스크(BitMask)