비트 마스크(Bit Mask)

1. Problem

- 비트 마스크 기법을 이용해 여러 연산을 수행해보자.

1) 비트 마스크 기법은 비트 연산자(&, | 등)를 활용해서 정수(int)의 이진 비트를 처리해 메모리를 적게 사용하면서 프로그램의 속도를 높이는 기법이다.

2) 모든 문제에 사용할 수 있는 것은 아니지만, 사용할 수 있다면 소스코드가 직관적으로 바뀌게 된다.

- 예를 들어, 출석을 1, 결석을 0으로 표시한다고 했을 때 한 반에 32명인데 3번과 6번이 출석이라면

  00000000 00000000 00000000 00100100 (2) = 36으로 표현할 수 있다.

3) 정수를 2진 비트로 표현할 때 음수를 표현하는 것은 2의 보수를 이용한다.

// 8비트로 예를 들자면
 30  = 0001 1110
-30 -> 1110 0001 + 1 = 1110 0010

 

2. Example

1) 모든 비트 출력하기

int a = 36; // a는 비트 마스크가 된 정수
show(a); // 00000000 00000000 00000000 00100100
         // 3번과 6번에 마스킹이 된 상태
// show() 연산 과정
// 6번째 비트를 확인한다고 하면 i = 6-1 = 5
1      = 00000000 00000000 00000000 00000001
1 << 5 = 00000000 00000000 00000000 00100000
a      = 00000000 00000000 00000000 00100100
a & i  = 00000000 00000000 00000000 00100000 = 32 -> 1 출력

- a를 2진수로 변환했을 때 가장 왼쪽 비트부터 오른쪽으로 가면서 1개씩 확인한다. 출력 결과가 맨 앞자리부터 나와야 하기 때문에 확인도 맨 앞부터 확인한다.

-  i번 비트를 확인하는 방법은 1에 대해 왼쪽으로 i-1번 이동하는 비트 연산을 수행한 후 비트 and(&) 연산을 하는 것이다.

- 연산 결과가 0보다 크면 i번 비트의 값이 1이라는 것을 의미하므로 그때는 1을 출력하고, 연산 결과가 0이면 0을 출력한다.

 

2) 모든 원소를 삭제하기

a = reset(a); // 00000000 00000000 00000000 00000000
              // a에 0을 대입하면 모든 마스킹을 삭제

 

3) 모든 원소를 포함시키기

a = all(a); // 11111111 11111111 11111111 11111111
            // a에 -1을 대입하면 2의 보수 계산에 의해 모두 마스킹

 

4) 특정 원소를 삭제하기

int a = 36; // 3번과 6번에 마스킹이 된 상태
// 3번 삭제
a = delete(a, 3); // 00000000 00000000 00000000 00100000
                  // a = 32
// delete(a, 3) 연산과정
~(1<<3-1) = ~(00000000 00000000 00000000 00000100)
            = 11111111 11111111 11111111 11111011
a = 36      = 00000000 00000000 00000000 00100100
a & ~(1<<2) = 00000000 00000000 00000000 00100000

- i번 비트를 삭제하는 방법은 1에 대해 왼쪽으로 i-1번 이동하는 비트 연산을 수행한 후 비트 not(~)을 적용한 다음 a와 비트 and(&) 연산을 하는 것이다.

 

5) 특정 원소를 포함시키기

// 3번 추가
a = add(a, 3); // 00000000 00000000 00000000 00100100
               // a = 36
// add(a, 3) 연산과정
a = 32     = 00000000 00000000 00000000 00100000
1<<3-1     = 00000000 00000000 00000000 00000100
a & (1<<2) = 00000000 00000000 00000000 00100100

- i번 비트를 포함시키는 방법은 1에 대해 왼쪽으로 i-1번 이동하는 비트 연산을 수행한 후 a와 비트 or(|) 연산을 하는 것이다.

 

6) 특정 원소 포함 여부 확인하기

// a는 3번과 6번에 마스킹이 된 상태
contains(a, 4); // false
contains(a, 6); // true
// contains(a, 4) 연산과정
a = 36   = 00000000 00000000 00000000 00100100
1<<4-1   = 00000000 00000000 00000000 00001000
a&(1<<3) = 00000000 00000000 00000000 00000000 = 0 -> false
// contains(a, 6) 연산과정
a = 36   = 00000000 00000000 00000000 00100100
1<<6-1   = 00000000 00000000 00000000 00100000
a&(1<<5) = 00000000 00000000 00000000 00100000 = 32 -> true

- i번이 포함되어 있는지 확인하는 방법은 1에 대해 왼쪽으로 i-1번 이동하는 비트 연산을 수행한 후 a와 비트 and(&) 연산을 하는 것이다.

- 그 값이 0보다 크면 해당 비트가 1이라는 뜻이므로 true, 0이라면 해당 비트가 0이라는 뜻이므로 false를 반환한다.

 

7) 특정 원소 토글하기

// a는 3번과 6번에 마스킹이 된 상태
a = toggle(a, 8); // 00000000 00000000 00000000 10100100
                  // a = 164
// a는 3번, 6번, 8번에 마스킹이 된 상태
a = toggle(a, 3); // 00000000 00000000 00000000 10100000
                  // a = 160
// toggle(a, 8) 연산과정
a = 36   = 00000000 00000000 00000000 00100100
1<<8-1   = 00000000 00000000 00000000 10000000
a^(1<<1) = 00000000 00000000 00000000 10100100
// toggle(a, 3) 연산과정
a = 164  = 00000000 00000000 00000000 10100100
1<<3-1   = 00000000 00000000 00000000 00000100
a^(1<<2) = 00000000 00000000 00000000 10100000

- i번을 토글하는 방법은 1에 대해 왼쪽으로 i-1번 이동하는 비트 연산을 수행한 후 a와 비트 xor(^) 연산을 하는 것이다.

- xor의 연산결과는 두 값이 같으면 0, 다르면 1이 나온다.

 

8) 마지막 원소 구하기

getLast(a); // a와 -a의 비트 연산 결과 = 32
            // 2^(i-1) = 32 = 2^5
            // 따라서 i=6이고, 6번이 마지막 원소가 된다.
// getLast(a) 연산과정
a = 160                                          = 00000000 00000000 00000000 10100000
-a    -> 11111111 11111111 11111111 01011111 + 1 = 11111111 11111111 11111111 01100000
a & -a                                           = 00000000 00000000 00000000 00100000 -> 6

- a와 -a를 비트 and(&) 연산을 하게 되면 가장 마지막 1의 10진수 값 N이 반환된다. 따라서 해당 비트의 번호 i는 N에 log2를 취한 후 1을 뺀 값이 된다.

 

9) 마지막 원소 삭제하기

// a는 6번, 8번이 마스킹된 상태
a = deleteLast(a); // 00000000 00000000 00000000 10000000
                   // 6번 삭제 후 a = 128
// deleteLast(a) 연산과정
a = 160 = 00000000 00000000 00000000 10100000
a-1     = 00000000 00000000 00000000 10011111
a&(a-1) = 00000000 00000000 00000000 10000000

- a와 a-1을 비트 and(&)를 하면 가장 마지막 1이 없어진다.

- a에서 1을 빼면 가장 마지막 1부터 받아 내림을 하게 되어 이후 모든 비트가 토글된다. 따라서 이를 a와 비트 and 연산을 하게 되면 가장 마지막 1이 0이 되는 것이다.

 

5. Code

int a = 36;

/* 1) 모든 비트 출력하기 */                           static void show(int a) {
show(a); /* 00000000000000000000000000100100 */         for(int i=32 ; i>=1 ; i--)
                                                            System.out.print((a&(1<<i-1))>0?1:0);
                                                        System.out.println();
                                                    }

/* 2) 모든 원소 삭제하기 */                           static int reset(int a) {
a = reset(a);                                           return 0;
show(a); /* 00000000000000000000000000000000 */     }

/* 3) 모든 원소 포함시키기 */                        static int all(int a) {
a = all(a);                                            return -1;
how(a); /* 01111111111111111111111111111111 */     }

/* 4) 특정 원소 삭제하기 */                          static int delete(int a, int i) {
a = 36; /* 3번, 6번이 마스킹이 된 상태 */                a &= ~(1<<i-1);
a = delete(a, 3); /* 3번 원소 삭제. a = 32 */           return a;
show(a); /* 00000000000000000000000000100000 */     }

/* 5) 특정 원소 포함시키기 */                        static int add(int a, int i) {
a = add(a, 3); /* 3번 원소 포함. a = 36 */              a |= 1<<i-1;
show(a); /* 00000000000000000000000000100100 */        return a;
                                                   }

/* 6) 특정 원소 포함 여부 확인하기 */                 static boolean contains(int a, int i) {
/* a는 3번, 6번이 마스킹이 된 상태	*/                     return (a&(1<<i-1))>0;
System.out.println(contains(a, 4)); /* false */    }
System.out.println(contains(a, 6)); // true

/* 7) 특정 원소 토글하기 */                          static int toggle(int a, int i) {
/* a는 3번, 6번이 마스킹이 된 상태	*/                     a ^= 1<<i-1;
a = toggle(a, 8); /* 8번 포함. a = 164 */               return a;
show(a); /* 00000000000000000000000010100100 */    }
// a는 3번, 6번, 8번이 마스킹이 된 상태
a = toggle(a, 3); // 3번 삭제. a = 160
show(a); // 00000000000000000000000010100000

/* 8) 마지막 원소 구하기 */                          static int getLast(int a) {
/* a는 6번, 8번이 마스킹이 된 상태 */                     int n = a&-a;
System.out.println(getLast(a)); /* 6 */                 return (int)(Math.log10(n)/Math.log10(2)) + 1;
                                                   }

/* 9) 마지막 원소 삭제하기 */                        static int deleteLast(int a) {
a = deleteLast(a); /* 6번 삭제. a = 128 */              return a&(a-1);
show(a); /* 00000000000000000000000010000000 */    }