整数 N が与えられた場合、1 から N までの範囲の exor を求めます
1 ^ 2 ^ 3 ^4 ^....N;
ブルートフォースアプローチ:
Tc:O(n)
Sc:O(1)
public int findExor(int N){ //naive/brute force approach: int val = 0; for(int i=1;i<5;i++){ val = val^ i; } return val; }
最適なアプローチ:
Tc:O(1)
Sc:O(1)
public int getExor(int N){ //better approach /** * one thing to observe is * 1 = 001 = 1 * 1 ^2 = 001 ^ 010 = 011= 3 * 1^2^3 = 011 ^ 011 = 0= 0 * 1^2^3^4 = 000^100 = 100= 4 * 1^2^3^4^5 = 100^101 = 001= 1 * 1^2^3^4^5^6 = 001^110 =111= 7 * 1^2^3^4^5^6^7 = 111^111=000= 0 * * what we can observer is : * * N%4==0 then result is: N * N%4 ==1 then result is: 1 * N%4 ==2 then result is: N+1 * N%4==3 then result is: 0 * * */ if(N%4==0) return N; else if(N%4 ==1) return 1; else if(N%4==2) return N+1; else return 0; }
L と R のような範囲の間で エクソルを見つけなければならない場合はどうなるでしょうか
たとえば、数値 4 と 7 の間の exor を見つけます。つまり 4^5^6^7。
これを解決するには、getExor() と同じ最適なソリューションを利用できます
まず、L-1 まで exor を取得します。つまり、getExor(L-1) = 1 ^ 2 ^ 3 (L-1 = 3 なので)....equation(1)
その後、getExor(R) = 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ----式(2)
が見つかります。ついに、
Result = equation(1) ^ equation(2) = (1 ^ 2 ^ 3) ^ (1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7) = (4^5^6^7)
public int findExorOfRange(int L, int R){ return getExor(L-1) ^ getExor(R); } public int getExor(int N){ //better approach /** * one thing to observe is * 1 = 001 = 1 * 1 ^2 = 001 ^ 010 = 011= 3 * 1^2^3 = 011 ^ 011 = 0= 0 * 1^2^3^4 = 000^100 = 100= 4 * 1^2^3^4^5 = 100^101 = 001= 1 * 1^2^3^4^5^6 = 001^110 =111= 7 * 1^2^3^4^5^6^7 = 111^111=000= 0 * * what we can observer is : * * N%4==0 then result is: N * N%4 ==1 then result is: 1 * N%4 ==2 then result is: N+1 * N%4==3 then result is: 0 * * */ if(N%4==0) return N; else if(N%4 ==1) return 1; else if(N%4==2) return N+1; else return 0; }
以上がN 個の数値の Xorの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。