비트마스킹 (Bit Manipulation)

비트마스킹 (Bit Manipulation) 설명:

비트마스킹은 이진 숫자 표현에서의 개별 비트(bit)를 조작하는 기법을 의미합니다. 컴퓨터는 모든 정보를 비트로 표현하므로 비트 연산을 이용하면 특정 연산들을 매우 빠르게 수행할 수 있습니다. 비트마스킹은 주로 공간 효율성이나 연산 속도 향상을 위해 사용됩니다.

비트 연산의 기본:

• AND 연산 (&): 두 비트가 모두 1일 때만 1을 반환합니다.
• OR 연산 (|): 두 비트 중 하나라도 1이면 1을 반환합니다.
• XOR 연산 (^): 두 비트가 서로 다를 때 1을 반환합니다.
• NOT 연산 (~): 비트를 반전시킵니다. (0 -> 1, 1 -> 0)
• LEFT SHIFT (<<): 모든 비트를 왼쪽으로 주어진 수만큼 이동시킵니다.
• RIGHT SHIFT (>>): 모든 비트를 오른쪽으로 주어진 수만큼 이동시킵니다.

비트마스킹의 대표적인 사용 예:

1. 단일 비트 설정, 제거, 토글: 특정 위치의 비트를 설정, 제거 또는 반전시키는데 사용됩니다.
2. 이진 표현에서 1의 개수 세기.
3. 두 수의 스왑: XOR 연산을 사용하여 추가 변수 없이 두 수를 교환할 수 있습니다.
4. 파워 오브 투 확인: 주어진 숫자가 2의 거듭제곱인지 확인하는데 사용됩니다.

예제와 솔루션 (이진 표현에서 1의 개수 세기):

문제:
정수 n을 입력으로 받아, 그 수의 이진 표현에서 1의 개수를 반환하라.

function countOnes(n) {
    let count = 0;

    while (n) {
        count += n & 1;
        n >>= 1;
    }

    return count;
}

console.log(countOnes(11));  // 출력: 3 (11의 이진 표현: 1011)

위 코드는 주어진 숫자 n의 이진 표현에서 1의 개수를 세는 함수를 보여줍니다. 비트 AND 연산과 오른쪽 시프트 연산을 사용하여 이를 수행합니다.

비트마스킹은 다양한 문제에서 공간 및 시간 효율성을 크게 향상시킬 수 있는 강력한 도구입니다.