[자.알.인] CH19. 비트 조작

1. 비트 조작

비트(bit)는 Binary Digit을 줄인 말로 데이터를 나타내는 최소 단위입니다. 0과 1 두 개의 값만을 가질 수 있습니다. 8bit가 모여 1Byte가 되며 이 후 단위들은 킬로, 메가, 기가 등 컴퓨터 저장 용량이나 RAM 용량 등에서 보던 익숙한 단위가 보이게 됩니다.

https://howtolivelikehuman.tistory.com/33 출처

 

2. 부울 연산자

가장 기본적인 부울 연산(Boolean Operation)에 대해서 설명드리겠습니다.

 

논리 회로 부울 연산자

 

• AND
• OR
• NOT
• NAND
• NOR
• XOR
• XNOR

등 으로 소개가 되어있습니다. 저 중에 0과 1의 숫자로 이용하는 '비트 연산자'에서 일부 사용이 가능합니다.

 

3. 비트 연산자

위의 부울 연산자에서 사용되는 것은 4가지의 연산이 있습니다.

1. AND(&)
   • 두 자릿수 중 하나라도 0이 있으면 0, 없으면 1로 하는 연산
2. OR(|)
   • 두 자릿수 중 하나라도 1이 있으면 1, 없으면 0으로 하는 연산
3. NOT(~)
   • 각 자릿수의 값을 반대로 바꾸는 연산
4. XOR(^)
   • 두 자릿수의 값이 다르면 1, 같으면 0으로 하는 연산

여기서 시프트 연산이라는 것도 추가가 됩니다.

1. 산술 시프트: 부호 비트를 유지하며 나머지 비트를 이동
   • >> 'n': n칸만큼 오른쪽으로 이동
   • << 'n': n칸만큼 왼쪽으로 이동
2. 논리 시프트: 부호 비트를 포함하여 나머지 비트를 이동
   • >>> 'n': n칸씩 오른쪽으로 회전
   • <<< 'n': n칸씩 왼쪽으로 회전

// @ <<
System.out.println(3 << 1);
System.out.println(-3 << 1);
System.out.println(3 << 2);
System.out.println(-3 << 2);
System.out.println();

// @ >>
System.out.println(5 >> 1);
System.out.println(-5 >> 1);
System.out.println(5 >> 2);
System.out.println();

//논리 시프트(>>>)
System.out.println(3 >>> 1);
System.out.println(-3 >>> 31);

 

 

4. 2의 보수

2의 보수(Two's Complement), 컴퓨터가 숫자로 표현하기 위한 여러 표기법 중 하나입니다. 이 중 음수를 효과적으로 표현할 수 있습니다.

 

예제로 4비트의 비트로 말씀드리겠습니다.

 

EX) 0000 ~ 1111

 

해당 예제에서는 기본적으로 2진수를 알고 있다면, 0에서 15까지의 숫자입니다. 여기서 2의 보수로 정리를 한다면

 

맨 처음 숫자가 0이면 양수, 1이면 음수 형태를 띄우게 됩니다. 이 후 나머지 3개의 비트로 2진수의 값을 지니게 됩니다.

 

0000: +0 => 0

1000: -0 => -8

0001: +1 => 1

1001: -1 => -1

...

로 -8부터 7까지의 범위를 가지게 됩니다.

 

5. 코드 풀이

이번 문제에서 간단하고 설명하기 쉬운 문제에 대해서 말씀드리겠습니다.

 

76번 문제의 '싱글 넘버'

 

문제의 조건은 숫자 배열 안에 단 한개를 제외한 나머지의 값은 2개씩 들어있다는 조건입니다.

 

private static int singleNumber(int[] nums) {

    int result = 0;

    for (int num : nums) {
        result = result ^ num;
    }

    return result;
}

 

이 때 0을 주어 들어오는 배열 값들을 for문으로 XOR 연산을 시켰습니다. 이 때 XOR 연산의 특징은 '두 자릿수의 값이 다르면 1, 같으면 0으로 하는 연산'으로 2개씩 들어있는 숫자가 전부 0으로 바뀌게 됩니다. 그러므로 단 한개만 들어있는 숫자가 표현이 되기에 for문의 시간 복잡도인 O(n)의 값을 지니게 됩니다.