logo

TechCodeview

XOR av 1 till n tal

Givet ett nummer n är uppgiften att hitta XOR från 1 till n. 
Exempel:  

Ingång: n = 6
Utgång: 7
// 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 = 7



Ingång: n = 7
Utgång:
// 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 = 0

sträng hitta c++

Naivt tillvägagångssätt - O(n) tid

1- Initiera resultatet som 0. 
1- Gå igenom alla nummer från 1 till n. 
2- Gör XOR av nummer en efter en med resultat. 
3- Returnera resultatet i slutet.

C++ 
// C++ program to find XOR of numbers // from 1 to n. #include    using namespace std; int computeXOR(int n) {  int res = 0;  for (int i = 1; i <= n; i++) {  res = res ^ i;   }  return res; } int main() {  int n = 7;  cout << computeXOR(n) << endl;  return 0; }
Java 
// Given a number n find the XOR from 1 to n for given n number import java.io.*; public class GfG {  static int computeXor(int n){  int res = 0;  for (int i = 1; i <= n; i++) {  res = res^i;   }  return res;  }  public static void main(String[] args) {  int n = 7;  System.out.println(computeXor(n));  } }
Python 
#defining a function computeXOR def computeXOR(n): res = 0 for i in range(1n+1): res = res ^ i return res n = 7 print(computeXOR(n))
C# 
// C# program that finds the XOR // from 1 to n for a given number n using System; public class GFG {  static int computeXor(int n)  {  int res = 0;  for (int i = 1; i <= n; i++) {  res = res ^ i; // calculate XOR  }  return res;  }  // Driver code  public static void Main(string[] args)  {  int n = 7;  // Function call  int ans = computeXor(n);  Console.WriteLine(ans);  } } // This code is contributed by phasing17
JavaScript 
// JavaScript that for a number n // finds the XOR from 1 to n for given n number function computeXor(n){  var res = 0;  for (let i = 1; i <= n; i++)  res = res^i; // calculate XOR  return res; } // Driver Code let n = 7; console.log(computeXor(n));

Produktion 
0

Tidskomplexitet: På)
Hjälputrymme: O(1)



sträng till heltalskonvertering

Förväntad inflygning - O(1) Tid

1- Hitta resten av n genom att modulera det med 4. 
2- Om rem = 0 kommer XOR att vara samma som n. 
3- Om rem = 1 så blir XOR 1. 
4- Om rem = 2 kommer XOR att vara n+1. 
5- Om rem = 3 kommer XOR att vara 0.
  Hur fungerar detta?  
När vi gör XOR av tal får vi 0 som XOR-värde strax före en multipel av 4. Detta upprepas hela tiden före varje multipel av 4. 

Nummer Binär-Repr XOR-från-1-till-n

minimax algoritm

1 1 [0001]
2 10 [0011]
3 11 [0000]<----- We get a 0
4 100 [0100]<----- Equals to n
5 101 [0001]
6 110 [0111]
7 111 [0000]<----- We get 0
8 1000 [1000]<----- Equals to n
9 1001 [0001]
10 1010 [1011]
11 1011 [0000]<------ We get 0
12 1100 [1100]<------ Equals to n  



C++ 
// C++ program to find XOR of numbers // from 1 to n. #include   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
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>
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 ?>

Produktion 
1

Tidskomplexitet: O(1)
Hjälputrymme: O(1)