🐢 3. Binary Search & Bitwise Operations

💡 추가 지식

• 이진 탐색/이진 검색

• 비트 연산

---

🫧 트리

: 하나의 루트 코드를 가진다

루트 노드는 0개 이상의 자식 노드를 갖고 있다

트리에는 사이클 존재할 수 없다

노드들은 특정 순서로 나열될 수도 있고 그럴 수 없을 수도 있다

각 노드는 어떤 자료형으로도 표현이 가능하다

🫧 이진트리

: 각 노드가 최대 두 개의 자식을 갖는 트리

🫧 이진탐색트리

: “모든 왼쪽 자식들 ≤ n < 모든 오른쪽 자식들” 속성은 모든 노드 n에 대해서 반드시 참이어야 함

모든 노드에 대해서 왼쪽 자식들의 값이 현재 노드 값보다 작거나 같도록 하고, 오른쪽 자식들 값은 현재 노드의 값보다 반드시 커야함

🫧 전이진트리

: 모든 노드의 자식이 없거나 정확히 두 개 있는 경우

자식이 하나만 있는 노드가 존재해서는 안됨

🫧 포화이진트리

: 전 이진 트리이면서 완전 이진 트리인 경우

모든 말단 노드는 같은 높이에 있어야 하며, 마지막 단계에서 노드의 개수가 최대가 되어야 한다

노드의 개수가 정확히 2^K-1 (K는 트리의 높이) 개

🫧 이진 탐색

처음에 N개 크기의 배열에서 단계가 하나씩 지나감에 따라 탐색할 배열의 크기가 반씩 줄어들기 때문

🫧 (정수가 정렬된 배열에서) 이진 탐색

int BSearch(int arr[], int target) {
    int low = 0;
    int high = arr.length - 1;
    int mid;

    while(low <= high) {
        mid = (low + high) / 2;

        if (arr[mid] == target)
            return mid;
        else if (arr[mid] > target)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return -1;
}

🫧 재귀를 사용한 이진 탐색

int BSearchRecursive(int arr[], int target, int low, int high) {
    if (low > high)
        return -1;

    int mid = (low + high) / 2;
    if (arr[mid] == target)
        return mid;
    else if (arr[mid] > target)
        return BSearchRecursive(arr, target, low, mid-1);
    else
        return BSearchRecursive(arr, target, mid+1, high);
}

🫧 비트 조작

: 0s 는 모든 비트가 0 인 값

1s 는 모든 비트가 1 인 값

연산들이 비트 단위로 이루어 진다!

한 비트에서 일어나는 일이 다른 비트에 어떤 영향도 미치지 않는다

🫧 2의 보수와 음수

: 컴퓨터는 일반적으로 정수를 저장할 때 2의 보수 형태로 저장

양수를 표현할 땐 문제 없음

음수를 표현할 땐 그 수의 절댓값에 부호비트를 1로 세팅한 뒤 2의 보수를 취한 형태로 표현함

N비트 숫자에 대한 2의 보수는 2^N 에 대한 보수값과 같음 (N은 부호비트를 뺀 나머지 값을 표현할 때 사용되는 비트의 개수)

2의 보수를 표현하는 다른 방법은 양수로 표현된 2진수를 뒤집은 뒤 1을 더해 주는 것

🫧 산술 우측 시프트 VS 논리 우측 시프트

• 산술 우측 시프트
  • 기본적으로 2로 나눈 결과와 같음
• 논리 우측 시프트
  • 일반적으로 비트를 옮길 때 보이는 것처럼 움직임
  • 비트를 옆으로 옮긴 다음에 최상위 비트에 0을 넣는다 (»> 연산)
  • 비트를 오른쪽으로 옮기긴 하지만 부호비트는 바꾸지 않는다

🫧 기본적인 비트 조작 : 비트값 확인 및 채워넣기

💖 비트값 확인

1 을 i 비트만큼 시프트에서 00010000와 같은 값 만들기

AND 연산을 통해 num 의 i번째 비트를 뺀 나머지 비트를 모두 삭제한 뒤, 이 값을 0과 비교

이 값이 0이 아니라면 i번째 비트는 1, 0이라면 i번째 비트는 0이어야 함

boolean getBit(int num, int i) {
	return ((num % (1 << i)) != );
}

🧡 비트값 채워넣기

1을 i비트만큼 시프트해서 00010000와 같은 값 만들기

OR 연산을 통해 num의 i번째 비트값 바꾸기

i번째를 제외한 나머지 비트들은 0과 OR 연산을 하므로 num에 영향 없음

int setBit(int num, int i) {
    return num | (1 << i);
}

💛 비트값 삭제하기

NOT 연산자를 이용해 00010000 을 11101111 와 같이 만든 뒤 num과 AND 연산

나머지 비트의 값은 변하지 않은 채 i 번째 비트값만 삭제됨

int clearBit(int num, int i) {
	int mask = ~(1 << i);
	return num & mask;
}

: 최상위 비트에서 i번째 비트까지 모두 삭제하려면 (1 « i) 로 i번째 비트를 1로 세팅한 뒤 이 값에서 1을 뺀다

i번째 비트 밑은 모두 1로 세팅되고 그 위로는 모두 0으로 세팅

mask 값과 num을 AND 연산한다면 하위 i개의 비트를 뺀 나머지 비트를 모두 삭제 할 수 있음

int clearBitMSBthroughI(int num, int i) {
	int mask = (1 << i) - 1;
	return num & mask;
}

: i 번째 비트에서 0번째 비트까지 모두 삭제하려면 모든 비트가 1로 세팅된 -1을 왼쪽으로 i + 1만큼 시프트 한다

i번째 비트 위로는 모두 1로 세팅되고 하위 i개 비트는 모두 0으로 세팅됨

int clearBitsIthrough0(int num, int i) {
	int mask = (-1 << (i + 1));
	return num & mask;
}

💚 비트값 바꾸기

i번째 비트값을 v로 바꾸고 싶다면, 우선 11101111와 같은 값을 이용해 i번째 비트값을 삭제해야 함

바꾸고자 하는 값 v를 왼쪽으로 i번 시프트 한다

i번째 비트값은 v가 될 것이고 나머지는 모두 0이 될 것이다

마지막으로 OR 연산을 이용해 i번째 비트값을 v로 바꿔준다

int updateBit(int num, int i, boolean bitIs1) {
	int value - bitIs1 ? 1 : 0;
	int mask = ~(1 << i);
	return (num & mask) | (value << i);
}

🫧 2의 보수, 음수

: 컴퓨터가 정수를 저장할 때는 대부분 2의 보수 형태로 저장

음수를 나타내기 위해서는 기존의 수에서 비트를 뒤집은 다음(1의 보수) 1을 더해주면 되는데, 이는 기존의 수를 2의 보수 표현을 이용해서 음수로 나타낸 것

🫧 산술 시프트, 논리 시프트

: 비트를 1bit씩 밀면서 생긴 빈자리에 새로운 bit를 채워주는 연산

• 산술 시프트 연산
  • 부호비트를 그대로 채워준다
  • 기본적으로 2로 나누거나 곱한 결과와 같다
• 논리 시프트 연산
  • 부호비트에 0을 채워준다
  • 산술적으로는 거의 관계가 없는 것처럼 숫자가 변화

🫧 기본 연산

• NOT [~] : 1이면 0, 0이면 1

• OR [|] : 두 값 중 1이 하나라도 있다면 1, 아니면 0

  합집합 개념과 유사하다.

• XOR [^] : 두 값이 다르면 1, 같으면 0

  실제로는 XOR에 들어가는 값 중 1의 갯수가 홀수개이면 1

• AND [&] : 두 값 모두 1이라면 1, 아니면 0

  교집합 개념과 유사하다.

• SHIFT [<< >>] : 비트 단위로 한 칸씩 미는 연산

🫧 함수 구현

1. Get : 특정 위치의 비트 값을 가져온다.
2. Set : 특정 위치의 비트 값을 세팅한다.
3. Count : 세팅된 비트 값이 몇 개인지 반환한다.
4. Clear : 비트를 0으로 초기화 한다.
5. Toggle : 비트를 반전시킨다.
6. MSB : 최상위 비트를 찾는다.
7. LSB : 최하위 비트를 찾는다.

🫧 비트마스크(BitMask)

: 여러 표현 시 비트를 이용하여 메모리 사용을 줄이고 효율적으로 표현할 수 있다

ex) 집합 {1,2,3,5}가 있을 때 11101로 나타낼 수 있고 저장할 때는 10진수로 29를 저장하면 된다

배열을 이용할 필요없이 정수 하나만으로 저장이 가능하므로 메모리 사용을 줄일 수 있다