범위의 빠른 비트 계산

Question

이 문제를 해결하는 알고리즘을 찾으려면 다음을 수행하십시오.
범위 [x, y]에있는 숫자의 모든 양수 비트 합계를 찾습니다.
경고 : x와 y는 매우 클 수 있습니다 (1에서 10^20까지).
도움 주셔서 감사합니다.

Answer 1

패턴을 식별하는 구체적인 예를 살펴 보는 것이 좋습니다. 예를 들어, 여기에 (25) (20)는 자신의 바이너리 표현은 다음과 같습니다 열을 기준으로 그것을보고

20: 10100 
21: 10101 
22: 10110 
23: 10111 
24: 11000 
25: 11001 

, 그것은 가장 오른쪽 열은 항상 우리가 결론을 내릴 수있는이에서 0과 1 번갈아 것이 명백 당신의 범위가있는 경우 그 N 개의 숫자와 N은 짝수이면 가장 오른쪽 열에 N/2 비트가 있습니다. 이제 가장 오른쪽 열을 무시하고 나머지 비트에서 패턴을 식별하려고 시도하십시오.

1010 
1010 
1011 
1011 
1100 
1100 

목록의 각 번호는 정확히 한 번 반복됩니다. 십진수로 변환하면이 숫자는 1010 = 10, 1011 = 11, 1100 = 12입니다. 이 두 가지 관찰을 사용하면 bitsInRange(20, 25) = (27 - 20 - 1) + 2*bitsInRange(10,12)이라고 결론 지을 수 있습니다. 우리가 확인 된 패턴은 모두 짝수와 홀수 끝 번호를 시작 어떤 위해 해당하므로 수식이 일반화 될 수 있습니다

bitsInRange(X,Y) = 
if X is even and Y is odd: 
    (Y - X - 1) + 2*bitsInRange(X/2, (Y-1)/2) 

그러나 우리는 이상한 시작 번호, 끝 번호가있는 경우 그거야? 우리가 확인한 두 패턴이 그 종류의 숫자에 대해 정확히 동일하지 않기 때문에 위의 공식은 이들에 대해서는 작동하지 않습니다. 당신은 짝수와 홀수의 각각의 가능한 조합에 대해 별도의 수식을 작성할 수 있습니다. 그러나 그 방법은 위험하고 전체가 Fencepost Errors입니다. numBits는 하나의 숫자에 1 비트의 양을 제공

bitsInRange(X, Y) = bitsInRange(X, Y-1) + numBits(Y) 
bitsInRange(X, Y) = bitsInRange(X+1, Y) + numBits(X) 

을 ... :이 중요한 특성을 활용하면 당신은 쉽게 시간을해야합니다.

이제 짝수 및 홀수 범위의 가능한 모든 조합에 대해 재귀 수식을 작성할 수 있습니다. 마지막 경우는 절반에 문제 공간을 자르면, 다른 모든 경우 신속하게 최종 케이스에 문제를 변환하기 때문에

function bitsInRange(X,Y): 
    if X == Y: 
     return numBits(X) 
    if X is odd: 
     return bitsInRange(X+1, Y) + numBits(X) 
    if Y is even: 
     return bitsInRange(X, Y-1) + numBits(Y) 
    return (Y - X - 1) + 2*bitsInRange(X/2, (Y-1)/2) 

(우리는 또한 그런데,베이스 케이스 필요), 전체 공식은 로그 복잡성을 가지고 . [1, 10^20]과 같이 거대한 범위에서 비트를 얻으려고한다면이 방법이 유용합니다. 그런 엄청난 숫자의 경우에도 bitsInRange은 약 200 번 정도만 실행됩니다.