首页 > 图灵资讯 > 技术篇>正文
N 个数字的异或
2024-09-29 20:50:55
给定一个整数 n,找到 1 到 n 范围内的异或 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 <p>最佳方法:<br> tc:o(1)<br> sc:o(1)<br></p> <pre class="brush:php;toolbar:false"> 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^6^ = 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 两者之间的异或,即 4^5^6^7。
为了解决这个问题,我们可以使用它 getexor() 同样的最佳解决方案
首先,我们将得到exor直到l-1,即getexor(l-1) = 1 ^ 2 ^ 3(因为l-1 = 3...方程(1)
然后我们会发现 getexor(r) = 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ----equation(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^6^ = 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 更多关于图灵教育的其他相关文章,请关注不同或详细的数字!