En algunas máquinas raras donde la bifurcación es costosa, el enfoque obvio a continuación para encontrar el mínimo puede ser lento ya que usa la bifurcación.
C++
/* The obvious approach to find minimum (involves branching) */
int min(int x, int y)
{
return (x < y) ? x : y
}
//This code is contributed by Shubham Singh
C
/* The obvious approach to find minimum (involves branching) */
int min(int x, int y)
{
return (x < y) ? x : y
}
Java
/* The obvious approach to find minimum (involves branching) */
static int min(int x, int y)
{
return (x < y) ? x : y;
}
// This code is contributed by rishavmahato348.
Python3
# The obvious approach to find minimum (involves branching) def min(x, y): return x if x < y else y # This code is contributed by subham348.
C#
/* The obvious approach to find minimum (involves branching) */
static int min(int x, int y)
{
return (x < y) ? x : y;
}
// This code is contributed by rishavmahato348.
Javascript
<script>
/* The obvious approach to find minimum (involves branching) */
function min(x, y)
{
return (x < y) ? x : y;
}
// This code is contributed by subham348.
</script>
A continuación se muestran los métodos para obtener el mínimo (o el máximo) sin usar la ramificación. Sin embargo, por lo general, el enfoque obvio es el mejor.
Método 1 (usar XOR y operador de comparación)
El mínimo de x e y será
y ^ ((x ^ y) & -(x < y))
Funciona porque si x < y, entonces -(x < y) será -1, que son todos unos (11111….), entonces r = y ^ ((x ^ y) & (111111…)) = y ^ x ^ y = x.
Y si x>y, entonces-(x<y) será -(0) es decir -(cero) que es cero, entonces r = y^((x^y) & 0) = y^0 = y.
En algunas máquinas, evaluar (x < y) como 0 o 1 requiere una instrucción de bifurcación, por lo que puede no haber ninguna ventaja.
Para encontrar el máximo, utilice
x ^ ((x ^ y) & -(x < y));
C++
// C++ program to Compute the minimum
// or maximum of two integers without
// branching
#include<iostream>
using namespace std;
class gfg
{
/*Function to find minimum of x and y*/
public:
int min(int x, int y)
{
return y ^ ((x ^ y) & -(x < y));
}
/*Function to find maximum of x and y*/
int max(int x, int y)
{
return x ^ ((x ^ y) & -(x < y));
}
};
/* Driver code */
int main()
{
gfg g;
int x = 15;
int y = 6;
cout << "Minimum of " << x <<
" and " << y << " is ";
cout << g. min(x, y);
cout << "\nMaximum of " << x <<
" and " << y << " is ";
cout << g.max(x, y);
getchar();
}
// This code is contributed by SoM15242
C
// C program to Compute the minimum
// or maximum of two integers without
// branching
#include<stdio.h>
/*Function to find minimum of x and y*/
int min(int x, int y)
{
return y ^ ((x ^ y) & -(x < y));
}
/*Function to find maximum of x and y*/
int max(int x, int y)
{
return x ^ ((x ^ y) & -(x < y));
}
/* Driver program to test above functions */
int main()
{
int x = 15;
int y = 6;
printf("Minimum of %d and %d is ", x, y);
printf("%d", min(x, y));
printf("\nMaximum of %d and %d is ", x, y);
printf("%d", max(x, y));
getchar();
}
Java
// Java program to Compute the minimum
// or maximum of two integers without
// branching
public class AWS {
/*Function to find minimum of x and y*/
static int min(int x, int y)
{
return y ^ ((x ^ y) & -(x << y));
}
/*Function to find maximum of x and y*/
static int max(int x, int y)
{
return x ^ ((x ^ y) & -(x << y));
}
/* Driver program to test above functions */
public static void main(String[] args) {
int x = 15;
int y = 6;
System.out.print("Minimum of "+x+" and "+y+" is ");
System.out.println(min(x, y));
System.out.print("Maximum of "+x+" and "+y+" is ");
System.out.println( max(x, y));
}
}
Python3
# Python3 program to Compute the minimum
# or maximum of two integers without
# branching
# Function to find minimum of x and y
def min(x, y):
return y ^ ((x ^ y) & -(x < y))
# Function to find maximum of x and y
def max(x, y):
return x ^ ((x ^ y) & -(x < y))
# Driver program to test above functions
x = 15
y = 6
print("Minimum of", x, "and", y, "is", end=" ")
print(min(x, y))
print("Maximum of", x, "and", y, "is", end=" ")
print(max(x, y))
# This code is contributed
# by Smitha Dinesh Semwal
C#
using System;
// C# program to Compute the minimum
// or maximum of two integers without
// branching
public class AWS
{
/*Function to find minimum of x and y*/
public static int min(int x, int y)
{
return y ^ ((x ^ y) & -(x << y));
}
/*Function to find maximum of x and y*/
public static int max(int x, int y)
{
return x ^ ((x ^ y) & -(x << y));
}
/* Driver program to test above functions */
public static void Main(string[] args)
{
int x = 15;
int y = 6;
Console.Write("Minimum of " + x + " and " + y + " is ");
Console.WriteLine(min(x, y));
Console.Write("Maximum of " + x + " and " + y + " is ");
Console.WriteLine(max(x, y));
}
}
// This code is contributed by Shrikant13
PHP
<?php
// PHP program to Compute the minimum
// or maximum of two integers without
// branching
// Function to find minimum
// of x and y
function m_in($x, $y)
{
return $y ^ (($x ^ $y) &
- ($x < $y));
}
// Function to find maximum
// of x and y
function m_ax($x, $y)
{
return $x ^ (($x ^ $y) &
- ($x < $y));
}
// Driver Code
$x = 15;
$y = 6;
echo"Minimum of"," ", $x," ","and",
" ",$y," "," is "," ";
echo m_in($x, $y);
echo "\nMaximum of"," ",$x," ",
"and"," ",$y," ", " is ";
echo m_ax($x, $y);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to Compute the minimum
// or maximum of two integers without
// branching
/*Function to find minimum of x and y*/
function min(x,y)
{
return y ^ ((x ^ y) & -(x << y));
}
/*Function to find maximum of x and y*/
function max(x,y)
{
return x ^ ((x ^ y) & -(x << y));
}
/* Driver program to test above functions */
let x = 15
let y = 6
document.write("Minimum of "+ x + " and " + y + " is ");
document.write(min(x, y) + "<br>");
document.write("Maximum of " + x + " and " + y + " is ");
document.write(max(x, y) + "\n");
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
Minimum of 15 and 6 is 6 Maximum of 15 and 6 is 15
Complejidad de tiempo: O(1)
Espacio Auxiliar: O(1)
Método 2 (Usar la resta y el cambio)
Si sabemos que
INT_MIN <= (x - y) <= INT_MAX
, entonces podemos usar los siguientes, que son más rápidos porque (x – y) solo necesita evaluarse una vez.
Mínimo de x e y será
y + ((x - y) & ((x - y) >>(sizeof(int) * CHAR_BIT - 1)))
Este método cambia la resta de x e y por 31 (si el tamaño del entero es 32). Si (xy) es menor que 0, entonces (x -y)>>31 será 1. Si (xy) es mayor o igual que 0, entonces (x -y)>>31 será 0.
Entonces, si x >= y, obtenemos mínimo como y + (xy)&0 que es y.
Si x < y, obtenemos mínimo como y + (xy)&1 que es x.
Del mismo modo, para encontrar el uso máximo
x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)))
C++
#include <bits/stdc++.h>
using namespace std;
#define CHARBIT 8
/*Function to find minimum of x and y*/
int min(int x, int y)
{
return y + ((x - y) & ((x - y) >>
(sizeof(int) * CHARBIT - 1)));
}
/*Function to find maximum of x and y*/
int max(int x, int y)
{
return x - ((x - y) & ((x - y) >>
(sizeof(int) * CHARBIT - 1)));
}
/* Driver code */
int main()
{
int x = 15;
int y = 6;
cout<<"Minimum of "<<x<<" and "<<y<<" is ";
cout<<min(x, y);
cout<<"\nMaximum of"<<x<<" and "<<y<<" is ";
cout<<max(x, y);
}
// This code is contributed by rathbhupendra
C
#include<stdio.h>
#define CHAR_BIT 8
/*Function to find minimum of x and y*/
int min(int x, int y)
{
return y + ((x - y) & ((x - y) >>
(sizeof(int) * CHAR_BIT - 1)));
}
/*Function to find maximum of x and y*/
int max(int x, int y)
{
return x - ((x - y) & ((x - y) >>
(sizeof(int) * CHAR_BIT - 1)));
}
/* Driver program to test above functions */
int main()
{
int x = 15;
int y = 6;
printf("Minimum of %d and %d is ", x, y);
printf("%d", min(x, y));
printf("\nMaximum of %d and %d is ", x, y);
printf("%d", max(x, y));
getchar();
}
Java
// JAVA implementation of above approach
class GFG
{
static int CHAR_BIT = 4;
static int INT_BIT = 8;
/*Function to find minimum of x and y*/
static int min(int x, int y)
{
return y + ((x - y) & ((x - y) >>
(INT_BIT * CHAR_BIT - 1)));
}
/*Function to find maximum of x and y*/
static int max(int x, int y)
{
return x - ((x - y) & ((x - y) >>
(INT_BIT * CHAR_BIT - 1)));
}
/* Driver code */
public static void main(String[] args)
{
int x = 15;
int y = 6;
System.out.println("Minimum of "+x+" and "+y+" is "+min(x, y));
System.out.println("Maximum of "+x+" and "+y+" is "+max(x, y));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the approach
import sys;
CHAR_BIT = 8;
INT_BIT = sys.getsizeof(int());
#Function to find minimum of x and y
def Min(x, y):
return y + ((x - y) & ((x - y) >>
(INT_BIT * CHAR_BIT - 1)));
#Function to find maximum of x and y
def Max(x, y):
return x - ((x - y) & ((x - y) >>
(INT_BIT * CHAR_BIT - 1)));
# Driver code
x = 15;
y = 6;
print("Minimum of", x, "and",
y, "is", Min(x, y));
print("Maximum of", x, "and",
y, "is", Max(x, y));
# This code is contributed by PrinciRaj1992
C#
// C# implementation of above approach
using System;
class GFG
{
static int CHAR_BIT = 8;
/*Function to find minimum of x and y*/
static int min(int x, int y)
{
return y + ((x - y) & ((x - y) >>
(sizeof(int) * CHAR_BIT - 1)));
}
/*Function to find maximum of x and y*/
static int max(int x, int y)
{
return x - ((x - y) & ((x - y) >>
(sizeof(int) * CHAR_BIT - 1)));
}
/* Driver code */
static void Main()
{
int x = 15;
int y = 6;
Console.WriteLine("Minimum of "+x+" and "+y+" is "+min(x, y));
Console.WriteLine("Maximum of "+x+" and "+y+" is "+max(x, y));
}
}
// This code is contributed by mits
Javascript
<script>
// javascript implementation of above approach
var CHAR_BIT = 4;
var INT_BIT = 8;
/* Function to find minimum of x and y */
function min(x , y) {
return y + ((x - y) & ((x - y) >> (INT_BIT * CHAR_BIT - 1)));
}
/* Function to find maximum of x and y */
function max(x , y) {
return x - ((x - y) & ((x - y) >> (INT_BIT * CHAR_BIT - 1)));
}
/* Driver code */
var x = 15;
var y = 6;
document.write("Minimum of " + x + " and " + y + " is " + min(x, y)+"<br/>");
document.write("Maximum of " + x + " and " + y + " is " + max(x, y));
// This code is contributed by shikhasingrajput
</script>
Complejidad de tiempo: O(1)
Espacio Auxiliar: O(1)
Tenga en cuenta que la especificación ANSI C de 1989 no especifica el resultado del desplazamiento a la derecha con signo, por lo que el método anterior no es portátil. Si se lanzan excepciones en los desbordamientos, entonces los valores de x e y deben estar sin firmar o convertir a sin firmar para las restas para evitar lanzar una excepción innecesariamente, sin embargo, el desplazamiento a la derecha necesita un operando con signo para producir todos los bits cuando es negativo, así que cast para firmar allí.
Método 3 (Usar valor absoluto)
Una fórmula generalizada para encontrar el número máximo/mínimo con valor absoluto es:
(x + y + ABS(x-y) )/2
Encuentra el número mínimo es:
(x + y - ABS(x-y) )/2
Entonces, si podemos usar la operación bit a bit para encontrar el valor absoluto, podemos encontrar el número máximo/mínimo sin usar condiciones if. La forma de encontrar la forma absoluta con la operación bit a bit se puede encontrar aquí :
Paso 1) Establezca la máscara como desplazamiento a la derecha de un entero por 31 (suponiendo que los enteros se almacenan como valores de 32 bits en complemento a dos y que el operador de desplazamiento a la derecha sí firma la extensión).
mask = n>>31
Paso 2) XOR la máscara con número
mask ^ n
Paso 3) Reste la máscara del resultado del paso 2 y devuelva el resultado.
(mask^n) - mask
Por lo tanto, podemos concluir la solución de la siguiente manera:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
int absbit32(int x, int y)
{
int sub = x - y;
int mask = (sub >> 31);
return (sub ^ mask) - mask;
}
int max(int x, int y)
{
int abs = absbit32(x, y);
return (x + y + abs) / 2;
}
int min(int x, int y)
{
int abs = absbit32(x, y);
return (x + y - abs) / 2;
}
// Driver Code
int main()
{
cout << max(2, 3) << endl; //3
cout << max(2, -3) << endl; //2
cout << max(-2, -3) << endl; //-2
cout << min(2, 3) << endl; //2
cout << min(2, -3) << endl; //-3
cout << min(-2, -3) << endl; //-3
return 0;
}
// This code is contributed by avijitmondal1998
Java
// Java program for the above approach
import java.io.*;
class GFG {
public static void main(String []args){
System.out.println( max(2,3) ); //3
System.out.println( max(2,-3) ); //2
System.out.println( max(-2,-3) ); //-2
System.out.println( min(2,3) ); //2
System.out.println( min(2,-3) ); //-3
System.out.println( min(-2,-3) ); //-3
}
public static int max(int x, int y){
int abs = absbit32(x,y);
return (x + y + abs)/2;
}
public static int min(int x, int y){
int abs = absbit32(x,y);
return (x + y - abs)/2;
}
public static int absbit32(int x, int y){
int sub = x - y;
int mask = (sub >> 31);
return (sub ^ mask) - mask;
}
}
Python3
# Python3 program for the above approach def max(x, y): abs = absbit32(x,y) return (x + y + abs)//2 def min(x, y): abs = absbit32(x,y) return (x + y - abs)//2 def absbit32( x, y): sub = x - y mask = (sub >> 31) return (sub ^ mask) - mask # Driver code print( max(2,3) ) #3 print( max(2,-3) ) #2 print( max(-2,-3) ) #-2 print( min(2,3) ) #2 print( min(2,-3) ) #-3 print( min(-2,-3) ) #-3 # This code is contributed by rohitsingh07052.
C#
// C# program for the above approach
using System;
class GFG{
public static void Main(String []args)
{
Console.WriteLine(max(2, 3)); //3
Console.WriteLine(max(2, -3)); //2
Console.WriteLine(max(-2, -3)); //-2
Console.WriteLine(min(2, 3)); //2
Console.WriteLine(min(2, -3)); //-3
Console.WriteLine(min(-2, -3)); //-3
}
public static int max(int x, int y)
{
int abs = absbit32(x, y);
return (x + y + abs) / 2;
}
public static int min(int x, int y)
{
int abs = absbit32(x, y);
return (x + y - abs) / 2;
}
public static int absbit32(int x, int y)
{
int sub = x - y;
int mask = (sub >> 31);
return (sub ^ mask) - mask;
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program for the above approach
function max(x , y){
var abs = absbit32(x,y);
return (x + y + abs)/2;
}
function min(x , y){
var abs = absbit32(x,y);
return (x + y - abs)/2;
}
function absbit32(x , y){
var sub = x - y;
var mask = (sub >> 31);
return (sub ^ mask) - mask;
}
// Drive code
document.write( max(2,3)+"<br>" ); //3
document.write( max(2,-3)+"<br>" ); //2
document.write( max(-2,-3)+"<br>" ); //-2
document.write( min(2,3)+"<br>" ); //2
document.write( min(2,-3)+"<br>" ); //-3
document.write( min(-2,-3) ); //-3
// This code is contributed by 29AjayKumar
</script>
Complejidad de tiempo: O(1)
Espacio auxiliar: O(1)
Fuente:
http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax
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