비트마스크란?

Havi·2021년 9월 27일
0

비트

비트란 이진 숫자(binary digit)를 뜻하는 말로, 컴퓨터에서 사용되는 데이터의 최소단위이다.
0 혹은 1을 가질 수 있으며, true/false 혹은 on/off 상태 를 나타낼 수 있다.
컴퓨터는 이 두가지 숫자만으로 표현하는 이진법을 사용한다.

비트마스크

비트마스크(BitMask)란 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 기법이다.

비트 마스크의 장점

  1. 수행 시간이 빠르다.
  • 비트마스크는 bit연산이므로 O(1)로 동작한다.
  1. 코드가 짧다.
  • 다양한 집합 연산을 한줄로 표현하여 간결한 코드 작성이 가능하다.
  1. 메모리 사용량이 적다.
  • 비트 마스크를 사용하는 가장 큰 이유이다.
  • 10개의 bit는 2^10가지의 경우를 나타낼 수 있다. 이처럼 많은 수를 표현하기에 효율적이며, 많은 데이터를 미리 계산하여 저장해둘 수 있다.(DP에서 유용)

비트 연산자

  1. AND 연산
    a bit와 b bit 모두 켜져있는 경우 (ex: c = a & b)

  2. OR 연산
    a bit와 b bit 둘 중 하나라도 켜져있는 경우 (ex: c = a | b)

  3. XOR 연산
    a bit와 b bit 둘 중 하나만 켜져있는 경우 (ex: c = a ^ b)

  4. NOT 연산
    bit중에서 켜져있는 비트는 끄고, 꺼져있는 비트는 킨다. (ex: c = ~a)

  5. SHIFT 연산
    비트들을 왼쪽 혹은 오른쪽으로 원하는 만큼 움직인다.
    빈자리는 0으로 채워진다.
    1101을 오른쪽으로 1bit shift하면 0110이 된다. (ex: c = a>>1 )

profile
iOS Developer

0개의 댓글