xor가 0과 같도록 몇 개의 4 자리 숫자 집합이 있습니까?

Question

두 개의 음이 아닌 정수 x와 y를 가지고 있는데, 두 개 모두 최대 30 비트를가집니다 (따라서 값은 약 10^9입니다).

나는 a_1 + a_2 = x 및 a_3 + a_4 = y와 xor가 같은 4 개의 수 {a_1, a_2, a_3, a_4}가 얼마나 많은지 계산하고 싶습니다. 0.

이 문제를 해결하는 가장 빠른 알고리즘은 무엇입니까?

내가 A_1 XOR A_2 = a_3 XOR a_4에 XOR 방정식을 재 배열되어 생각할 수있는 가장 빠른.

그러면 I는 O에서 왼쪽의 모든 값을 계산할 수있다 (X)과 O의 우변의 값 (Y), 전체 알고리즘은 O (X + Y)에서 실행되도록.

Answer 1

하자이 문제의 솔루션의 숫자 N(x, y). 분명히 N(0, 0)은 1입니다. 유일한 해결책은 (0, 0, 0, 0)이기 때문입니다. x 또는 y이 음수이면 a1, a2, a3, a4가 모두 음수가 아니기 때문에 해결책이 없습니다.

그렇지 않으면, 우리는 가장 낮은 비트에 대한 해결함으로써 진행 및 재발 관계를 생성 할 수 있습니다. n:0과 n:1을 2n + 0과 2n + 1 (그래서 0과 1이 최하위 비트 임)으로 작성하겠습니다. 이어서

:

N(0, 0) = 1 
N(-x, y) = N(x, -y) = 0 
N(x:0, y:0) = N(x, y) + N(x-1, y) + N(x, y-1) + N(x-1, y-1) 
N(x:0, y:1) = N(x:1, y:0) = 0 
N(x:1, y:1) = 4 * N(x, y) 

다음을 볼 수는, 하나는 A1, A2, A3, A4 가능한 저 비트를 고려한다.

먼저 N(x:0, y:0). 우리는 a1 + a2의 하위 비트가 0이 될 필요가 있습니다. 즉, a1과 a2가 모두 짝수이거나 둘 다 이상하다는 것을 의미합니다. 둘 다 홀수 인 경우 캐리가 발생하며 상위 비트에 1을 더한 값의 합은 x의 상위 비트에 합계해야합니다. 같은 논리가 a3, a4에 적용됩니다. 4 가지 가능성이 있습니다 : a1, a2, a3, a4의 모든 하위 비트는 0, a1, a2의 하위 비트는 1, a3, a4의 하위 비트는 1, a1, a2, a3, a4의 하위 비트는 1입니다. 4 건.

둘째 N(x:0, y:1) 및 N(x:1, y:0). 하나의 합이 짝수이고 다른 하나가 홀수 인 경우 해결책이 없습니다. a1, a2, a3, a4의 최하위 비트에 대한 모든 조합을 확인할 수 있습니다.

셋째 N(x:1, y:1). 정확히 a1과 a2 중 하나는 홀수이어야하며 마찬가지로 a3과 a4 중 하나는 홀수 여야합니다. 이 경우에는 4 가지 가능성이 있으며 어떤 경우에도 해당 사항이 없습니다. 지수 이론 그래서,

def N(x, y): 
    if x == y == 0: return 1 
    if x < 0 or y < 0: return 0 
    if x % 2 == y % 2 == 0: 
     return N(x//2, y//2) + N(x//2-1, y//2) + N(x//2, y//2-1) + N(x//2-1, y//2-1) 
    elif x % 2 == y % 2 == 1: 
     return 4 * N(x//2, y//2) 
    else: 
     return 0 

알고리즘은 여러 재귀 호출을 :

여기에 완벽한 솔루션입니다. 그러나 실제로 많은 지점이 신속하게 종료되므로 코드는 최대 2^30 값까지 충분히 빠르게 실행됩니다. 물론 캐시를 추가하거나 동적 프로그래밍 테이블을 사용하여 O (log (x) + log (y))의 런타임을 보장 할 수 있습니다.

마지막으로

는, 정확성의 신뢰를 높이기 위해, 여기에 순진 O에 대한 몇 가지 검사를의 (XY) 솔루션 :

def N_slow(x, y): 
    s = 0 
    for a1 in xrange(x + 1): 
     for a3 in xrange(y + 1): 
      a2 = x - a1 
      a4 = y - a3 
      if a1^a2^a3^a4: 
       continue 
      s += 1 
    return s 

for x in xrange(50): 
    for y in xrange(50): 
     n = N(x, y) 
     ns = N_slow(x, y) 
     if n != ns: 
      print 'N(%d, %d) = %d, want %d' % (x, y, n, ns)