비트마스크 연산

대표 문제 (비트 마스크와 누적합을 이용한 문제)

문제 링크

세부 예제들

dp[i] = (dp[i - 1] << 1) + (1L << i)

// 아래의 연산은 dp[i - 1] * 2와 같은 의미이다.
dp[i-1] << 1
 
// 아래의 연산은 2^i 와 같다.
1L <<i

동작 방법

• 이전 dp값을 두 배로 만들고
• 2의 i제곱 값을 더하는 점화식입니다.
• 비트 연산을 이용해 곱셈과 거듭제곱 연산을 빠르게 처리 비트 연산을 안쓰면 아래와 같이 표현할 수 있다.

dp[i] = dp[i - 1] * 2 + (long)Math.pow(2, i)

아래 반복문에서 비트 연산

for (int i = size; i > 0; i--) {  
	// 숫자 1L을 i비트 만큼 이동시킨 부분(특정 위치의 1확인)과 비교해서 1L인 경우면 내부로 들어간다.
    if ((n & (1L << i)) != 0L) {  
	    // 숫자 13을 예시로 들고 첫 번째 반복문이라고 가정을 하면
	    // `n - (1L << i) + 1`은 13 - 8 + 1 = 6이다.
	    // dp[i-1]에서 0 ~ 7까지의 1의 개수 합을 알 수 있다.
	    // 숫자 6개(8, 9, 10, 11, 12, 13) 각각에 대해 3번째 숫자가 1인 경우의 수를 더한다.
        count += dp[i - 1] + (n - (1L << i) + 1);  
 
	    // 앞의 비트를 빼주면서 남은 부분을 처리한다.
	    // 13(1101) => 5(101)
        n -= (1L << i); 
    }  
}

직접 이진법으로 변환하지 않아도 내부적으로 변환한다

• 1L << 2 = 4
• 1L << 3 = 8
• 1L << 4 = 16

long count = n & 1

정수 n의 가장 오른쪽이 짝수인지 홀수인지 확인하는 코드
홀수면 1 짝수면 0을 count에 저장하게 된다.

동작 방법

• &는 비트 AND 연산자입니다. 두 수의 각 비트를 비교해서, 둘 다 1일 때만 1을 결과로 만듭니다
• 1의 이진수는 ...0 001이므로, n과 1을 AND하면 n의 최하위 비트(맨 오른쪽 비트)만 남고 나머지는 모두 0이 됩니다.