[Java/알고리즘] 비트 연산자 사용법

▤ 목차

 

1. 비트 관련 메서드 사용법

메서드 (Integer/Long 공통)	설명
bitCount(n)	2진수 표현에서 1의 개수를 반환
highestOneBit(n)	가장 왼쪽(최상위) 1의 위치만 남기고 나머지는 0으로 만든 값을 반환
lowestOneBit(n)	가장 오른쪽(최하위) 1의 위치만 남기고 나머지는 0으로 만든 값을 반환
numberOfLeadingZeros(n)	가장 왼쪽 1의 앞(왼쪽)에 있는 0의 개수를 반환
numberOfTrailingZeros(n)	가장 오른쪽 1의 뒤(오른쪽)에 있는 0의 개수를 반환

1. bitCount - 집합의 크기 구하기

2진수 표현에서 1의 개수를 반환

활용법: 비트 마스킹을 이용해 부분 집합을 표현할 때, 해당 집합에 원소가 몇 개 포함되어 있는지 바로 알 수 있다.

int n = 7; // 이진수: 0111
System.out.println(Integer.bitCount(n)); // 출력: 3

int set = 0b10110; // {1, 2, 4} 원소가 들어있다고 가정 (2진수: 10110)
// 1의 개수를 세어 원소의 개수를 파악
int count = Integer.bitCount(set); 
System.out.println("포함된 원소의 개수: " + count); // 출력: 3

2. highestOneBit - 숫자보다 작은 가장 큰 2의 거듭제곱 찾기

가장 왼쪽(최상위) 1의 위치만 남기고 나머지는 0으로 만든 값을 반환

활용법: 숫자보다 작은 가장 큰 2의 거듭제곱 값을 구할 수 있다.

int n = 25; // 2진수: 11001

// 최상위 비트 하나만 남기고 나머지를 0으로 만듦
int powerOfTwo = Integer.highestOneBit(n);

System.out.println("25 이하의 가장 큰 2의 거듭제곱: " + powerOfTwo); // 출력: 16 (10000)

3. lowestOneBit - 펜윅 트리(Fenwick Tree) 구현

가장 오른쪽(최하위) 1의 위치만 남기고 나머지는 0으로 만든 값을 반환

활용법: 비트 집합에서 가장 낮은 순위의 원소를 하나씩 꺼내어 처리할 때 사용
펜윅 트리(Fenwick Tree): 알고리즘 문제 풀이 시 구간 합을 빠르게 구하는 자료구조인 '펜윅 트리'에서 인덱스를 업데이트하는 핵심 로직(i & -i)과 동일한 역할

int i = 6; // 2진수: 110
int lob = Integer.lowestOneBit(i);

System.out.println("최하위 비트 값: " + lob); // 출력: 2 (2진수: 010)

4. numberOfTrailingZeros - 가장 낮은 자리의 비트 위치 찾기

가장 오른쪽 1의 뒤(오른쪽)에 있는 0의 개수를 반환

활용법: 가장 오른쪽에 있는 1이 몇 번째 인덱스에 있는지 찾을 때 유용
숫자가 2로 몇 번 나누어 떨어지는지 확인할 때 사용

 

int n = 12; // 2진수: 1100

// 뒤에서부터 처음 1이 나올 때까지의 0의 개수 = 최하위 비트의 인덱스
int index = Integer.numberOfTrailingZeros(n);

System.out.println("가장 낮은 1의 위치: " + index); // 출력: 2 (0의 개수 2개)

2. 비트 이동(Shift) 연산자 사용법

연산자	이름	설명	활용
<<	Left Shift	비트를 왼쪽으로 이동	빈 자리는 0으로 채워지며, 한 칸 이동할 때마다 값에 2를 곱한 결과
>>	Right Shift	비트를 오른쪽으로 이동	빈 자리를 **부호 비트(최상위 비트)**로 채움 (양수는 0, 음수는 1)
>>>	Unsigned Right Shift	비트를 오른쪽으로 이동	부호와 상관없이 빈 자리를 무조건 **0**으로 채움

1. Left Shift  <<

비트를 왼쪽으로 밀고, 오른쪽 빈 공간은 0으로 채운다.

활용법: x << n는 한 칸 이동할 때마다 값에 2를 곱한 결과

int a = 5; // 이진수: 00101 
int result = a << 2; // 왼쪽으로 2칸 이동

System.out.println("결과값: " + result); // 20
System.out.println("이진수: " + Integer.toBinaryString(result)); // 10100

2. Right Shift >>

비트를 오른쪽으로 밀고, **왼쪽 빈 공간을 원래 숫자의 부호(가장 왼쪽 비트)**로 채운다.

양수면 0으로, 음수면 1로 채워져서 숫자의 부호가 바뀌지 않는다.

활용법: 한 칸 이동할 때마다 2로 나누는 효과

int a = 20; // 10100
int b = -20; // 111...101100 (2의 보수 표현)

System.out.println(a >> 2); // 20 / 4 = 5
System.out.println(b >> 2); // -20 / 4 = -5 (부호가 유지됨)

3. Unsigned Right Shift >>>

비트를 오른쪽으로 밀되, 부호에 상관없이 무조건 왼쪽 빈 공간을 0으로 채운다.

양수일 때는 >>와 같지만, 음수일 때는 부호 비트가 0으로 바뀌면서 아주 큰 양수로 변하게 된다.

int a = 20; // 10100
int b = -20; // 111...101100 (2의 보수 표현)

System.out.println(a >>> 2); // 5 (양수일 땐 >>와 동일)
System.out.println(b >>> 2); // 1073741819 (아주 큰 양수로 변함)

3. 비트 논리(Logical) 연산자 사용법

연산자	논리	설명	활용
&	AND	두 비트 모두 1일 경우에만 연산 결과가 1	특정 비트를 추출하거나 0으로 만들 때 (Masking)
|	OR	두 비트 중 하나만 1일 경우에만 연산결과가 1	두 비트 중 하나라도 1이면 1을 반환
^	XOR	두 비트가 서로 다를 때만 1을 반환	두 값이 같은지 비교하거나, 비트를 반전시킬 때
~	NOT	비트를 반전시킵니다. (0→1, 1→0)	보수 연산을 하거나 전체 비트를 뒤집을 때

1. & (AND) 연산자

두 비트 모두 1일 경우에만 연산 결과가 1

활용법: 짝수/홀수 판별 1과 AND 연산을 하면 마지막 비트만 남는다.

int n = 15; // 1111
boolean isOdd = (n & 1) == 1; // 결과: true

2. | (OR) 연산자

두 비트 중 하나만 1일 경우에만 연산결과가 1

활용법: 비트들을 하나로 합칠 수 있다.

int READ = 1, WRITE = 2, EXEC = 4;
int userAuth = READ | WRITE; // 001 | 010 = 011 (읽기+쓰기 권한)

3. ^ (XOR) 연산자

두 비트가 서로 다를 때만 1을 반환

활용법: 간단한 대칭키 같은 값으로 두 번 XOR하면 원래 숫자로 돌아오는 성질을 이용 (암호화/복호화)

int data = 123;
int key = 777;
int encrypted = data ^ key; // 암호화
int decrypted = encrypted ^ key; // 복호화 (다시 123)

활용법: 유일한 숫자 찾기 배열에서 두 번씩 등장하는 숫자들 중 혼자만 한 번 등장하는 숫자를 찾을 때 씁니다.(중복 제거)
XOR은 같은 수끼리 만나면 0이 되기 때문

int unique = 1 ^ 2 ^ 3 ^ 2 ^ 1; // 결과: 3 (나머지는 서로 지워짐)

4. 비트 연산자 활용예시

1. n번째 비트 켜기

int bitset = 0; // 비어있는 집합

// 1. n번째 비트 켜기 (Set) : 1 << n
int n = 3;
bitset |= (1 << n); // 3번 비트를 1로 만듦 (1000)
System.out.println("3번 비트 켠 후: " + Integer.toBinaryString(bitset));

2. n번째 비트 확인

int bitset = 0; // 비어있는 집합

// 2. n번째 비트 확인 (Check) : bitset & (1 << n)
boolean isSet = (bitset & (1 << n)) != 0;
System.out.println(n + "번 비트가 켜져 있나요? " + isSet);

3. n번째 비트 끄기

int bitset = 0; // 비어있는 집합

// 3. n번째 비트 끄기 (Clear) : bitset & ~(1 << n)
bitset &= ~(1 << n);
System.out.println("3번 비트 끈 후: " + Integer.toBinaryString(bitset));

4. 다크모드 설정 

public class UserSettings {
    // 1. 각 옵션을 2의 거듭제곱(비트 위치)으로 정의
    static final int SETTING_NOTI  = 1 << 0; // 0001 (알림)
    static final int SETTING_DARK  = 1 << 1; // 0010 (다크모드)
    static final int SETTING_AUTO  = 1 << 2; // 0100 (자동로그인)

    public static void main(String[] args) {
        int myConfig = 0; // 초기값 (모두 OFF)

        // 설정 켜기 (OR 연산: |)
        myConfig |= SETTING_NOTI; // 알림 ON
        myConfig |= SETTING_DARK; // 다크모드 ON (결과: 0011)

        // 특정 설정 확인 (AND 연산: &)
        if ((myConfig & SETTING_DARK) != 0) {
            System.out.println("다크 모드가 적용 중입니다.");
        }

        // 설정 반전 (XOR 연산: ^) - 누를 때마다 켜졌다 꺼졌다 하는 스위치
        myConfig ^= SETTING_NOTI; // 알림 OFF로 바뀜 (0011 ^ 0001 = 0010)

        // 설정 끄기 (AND + NOT 연산: & ~) - 무조건 OFF
        myConfig &= ~SETTING_DARK; // 다크모드 무조건 OFF (0010 & ~0010 = 0000)
    }
}

5. 고속 알고리즘: 부분집합(Subset) 구하기  

public class SubsetGenerator {
    public static void main(String[] args) {
        String[] items = {"A", "B", "C"};
        int n = items.length;

        // 1 << n 은 2^3 = 8 (0부터 7까지 반복)
        for (int i = 0; i < (1 << n); i++) {
            System.out.print("{ ");
            for (int j = 0; j < n; j++) {
                // i의 j번째 비트가 1인지 확인
                if ((i & (1 << j)) != 0) {
                    System.out.print(items[j] + " ");
                }
            }
            System.out.println("}");
        }
    }
}
/* 출력 결과:
{ }
{ A }
{ B }
{ A B }
{ C }
{ A C }
{ B C }
{ A B C }
*/

6. 프로그래머스  풀이 - 2개 이하로 다른 비트

https://school.programmers.co.kr/learn/courses/30/lessons/77885

프로그래머스

풀이방법

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
        
        for(int i =0; i<numbers.length; i++){
          long n = numbers[i];    
                
          if(n % 2 ==0){
              answer[i] = n + 1;
          }else{
              //처음으로 0이 나오는 비트 위치 찾기 (~x를 통해 1로 반전시킨 뒤 가장 낮은 비트 찾기)
              // 2가지 방법
              long firstZeroBit = Long.lowestOneBit(~n);
              // long firstZero = (~n) & (n+1); 
                 
              //0인 비트를 1로 바꿔주고, 이전 비트를 0으로 바꿔준다
              // 2가지 방법
              answer[i] = (n | firstZeroBit) & ~(firstZeroBit >> 1);
              // answer[i] = n + firstZero - (firstZero >> 1);
              
          }
            
        }
        return answer;
    }
}

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.