e305: Xor 運算

e305: Xor 運算

題 意:

請 優 化 下 列 函 式
long long sumxor(long long N)

{
       long long sum = 0;
       for (int i = 0; i < N; ++i)
             sum += ((N ^ i) == (N + i));
       return sum;
}

對 於 輸 入 的 $N$，請 輸 出 $sum$，也 就 是 函 式 的 回 傳 值。


solve:
XOR 運 算 又 名 "不 進 位 加 法"。也 就 是 說 當 $a$ 及 $b$ 任 何 相 同 一 位 都 是 1 時，就 不 會 相 同，反 之，只 要 $a$ 及 $b$ 任 何 相 同 一 位 都 不 同 時，異 或 跟 加 法 就 會 相 同。
而 在 $N$ 以 下 有 幾 個 整 數 符 合 條 件 只 要 看 $N$ 在 二 進 制 下 有 幾 個 0 就 好 了，答 案 為 $2 ^ m$，其 中 $m$ 為 $N_2$ 0 的 個 數。

code: