비트연산으로 숫자 범위의 AND 연산

문제: https://leetcode.com/problems/bitwise-and-of-numbers-range/description/?envType=daily-question&envId=2024-07-11

위 문제는 주어진 숫자 n에 대해 n-1을 비트로 표현하는 방법과, n & n-1의 관계를 들여다 보면 힌트를 얻을 수 있다.

1. 자바 비트연산 기본 쓰임 방법

자바에서 비트연산은 다음과 같은 연산자로 수행된다.

• AND 연산 (&): 두 비트가 모두 1일 때만 1, 그렇지 않으면 0.
• OR 연산 (|): 두 비트 중 하나라도 1이면 1, 그렇지 않으면 0.
• XOR 연산 (^): 두 비트가 다를 때만 1, 같으면 0.
• NOT 연산 (~): 모든 비트를 반전 (0은 1로, 1은 0으로).
• 비트 이동 연산 (<<, >>, >>>): 비트를 왼쪽 또는 오른쪽으로 이동.

int a = 5;  // 0101 in binary
int b = 3;  // 0011 in binary

int andResult = a & b; // 0001 in binary, which is 1
int orResult = a | b;  // 0111 in binary, which is 7
int xorResult = a ^ b; // 0110 in binary, which is 6
int notResult = ~a;    // 1010 in binary, which is -6 in two's complement form

System.out.println("AND 연산: " + andResult);
System.out.println("OR 연산: " + orResult);
System.out.println("XOR 연산: " + xorResult);
System.out.println("NOT 연산: " + notResult);

2. n이 주어졌을 때 n-1을 비트로 표현하는 방법

예를 들어, 숫자 n = 6 (0110 in binary)이라면, n-1은 5 (0101 in binary)이다. 이를 비트 단위로 살펴보면, n-1은 n의 마지막 1 인덱스를 기점으로, 이후의 0을 1로 바꾸고, 마지막 1을 0으로 바꿔서 표현된다.

3. n & n-1 관계도에 대해서 표현

n과 n-1의 AND 연산을 수행하면, 동일한 비트는 남고 나머지 비트는 0이 된다는 걸 알 수 있다.

예를 들어, n = 6 (0110 in binary)과 n-1 = 5 (0101 in binary)를 AND 연산하면 아래와 같다.

int n = 6; // 0110 in binary
int nMinus1 = n - 1; // 0101 in binary
int andResult = n & nMinus1; // 0100 in binary, which is 4

System.out.println("n & (n-1): " + Integer.toBinaryString(andResult));

---

위 개념을 토대로 코드는 아래와 같이 작성할 수 있다.

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int cnt = 0;
        while (left != right) {
            left >>=1;
            right >>=1;
            cnt++;
        }
        return left << cnt;
    }
}