给定一个数字n，任务是找到从1到n的异或。 例如：
null
Input : n = 6Output : 7// 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 = 7Input : n = 7Output : 0// 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 = 0
方法1（天真的方法）： 1-将结果初始化为0。 1-遍历从1到n的所有数字。 2-用结果逐个进行数字的异或运算。 3-最后，返回结果。 方法2（有效方法）： 1-用4模化n的余数。 2-如果rem=0，那么xor将与n相同。 3-如果rem=1，那么xor将为1。 4-如果rem=2，那么xor将是n+1。 5-如果rem=3，那么xor将为0。
C++
// C++ program to find XOR of numbers // from 1 to n. #include<bits/stdc++.h> using namespace std; // Method to calculate xor int computeXOR( int n) { // If n is a multiple of 4 if (n % 4 == 0) return n; // If n%4 gives remainder 1 if (n % 4 == 1) return 1; // If n%4 gives remainder 2 if (n % 4 == 2) return n + 1; // If n%4 gives remainder 3 return 0; } // Driver method int main() { int n = 5; cout<<computeXOR(n); } // This code is contributed by rutvik_56. |
JAVA
// Java program to find XOR of numbers // from 1 to n. class GFG { // Method to calculate xor static int computeXOR( int n) { // If n is a multiple of 4 if (n % 4 == 0 ) return n; // If n%4 gives remainder 1 if (n % 4 == 1 ) return 1 ; // If n%4 gives remainder 2 if (n % 4 == 2 ) return n + 1 ; // If n%4 gives remainder 3 return 0 ; } // Driver method public static void main (String[] args) { int n = 5 ; System.out.println(computeXOR(n)); } } |
Python 3
# Python 3 Program to find # XOR of numbers from 1 to n. # Function to calculate xor def computeXOR(n) : # Modulus operator are expensive # on most of the computers. n & 3 # will be equivalent to n % 4. # if n is multiple of 4 if n % 4 = = 0 : return n # If n % 4 gives remainder 1 if n % 4 = = 1 : return 1 # If n%4 gives remainder 2 if n % 4 = = 2 : return n + 1 # If n%4 gives remainder 3 return 0 # Driver Code if __name__ = = "__main__" : n = 5 # function calling print (computeXOR(n)) # This code is contributed by ANKITRAI1 |
C#
// C# program to find XOR // of numbers from 1 to n. using System; class GFG { // Method to calculate xor static int computeXOR( int n) { // If n is a multiple of 4 if (n % 4 == 0) return n; // If n%4 gives remainder 1 if (n % 4 == 1) return 1; // If n%4 gives remainder 2 if (n % 4 == 2) return n + 1; // If n%4 gives remainder 3 return 0; } // Driver Code static public void Main () { int n = 5; Console.WriteLine(computeXOR(n)); } } // This code is contributed by ajit |
PHP
<?php // PHP program to find XOR // of numbers from 1 to n. // Function to calculate xor function computeXOR( $n ) { // Modulus operator are expensive // on most of the computers. n & 3 // will be equivalent to n % 4. switch ( $n & 3) // n % 4 { // if n is multiple of 4 case 0: return $n ; // If n % 4 gives remainder 1 case 1: return 1; // If n % 4 gives remainder 2 case 2: return $n + 1; // If n % 4 gives remainder 3 case 3: return 0; } } // Driver code $n = 5; echo computeXOR( $n ); // This code is contributed by aj_36 ?> |
Javascript
<script> // JavaScript program to find XOR of numbers // from 1 to n. // Function to calculate xor function computeXOR(n) { // Modulus operator are expensive on most of the // computers. n & 3 will be equivalent to n % 4. // if n is multiple of 4 if (n % 4 == 0) return n; // If n % 4 gives remainder 1 if (n % 4 == 1) return 1; // If n % 4 gives remainder 2 if (n % 4 == 2) return n + 1; // If n % 4 gives remainder 3 if (n % 4 == 3) return 0; } // Driver code // your code goes here let n = 5; document.write(computeXOR(n)); // This code is constributed by Surbhi Tyagi. </script> |
输出：
1
时间复杂度：O（1）
辅助空间：O（1）
这是怎么回事？ 当我们对数字进行异或运算时，我们得到0作为4的倍数之前的异或值。这会在4的每一个倍数之前不断重复。
Number Binary-Repr XOR-from-1-to-n1 1 [0001]2 10 [0011]3 11 [0000] <----- We get a 04 100 [0100] <----- Equals to n5 101 [0001]6 110 [0111]7 111 [0000] <----- We get 08 1000 [1000] <----- Equals to n9 1001 [0001]10 1010 [1011]11 1011 [0000] <------ We get 012 1100 [1100] <------ Equals to n
本文由 萨希尔·查布拉 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
