[알고리즘] 비트 연산자 정리 (Java 예제 포함)

논리 연산자

논리 연산자는 false(0) 또는 true(1) 값을 다루는 연산자로, 기본적인 연산에는 AND, OR, XOR가 있습니다.

1. AND 연산 (a AND b)

• 정의: a와 b가 모두 1일 때만 1을 반환하며, 나머지 경우는 0을 반환합니다.
• 진리표:

A	B	A AND B
0	0	0
0	1	0
1	0	0
1	1	1

2. OR 연산 (a OR b)

• 정의: a와 b 중 하나라도 1일 때 1을 반환하며, 둘 다 0일 때만 0을 반환합니다.
• 진리표:

A	B	A OR B
0	0	0
0	1	1
1	0	1
1	1	1

3. XOR 연산 (a XOR b)

• 정의: a와 b 중 하나만 1일 때 1을 반환하며, 둘 다 같을 때는 0을 반환합니다.
• 진리표:

A	B	A XOR B
0	0	0
0	1	1
1	0	1
1	1	0

 

---

비트 연산자

비트 연산자는 컴퓨터 내부에서 이루어지는 연산 중 하나로, AND, OR, XOR 연산을 통해 2진수의 각 비트를 비교해 새로운 값을 생성합니다.

비트 연산의 기본 흐름

1. 정수를 2진법으로 변환합니다.
2. 각 자릿수별로 논리 연산을 수행합니다.
3. 논리 연산의 결과를 다시 10진수로 변환합니다.

예시 1: AND 연산

11과 13의 AND 연산을 살펴보겠습니다.

1. 정수를 2진법으로 변환:
   • 11 -> 1011
   • 13 -> 1101
2. 자릿수별로 논리 연산 수행:
   • 1 0 1 1
   • 1 1 0 1
   • ---------
   • 1 0 0 1
   • AND 연산 결과: 1001
3. 2진수를 10진수로 변환:
   • 1001 -> 9
   결과: 11 AND 13 = 9

예시 2: OR 연산

11과 13의 OR 연산을 살펴보겠습니다.

1. 정수를 2진법으로 변환:
   • 11 -> 1011
   • 13 -> 1101
2. 자릿수별로 논리 연산 수행:
   • 1 0 1 1
   • 1 1 0 1
   • ---------
   • 1 1 1 1
   • OR 연산 결과: 1111
3. 2진수를 10진수로 변환:
   • 1111 -> 15
   결과: 11 OR 13 = 15

예시 3: XOR 연산

11과 13의 XOR 연산을 살펴보겠습니다.

1. 정수를 2진법으로 변환:
   • 11 -> 1011
   • 13 -> 1101
2. 자릿수별로 논리 연산 수행:
   • 1 0 1 1
   • 1 1 0 1
   • ---------
   • 0 1 1 0
   • XOR 연산 결과: 0110
3. 2진수를 10진수로 변환:
   • 0110 -> 6
   결과: 11 XOR 13 = 6

 

 

비트 연산 구현

프로그래밍 언어는 기본적으로 비트 연산을 지원하고 있습니다.

사칙 연산과 같이 기호 하나로 연산을 할 수 있습니다.

AND	OR	XOR
&	|	^
11 & 13 = 10	11 | 13 = 15	11 ^ 13 = 5

 

 

 

AND 연산

public class Main {
    public static void main(String[] args){
        
        int a = 11;
        int b = 13;
        
        System.out.println(11 & 13);
    }
}

 

OR 연산

public class Main {
    public static void main(String[] args){
        
        int a = 11;
        int b = 13;
        
        System.out.println(11 | 13);
    }
}

 

XOR 연산

public class Main {
    public static void main(String[] args){
        
        int a = 11;
        int b = 13;
        
        System.out.println(11 ^ 13);
    }
}

 

 

3개 이상의 비트 연산

3개의 정수 a, b, c에 비트 연산을 적용하려면, 두 개의 값을 비트 연산한 다음 그 결과를 남은 값과 다시 비트 연산하면 됩니다. 중요한 점은 어떤 순서로 계산해도 결과가 같다는 것입니다. 예를 들어, a OR (b OR c)와 (a OR b) OR c는 같은 결과를 출력합니다. 이는 AND, OR, XOR 연산 모두에 적용되는 규칙입니다.

 

비트 시프트 연산

비트 시프트 연산은 정수 a를 2진법으로 변환한 후, 비트를 왼쪽 또는 오른쪽으로 b만큼 이동시키는 연산입니다.

시프트 연산은 a << b(왼쪽 시프트)와 a >> b(오른쪽 시프트) 기호를 사용해 표현할 수 있습니다.

• 오른쪽 시프트(>>): 비트를 오른쪽으로 이동시키며, 오른쪽에서 밀려난 값은 버려지고 왼쪽으로는 부호 비트(부호 확장)로 채워집니다. 이는 a를 2^b로 나눈 것과 같습니다.
• 왼쪽 시프트(<<): 비트를 왼쪽으로 이동시키며, 왼쪽으로 밀려난 자리에는 0이 채워집니다. 이는 a를 2^b로 곱한 것과 동일합니다.
  • 주의사항: 왼쪽 시프트 연산 시, 일부 프로그래밍 언어(C, C++ 등)에서는 결과가 자료형의 범위를 초과하면 오버플로가 발생해 값이 잘릴 수 있습니다. 그러나 파이썬과 같은 언어에서는 원하는 만큼 시프트 연산을 수행할 수 있으며, 자동으로 큰 숫자를 처리합니다.

특히, 1 << N은 2^N과 같은 의미를 가지며, 조합 탐색이나 반복 제곱법 같은 알고리즘에서 유용하게 사용됩니다.