흔하진 않지만 사용되면 반드시 쓰임새를 알아야 하는 연산으로, 코딩테스트연습문제에 종종 출제되어 개념을 총 망라하고자 본 포스팅을 한다. (틀리긴 아까우니깐)

🚀 비트연산 완전 정복 (코딩테스트 대비)

1. 필요성

일반적인 operator를 사용한 연산은 CPU가 여러 클럭을 소모하지만, 비트 연산은 CPU가 직접 비트 단위로 처리하므로 휄씬 빠르고 효율적이다.

• 속도 측면 :
  - %2대신 (N & 1) -> 나머지 연산보다 빠름.
  • *2 대신 (n<<1) => 곱셈보다 빠름
• 메모리 효율:
  - boolean 배열 대신 비트마스크 사용 -> 메모리 절약
  • 예시) 1000개의 상태 저장 시, boolean[1000]은 1000byte, 비트마스크는 약 125byte.
    👉 그래서 코테에서 속도 최적화 + 상태 표현 문제에서 자주 등장한다.

2. 비트 연산자 표

3.핵심 활용 패턴

(1) 짝/홀 판별

if((n & 1) ==1) //o홀수
else // 짝수

👉 %2 연산보다 빠름

(2) 특정 비트 확인

if((n&(1<<k))!=0){
	System.out.println(k + "번째 비트는 1")
}

👉 K번째 자리만 1인 마스크

(3) 비트 조작

• 켜기: n|(1<<k)
• 끄기: n & ~(1<<k) (-> k번쨰 자리를 꺼야되니 반전주고 &연산)
• 토글: n ^ (1<<k)

예제 문제들

백준 3460

문제 정의

십진수로 들어온 수를 이진수로 바꾸었을 때 1인 위치를 출력하는 간단한 문제이다.

설계

• 1인 위치를 어떻게 추적(trace) 할것 인가?
  - pos변수를 두어서 다음 loop때 +1
  
• 어떻게 1인지 비교를 할 것인가?
  - &연산자를 통해 1인 위치 식별
  • 식별했으면 위치 출력 + 해당 숫자 오른쪽 shift연산
  • &1 연산 반복
• 출력을 어떻게 할것인가?
  -매 TC때 list에 pos변수를 담는다.
  -새로운 TC시작시 clear()를 해준다.

구현

import java.io.*;
import java.util.*;

class Main{
    static int pos;
    public static void main(String[]args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int TC = Integer.parseInt(br.readLine());
        List<Integer> list = new ArrayList<>();
        
        StringBuilder sb = new StringBuilder();
        
        while(TC-->0){
            pos =0;
            int num = Integer.parseInt(br.readLine());
            while(num>0){
                if((num&1)==1){
                    list.add(pos);
                }
                num>>=1;
                pos++;
            }
             //output
                for(int i=0;i<list.size();i++){
                    sb.append(list.get(i));
                    sb.append(" ");
                }
            list.clear();
                sb.append("\n");
        }//end of TC
        System.out.println(sb);
    }//end of main
}//end of class

6. 정리

비트연산은 빠른 속도 + 적은 메모리가 강점.
%, *, / 대신 &, <<, >>로 치환 가능.
코테 단골 패턴:
홀짝 판별, k번째 비트 확인, on/off/toggle, 부분집합 탐색, 방문 체크등이 있고 계속 update예정