[演算法] XOR 連續的數

Python:

def f(a):
    return [a, 1, a + 1, 0][a % 4]


def get_xor_between(a, b):
    return f(a - 1) ^ f(b)

Java:

private static long f(long n)
{
  return (new long[]{n, 1, n + 1, 0})[n % 4];
}

public static long get_xor_between(long a, long b)
{
  return f(a - 1) ^ f(b);
}

C:

long long f(long long n)
{
  long long res[] = {n, 1, n + 1, 0};
  return res[n % 4];
}

long long get_xor_between(long long a, long long b)
{
  return f(a - 1) ^ f(b);
}

用法:

假如我要求 5^6^7^8^9 的值,就呼叫 get_xor_between(5, 9)

這個演算法讓原本時間複雜度 O(n) 的過程變成 O(1)

Show Comments