Dados dos enteros, encuentre XOR de ellos sin usar el operador XOR, es decir, sin usar ^ en C/C++.
Ejemplos:
Input: x = 1, y = 2 Output: 3 Input: x = 3, y = 5 Output: 6
Una solución simple es recorrer todos los bits uno por uno. Para cada par de bits, verifique si ambos son iguales, configure el bit correspondiente como 0 en la salida, de lo contrario, configúrelo como 1.
C++
// C++ program to find XOR without using ^
#include <iostream>
using namespace std;
// Returns XOR of x and y
int myXOR(int x, int y)
{
int res = 0; // Initialize result
// Assuming 32-bit Integer
for (int i = 31; i >= 0; i--)
{
// Find current bits in x and y
bool b1 = x & (1 << i);
bool b2 = y & (1 << i);
// If both are 1 then 0 else xor is same as OR
bool xoredBit = (b1 & b2) ? 0 : (b1 | b2);
// Update result
res <<= 1;
res |= xoredBit;
}
return res;
}
// Driver program to test above function
int main()
{
int x = 3, y = 5;
cout << "XOR is " << myXOR(x, y);
return 0;
}
C
// C program to find XOR without using ^
#include <stdio.h>
#include <stdbool.h> //to use bool
// Returns XOR of x and y
int myXOR(int x, int y)
{
int res = 0; // Initialize result
// Assuming 32-bit Integer
for (int i = 31; i >= 0; i--)
{
// Find current bits in x and y
bool b1 = x & (1 << i);
bool b2 = y & (1 << i);
// If both are 1 then 0 else xor is same as OR
bool xoredBit = (b1 & b2) ? 0 : (b1 | b2);
// Update result
res <<= 1;
res |= xoredBit;
}
return res;
}
// Driver Code
int main()
{
int x = 3, y = 5;
printf("XOR is %d\n", myXOR(x, y));
return 0;
}
// This code is contributed by phalashi.
Java
// Java program to find XOR without using ^
import java.io.*;
class GFG{
// Returns XOR of x and y
static int myXOR(int x, int y)
{
// Initialize result
int res = 0;
// Assuming 32-bit Integer
for(int i = 31; i >= 0; i--)
{
// Find current bits in x and y
int b1 = ((x & (1 << i)) == 0 ) ? 0 : 1;
int b2 = ((y & (1 << i)) == 0 ) ? 0 : 1;
// If both are 1 then 0 else xor is same as OR
int xoredBit = ((b1 & b2) != 0) ? 0 : (b1 | b2);
// Update result
res <<= 1;
res |= xoredBit;
}
return res;
}
// Driver Code
public static void main (String[] args)
{
int x = 3, y = 5;
System.out.println("XOR is " + myXOR(x, y));
}
}
// This code is contributed by math_lover
Python3
# Python3 program to find XOR without using ^
# Returns XOR of x and y
def myXOR(x, y):
res = 0 # Initialize result
# Assuming 32-bit Integer
for i in range(31, -1, -1):
# Find current bits in x and y
b1 = x & (1 << i)
b2 = y & (1 << i)
b1 = min(b1, 1)
b2 = min(b2, 1)
# If both are 1 then 0
# else xor is same as OR
xoredBit = 0
if (b1 & b2):
xoredBit = 0
else:
xoredBit = (b1 | b2)
# Update result
res <<= 1;
res |= xoredBit
return res
# Driver Code
x = 3
y = 5
print("XOR is", myXOR(x, y))
# This code is contributed by Mohit Kumar
C#
// C# program to find XOR
// without using ^
using System;
class GFG{
// Returns XOR of x and y
static int myXOR(int x,
int y)
{
// Initialize result
int res = 0;
// Assuming 32-bit int
for(int i = 31; i >= 0; i--)
{
// Find current bits in x and y
int b1 = ((x & (1 << i)) == 0 ) ?
0 : 1;
int b2 = ((y & (1 << i)) == 0 ) ?
0 : 1;
// If both are 1 then 0 else
// xor is same as OR
int xoredBit = ((b1 & b2) != 0) ?
0 : (b1 | b2);
// Update result
res <<= 1;
res |= xoredBit;
}
return res;
}
// Driver Code
public static void Main(String[] args)
{
int x = 3, y = 5;
Console.WriteLine("XOR is " +
myXOR(x, y));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to find XOR without using ^
// Returns XOR of x and y
function myXOR(x, y)
{
let res = 0; // Initialize result
// Assuming 32-bit Integer
for (let i = 31; i >= 0; i--)
{
// Find current bits in x and y
let b1 = ((x & (1 << i)) == 0 ) ? 0 : 1;
let b2 = ((y & (1 << i)) == 0 ) ? 0 : 1;
// If both are 1 then 0 else xor is same as OR
let xoredBit = (b1 & b2) ? 0 : (b1 | b2);
// Update result
res <<= 1;
res |= xoredBit;
}
return res;
}
// Driver program to test above function
let x = 3, y = 5;
document.write("XOR is " + myXOR(x, y));
// This code is contributed by Surbhi Tyagi.
</script>
Producción
XOR is 6
Complejidad de Tiempo: O( num ), donde num es el número de bits en el máximo de los dos números.
Complejidad espacial: O(1)
Gracias a Utkarsh Trivedi por sugerir esta solución.
Una mejor solución puede encontrar XOR sin usar un bucle.
1) Encuentre OR bit a bit de x e y (el resultado tiene bits establecidos donde x ha establecido o y ha establecido bits). O de x = 3 (011) e y = 5 (101) es 7 (111)
2) Para eliminar los bits establecidos adicionales, busque lugares donde tanto x como y tengan bits establecidos. El valor de la expresión “~x | ~y” tiene 0 bits siempre que x e y tengan bits establecidos.
3) AND bit a bit de “(x | y)” y “~x | ~y” produce el resultado requerido.
A continuación se muestra la implementación.
C++
// C++ program to find XOR without using ^
#include <iostream>
using namespace std;
// Returns XOR of x and y
int myXOR(int x, int y)
{
return (x | y) & (~x | ~y);
}
// Driver program to test above function
int main()
{
int x = 3, y = 5;
cout << "XOR is " << myXOR(x, y);
return 0;
}
Java
// Java program to find
// XOR without using ^
import java.io.*;
class GFG
{
// Returns XOR of x and y
static int myXOR(int x, int y)
{
return (x | y) &
(~x | ~y);
}
// Driver Code
public static void main (String[] args)
{
int x = 3, y = 5;
System.out.println("XOR is "+
(myXOR(x, y)));
}
}
// This code is contributed by ajit
Python3
# Python 3 program to
# find XOR without using ^
# Returns XOR of x and y
def myXOR(x, y):
return ((x | y) &
(~x | ~y))
# Driver Code
x = 3
y = 5
print("XOR is" ,
myXOR(x, y))
# This code is contributed
# by Smitha
C#
// C# program to find
// XOR without using ^
using System;
class GFG
{
// Returns XOR of x and y
static int myXOR(int x, int y)
{
return (x | y) &
(~x | ~y);
}
// Driver Code
static public void Main ()
{
int x = 3, y = 5;
Console.WriteLine("XOR is "+
(myXOR(x, y)));
}
}
// This code is contributed by m_kit
PHP
<?php
// PHP program to find
// XOR without using ^
// Returns XOR of x and y
function myXOR($x, $y)
{
return ($x | $y) & (~$x | ~$y);
}
// Driver Code
$x = 3;
$y = 5;
echo "XOR is " , myXOR($x, $y);
// This code is contributed by aj_36
?>
Javascript
<script>
// Javascript program to find XOR without using ^
// Returns XOR of x and y
function myXOR(x, y)
{
return (x | y) & (~x | ~y);
}
// Driver program to test above function
let x = 3, y = 5;
document.write("XOR is " + myXOR(x, y));
// This code is contributed by subham348.
</script>
Producción
XOR is 6
Complejidad de tiempo: O(1)
Complejidad espacial: O(1)
Gracias a jitu_the_best por sugerir esta solución.
Solución alternativa:
C++
// C++ program to find XOR without using ^
#include <iostream>
using namespace std;
// Returns XOR of x and y
int myXOR(int x, int y)
{
return (x & (~y)) | ((~x )& y);
}
// Driver program to test above function
int main()
{
int x = 3, y = 5;
cout << "XOR is " << myXOR(x, y);
return 0;
}
Java
// Java program to find XOR without using ^
import java.io.*;
class GFG
{
// Returns XOR of x and y
static int myXOR(int x, int y)
{
return (x & (~y)) | ((~x )& y);
}
// Driver Code
public static void main (String[] args)
{
int x = 3, y = 5;
System.out.println("XOR is "+
(myXOR(x, y)));
}
}
// This code is contributed by shivanisinghss2110
Python3
# Python3 program to
# Returns XOR of x and y
def myXOR(x, y):
return (x & (~y)) | ((~x )& y)
# Driver Code
x = 3
y = 5
print("XOR is" ,
myXOR(x, y))
# This code is contributed by shivanisinghss2110
C#
// C# program to find XOR without using ^
using System;
class GFG{
// Returns XOR of x and y
static int myXOR(int x, int y)
{
return (x & (~y)) | ((~x )& y);
}
// Driver program to test above function
public static void Main()
{
int x = 3, y = 5;
Console.WriteLine("XOR is " +myXOR(x, y));
}
}
// This code is contributed by shivansinghss2110
Javascript
<script>
// Javascript program to find XOR without using ^
// Returns XOR of x and y
function myXOR(x, y)
{
return (x & (~y)) | ((~x ) & y);
}
// Driver code
let x = 3, y = 5;
document.write("XOR is " + myXOR(x, y));
// This code is contributed by subhammahato348
</script>
Producción
XOR is 6
Complejidad de tiempo: O(1)
Complejidad espacial: O(1)
Otra solución: podemos simplemente usar una de las propiedades del operador bit a bit XOR, es decir, a+b = a^b + 2*(a&b), con la ayuda de esto también podemos hacer lo mismo para una variante del operador.
C++14
// C++ program to find XOR without using ^
#include <iostream>
using namespace std;
int XOR(int x, int y) { return (x + y - (2 * (x & y))); }
int main()
{
int x = 3, y = 5;
cout << XOR(x, y) << endl;
return 0;
}
// this code is contributed by vishu05
Java
// Java program to find XOR without using ^
class GFG {
static int XOR(int x, int y) {
return (x + y - (2 * (x & y)));
}
public static void main(String[] args) {
int x = 3, y = 5;
System.out.print(XOR(x, y) + "\n");
}
}
// This code is contributed by umadevi9616
Python3
# Python3 program to return XOR of x and y without ^ operator
def XOR(x, y):
return (x+y - (2*(x & y)))
# Driver Code
x = 3
y = 5
print("XOR of",x,'&',y,'is:',
XOR(x, y))
# This code is contributed by vishu05
C#
// C# program to find XOR without using ^
using System;
class GFG{
static int XOR(int x, int y)
{
return(x + y - (2 * (x & y)));
}
// Driver code
public static void Main(String[] args)
{
int x = 3, y = 5;
Console.Write(XOR(x, y) + "\n");
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// javascript program to find XOR without using ^
function XOR(x , y) {
return (x + y - (2 * (x & y)));
}
var x = 3, y = 5;
document.write(XOR(x, y) + "\n");
// This code contributed by umadevi9616
</script>
Producción
6
Complejidad de tiempo: O(1), es decir, cálculo simple del operador aritmético y bit a bit.
Espacio Auxiliar: O(1)
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA