e305: Xor 運算

2019-09-05

內容

有一個函式如下

C/C++:

long long sumxor(long long N) {
    long long ans = 0;
    for (long long i = 0; i < N; i++) {
        if ((N ^ i) == (N + i))ans++;
    }
    return ans;
}

Python:

def sumxor(N) :
    ans = 0
    for i in range(N) :
        if ((N ^ i) == (N + i)) :
            ans += 1
            return ans

Java:

public static long sumxor(long N) {
    long ans = 0;
    for (long i = 0; i < N; i++) {
        if ((N ^ i) == (N + i)) ans++;
    }
    return ans;
}

Pascal:

var
    i, N: int64;
    ans : int64 = 0;
function sumxor(N: int64):int64;
begin
    ans:=0;
    for i := 0 to N do begin
        if ((N xor i) = (N + i)) then ans:=ans+1;
        if (N=0) ans:=0;
        sumxor:=ans;
    end;
end;

因為要處理的 N 很大,現在請你優化這個函式

輸入

多筆測資

一行有一個整數 N(N<10¹⁵)

4
10

輸出

輸出函式的回傳值

4
4

解題思路

a ^ b 和 a + b 相等的情況只有在轉換成二進制後位元 1 不重疊的情況 (如下)

48 + 1 = (11000) + (00001)，此時不論用 XOR 或 + 都會變成 (11001)

而由於有多個 0 ，所以要算出所有組合數 : 2^{最大位元 1 後面 0 的數量} 舉例來說，上面的 48 最大位元 1 為 (‘1’1000)，後面共有 3 個 0 ，所以就是 2³ = 8，而因為是 2 的乘冪，所以可以用位元運算加速，如底部程式碼。

雖然 0 符合以上邏輯，但因為 0 沒有辦法進行位元操作所以要做特殊處理。

完整程式碼

AC (6ms, 104KB)

#include <stdio.h>

long long n, ans;

int main()
{
    while (scanf(" %llu", &n) == 1)
    {
        if (n)
        {
            ans = 1;
            do
            {
                if (!(n & 1))
                    ans <<= 1;
            } while (n >>= 1);
            printf("%llu\n", ans);
        }
        else puts("0");
    }
    return 0;
}