¿Explica este fragmento que encuentra el máximo de dos enteros sin usar if-else o cualquier otro operador de comparación?

Encuentra el máximo de dos números. No debe usar if-else o cualquier otro operador de comparación. Encontré esta pregunta en el tablón de anuncios en línea, así que pensé que debería preguntar en StackOverflow

EJEMPLO Entrada: 5, 10 Salida: 10

Encontré esta solución, ¿alguien puede ayudarme a entender estas líneas de código?

int getMax(int a, int b) { int c = a - b; int k = (c >> 31) & 0x1; int max = a - k * c; return max; } 

 int getMax(int a, int b) { int c = a - b; int k = (c >> 31) & 0x1; int max = a - k * c; return max; } 

Vamos a diseccionar esto. Parece que esta primera línea es sencilla: almacena la diferencia de a y b . Este valor es negativo si a < b y no es negativo de lo contrario. De hecho, hay un error aquí: si la diferencia de los números a y b es tan grande que no cabe en un número entero, esto dará lugar a un comportamiento indefinido, ¡vaya! Asummos que eso no sucede aquí.

En la siguiente línea, que es

 int k = (c >> 31) & 0x1; 

la idea es verificar si el valor de c es negativo. En prácticamente todas las computadoras modernas, los números se almacenan en un formato llamado complemento de dos en el cual el bit más alto del número es 0 si el número es positivo y 1 si el número es negativo. Además, la mayoría de las entradas son de 32 bits. (c >> 31) desplaza el número hacia abajo 31 bits, dejando el bit más alto del número en el punto para el bit más bajo. El siguiente paso para tomar este número y ANDing it con 1 (cuya representación binaria es 0 en todas partes excepto el último bit) borra todos los bits más altos y solo le da el bit más bajo. Como el bit más bajo de c >> 31 es el bit más alto de c , este lee el bit más alto de c como 0 o 1. Dado que el bit más alto es 1 sif c es 1, esta es una forma de comprobar si c es negativo (1) o positivo (0). Combinando este razonamiento con lo anterior, k es 1 si a < b y es 0 de lo contrario.

El último paso es hacer esto:

 int max = a - k * c; 

Si a < b , entonces k == 1 k * c = c = a - b , y así

 a - k * c = a - (a - b) = a - a + b = b 

Cuál es el máximo correcto, ya que a < b . De lo contrario, si a >= b , entonces k == 0 y

 a - k * c = a - 0 = a 

Que también es el máximo correcto

Aquí vamos: (a + b) / 2 + |a - b| / 2 (a + b) / 2 + |a - b| / 2

Usa hacks bit a bit

 r = x ^ ((x ^ y) & -(x < y)); // max(x, y) 

Si sabe que INT_MIN < = x - y <= INT_MAX, puede usar lo siguiente, que es más rápido porque (x - y) solo necesita ser evaluado una vez.

 r = x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))); // max(x, y) 

Fuente: Bit Twiddling Hacks por Sean Eron Anderson

 (sqrt( a*a + b*b - 2*a*b ) + a + b) / 2 

Esto se basa en la misma técnica que la solución de mike.dld , pero aquí es menos “obvio” lo que estoy haciendo. Una operación “abs” parece que estás comparando el signo de algo, pero aquí estoy aprovechando el hecho de que sqrt () siempre te devolverá la raíz cuadrada positiva, así que estoy cuadrando (ab) escribiéndola en forma completa y luego cuadrada- enraizándolo otra vez, agregando a + b y dividiendo por 2.

Verá que siempre funciona: por ejemplo, el ejemplo del usuario de 10 y 5 obtiene sqrt (100 + 25 – 100) = 5, luego agregue 10 y 5 le da 20 y divide por 2 le da 10.

Si usamos 9 y 11 como nuestros números, obtendríamos (sqrt (121 + 81 – 198) + 11 + 9) / 2 = (sqrt (4) + 20) / 2 = 22/2 = 11

La respuesta más simple está abajo.

 #include  int Max(int x, int y) { return (float)(x + y) / 2.0 + abs((float)(x - y) / 2); } int Min(int x, int y) { return (float)(x + y) / 2.0 - abs((float)(x - y) / 2); } 
 int max(int i, int j) { int m = ((ij) >> 31); return (m & j) + ((~m) & i); } 

Esta solución evita la multiplicación. m será 0x00000000 o 0xffffffff

Usando la idea cambiante para extraer el letrero tal como fue publicado por otros, aquí hay otra manera:

 max (a, b) = new[] { a, b } [((a - b) >> 31) & 1] 

Esto empuja los dos números en una matriz con el número máximo dado por el elemento de matriz cuyo índice es signo de la diferencia entre los dos números.

Ten en cuenta que:

  1. La diferencia (a - b ) puede desbordarse.
  2. Si los números no están firmados y el operador >> refiere a un desplazamiento a la derecha lógico , el & 1 es innecesario.

Así es como creo que haría el trabajo. No es tan fácil de leer como te gustaría, pero cuando comienzas con “¿cómo hago X sin usar la forma obvia de hacer X?”, En cierto modo debes esperar eso. En teoría, esto también te deja algo de portabilidad, pero tú ” Tengo que encontrar un sistema bastante inusual para ver un problema.

 #define BITS (CHAR_BIT * sizeof(int) - 1) int findmax(int a, int b) { int rets[] = {a, b}; return rets[unsigned(ab)>>BITS]; } 

Esto tiene algunas ventajas sobre el que se muestra en la pregunta. En primer lugar, calcula el tamaño correcto del cambio, en lugar de estar codificado para entradas de 32 bits. Segundo, con la mayoría de los comstackdores podemos esperar que toda la multiplicación ocurra en tiempo de comstackción, por lo que todo lo que queda en el tiempo de ejecución es la manipulación de bits triviales (restar y desplazar) seguido de una carga y retorno. En resumen, es casi seguro que sea bastante rápido, incluso en el microcontrolador más pequeño, donde el original usó la multiplicación que tenía que ocurrir en el tiempo de ejecución, así que aunque probablemente sea bastante rápido en una máquina de escritorio, a menudo será bastante un poco más lento en un microcontrolador pequeño.

Esto es lo que esas líneas están haciendo:

c es ab. si c es negativo, a

k es el 32º bit de c, que es el bit de signo de c (suponiendo enteros de 32 bits. Si se hace en una plataforma con enteros de 64 bits, este código no funcionará). Se desplazó 31 bits hacia la derecha para eliminar los 31 bits más a la derecha, dejando el bit de signo en el lugar más derecho y luego yendo con 1 para eliminar todos los bits a la izquierda (que se rellenarán con 1 si c es negativo). Entonces k será 1 si c es negativo y 0 si c es positivo.

Entonces max = a – k * c. Si c es 0, esto significa a> = b, entonces max es a – 0 * c = a. Si c es 1, esto significa que a

En general, solo usa el signo de la diferencia para evitar el uso de operaciones mayores o menores que. Honestamente, es un poco tonto decir que este código no usa una comparación. c es el resultado de comparar ay b. El código simplemente no usa un operador de comparación. Podría hacer algo similar en muchos códigos de ensamblaje simplemente restando los números y luego saltando en función de los valores establecidos en el registro de estado.

También debo agregar que todas estas soluciones están asumiendo que los dos números son enteros. Si son flotadores, dobles o algo más complicado (BigInts, números Rational, etc.), entonces realmente tiene que usar un operador de comparación. Los trucos de bits generalmente no servirán para eso.

Función getMax () sin ninguna operación lógica.

 int getMax(int a, int b){ return (a+b+((ab)>>sizeof(int)*8-1|1)*(ab))/2; } 

Explicación:

Vamos a romper el ‘máximo’ en pedazos,

 max = ( max + max ) / 2 = ( max + (min+differenceOfMaxMin) ) / 2 = ( max + min + differenceOfMaxMin ) / 2 = ( max + min + | max - min | ) ) / 2 

Entonces la función debería verse así:

 getMax(a, b) = ( a + b + absolute(a - b) ) / 2 

Ahora,

 absolute(x) = x [if 'x' is positive] or -x [if 'x' is negative] = x * ( 1 [if 'x' is positive] or -1 [if 'x' is negative] ) 

En número positivo entero, el primer bit (bit de signo) es- 0 ; en negativo es- 1 . Al desplazar los bits hacia la derecha (>>) se puede capturar el primer bit.

Durante el cambio a la derecha, el espacio vacío se llena con el bit de signo. Entonces 01110001 >> 2 = 00011100 , mientras que 10110001 >> 2 = 11101100 .

Como resultado, para un número de 8 bits, el desplazamiento de 7 bits producirá -1 1 1 1 1 1 1 [0 o 1] para negativo, o 0 0 0 0 0 0 0 [0 o 1] para positivo.

Ahora, si la operación OR se realiza con 00000001 (= 1) , el número negativo rinde- 11111111 (= -1) y positivo- 00000001 (= 1) .

Asi que,

 absolute(x) = x * ( 1 [if 'x' is positive] or -1 [if 'x' is negative] ) = x * ( ( x >> (numberOfBitsInInteger-1) ) | 1 ) = x * ( ( x >> ((numberOfBytesInInteger*bitsInOneByte) - 1) ) | 1 ) = x * ( ( x >> ((sizeOf(int)*8) - 1) ) | 1 ) 

Finalmente,

 getMax(a, b) = ( a + b + absolute(a - b) ) / 2 = ( a + b + ((ab) * ( ( (ab) >> ((sizeOf(int)*8) - 1) ) | 1 )) ) / 2 

static int mymax (int a, int b)

  { int[] arr; arr = new int[3]; arr[0] = b; arr[1] = a; arr[2] = a; return arr[Math.Sign(a - b) + 1]; } 

Si b> a, entonces (ab) será negativo, el signo devolverá -1, al sumr 1 obtenemos el índice 0 que es b, si b = a, entonces ab será 0, +1 dará 1 índice por lo que no importa si estamos devolviendo a o b, cuando a> b, entonces ab será positivo y el signo devolverá 1, sumndo 1 obtenemos el índice 2 donde a se almacena.

 #include main() { int num1,num2,diff; printf("Enter number 1 : "); scanf("%d",&num1); printf("Enter number 2 : "); scanf("%d",&num2); diff=num1-num2; num1=abs(diff); num2=num1+diff; if(num1==num2) printf("Both number are equal\n"); else if(num2==0) printf("Num2 > Num1\n"); else printf("Num1 > Num2\n"); } 

El código que estoy proporcionando es para encontrar el máximo entre dos números, los números pueden ser de cualquier tipo de datos (entero, flotante). Si los números ingresados ​​son iguales, la función devuelve el número.

 double findmax(double a, double b) { //find the difference of the two numbers double diff=ab; double temp_diff=diff; int int_diff=temp_diff; /* For the floating point numbers the difference contains decimal values (for example 0.0009, 2.63 etc.) if the left side of '.' contains 0 then we need to get a non-zero number on the left side of '.' */ while ( (!(int_diff|0)) && ((temp_diff-int_diff)||(0.0)) ) { temp_diff = temp_diff * 10; int_diff = temp_diff; } /* shift the sign bit of variable 'int_diff' to the LSB position and find if it is 1(difference is -ve) or 0(difference is +ve) , then multiply it with the difference of the two numbers (variable 'diff') then subtract it with the variable a. */ return a- (diff * ( int_diff >> (sizeof(int) * 8 - 1 ) & 1 )); } 

Descripción

  • Lo primero que hace la función es que los argumentos sean dobles y que el tipo de retorno sea doble. La razón de esto es que para crear una función única que puede encontrar el máximo para todos los tipos. Cuando se proporcionan números de tipo entero o uno es un número entero y otro es el punto flotante, también debido a la conversión implícita, la función se puede utilizar para encontrar el máximo para los enteros también.
  • La lógica básica es simple, digamos que tenemos dos números a y b si ab> 0 (es decir, la diferencia es positiva) entonces a es el máximo si ab == 0 entonces ambos son iguales y si ab <0 (es decir, diff es - ve) b es máximo.
  • El bit de signo se guarda como el bit más significativo (MSB) en la memoria. Si MSB es 1 y viceversa. Para verificar si MSB es 1 o 0, cambiamos el MSB a la posición LSB y Bitwise & con 1, si el resultado es 1, entonces el número es -ve else no. es + ve. Este resultado se obtiene mediante la statement:

    int_diff >> (sizeof (int) * 8 – 1) & 1

Aquí para obtener el bit de signo del MSB al LSB lo desplazamos a la derecha a k-1 bits (donde k es el número de bits necesarios para guardar un número entero en la memoria que depende del tipo de sistema). Aquí k = sizeof (int) * 8 como sizeof () da la cantidad de bytes necesarios para guardar un entero para obtener no. de bits, lo multiplicamos por 8. Después del cambio a la derecha, aplicamos el bit a bit y con 1 para obtener el resultado.

  • Ahora después de obtener el resultado (supongamos que como r) como 1 (para -ve diff) y 0 (para + ve diff) multiplicamos el resultado con la diferencia de los dos números, la lógica se da de la siguiente manera:

    1. si a> b entonces ab> 0 es decir, es + ve entonces el resultado es 0 (es decir, r = 0). Entonces a- (ab) * r => a- (ab) * 0, que da ‘a’ como el máximo.
    2. si a a- (ab) * 1 => a-a + b => b, que da ‘b’ como el máximo.
  • Ahora hay dos puntos restantes 1. el uso de while loop y 2. por qué he usado la variable ‘int_diff’ como un entero. Para responderlas adecuadamente, debemos entender algunos puntos:

    1. Los valores de tipo flotante no se pueden usar como un operando para los operadores bit a bit.
    2. Debido a la razón anterior, necesitamos obtener el valor en un valor entero para obtener el signo de la diferencia mediante el uso de operadores bit a bit. Estos dos puntos describen la necesidad de la variable ‘int_diff’ como tipo entero.
    3. Ahora digamos que encontramos la diferencia en la variable ‘diff’ ahora hay 3 posibilidades para los valores de ‘diff’ independientemente del signo de estos valores. (un). | diff |> = 1, (b). 0 < | diff | <1, (c). | diff | == 0.
    4. Cuando asignamos un valor doble a la variable entera, la parte decimal se pierde.
    5. Para el caso (a) el valor de ‘int_diff’> 0 (es decir, 1,2, …). Para otros dos casos int_diff = 0.
    6. La condición (temp_diff-int_diff) || 0.0 comprueba si diff == 0, por lo que ambos números son iguales.
    7. Si diff! = 0, comprobamos si int_diff | 0 es verdadero, es decir, el caso (b) es verdadero
    8. En el ciclo while, tratamos de obtener el valor de int_diff como distinto de cero para que el valor de int_diff también obtenga el signo de diff.

Aquí hay un par de métodos poco comunes para obtener el máximo de dos valores integrales:

Método 1

 int max1(int a, int b) { static const size_t SIGN_BIT_SHIFT = sizeof(a) * 8 - 1; int mask = (a - b) >> SIGN_BIT_SHIFT; return (a & ~mask) | (b & mask); } 

Explicación:

  • (a – b) >> SIGN_BIT_SHIFT – Si a > b entonces a - b es positivo, entonces el bit de signo es 0 , y la máscara es 0x00.00 . De lo contrario, a < b so a - b es negativo, el bit de signo es 1 y después del cambio, obtenemos una máscara de 0xFF..FF
  • (a & ~ mask) - Si la máscara es 0xFF..FF , entonces ~mask es 0x00..00 y luego este valor es 0 . De lo contrario, ~mask es 0xFF..FF y el valor es
  • (b & máscara) - Si la máscara es 0xFF..FF , entonces este valor es b . De lo contrario, la mask es 0x00..00 y el valor es 0 .

Finalmente:

  • Si a >= b entonces a - b es positivo, obtenemos max = a | 0 = a max = a | 0 = a
  • Si a < b entonces a - b es negativo, obtenemos max = 0 | b = b max = 0 | b = b

Método 2

 int max2(int a, int b) { static const size_t SIGN_BIT_SHIFT = sizeof(a) * 8 - 1; int mask = (a - b) >> SIGN_BIT_SHIFT; return a ^ ((a ^ b) & mask); } 

Explicación:

  • La explicación de la máscara es la misma que para el Método 1 . Si a > b la máscara es 0x00..00 , de lo contrario, la máscara es 0xFF..FF
  • Si la máscara es 0x00..00 , entonces (a ^ b) & mask es 0x00..00
  • Si la máscara es 0xFF..FF , entonces (a ^ b) & mask es a ^ b

Finalmente:

  • Si a >= b , obtenemos a ^ 0x00..00 = a
  • Si a < b , obtenemos a ^ a ^ b = b

La lógica que se describe en un problema puede explicarse como si el 1er. Número es más pequeño que 0 será restado, de lo contrario la diferencia se restará del 1er número para obtener el 2 ° número. Encontré una solución matemática más que creo que es un poco más simple de entender este concepto.

Teniendo en cuenta a y b como números dados

 c=|a/b|+1; d=(c-1)/b; smallest number= a - d*(ab); 

De nuevo, la idea es encontrar k que es marchitar 0 o 1 y multiplicarlo con la diferencia de dos números. Y finalmente este número debe restarse del 1er número para dar el menor de los dos números. PS esta solución fallará en caso de que el segundo número sea cero

 int a=151; int b=121; int k=Math.abs(ab); int j= a+b; double k1=(double)(k); double j1= (double) (j); double c=Math.ceil(k1/2) + Math.floor(j1/2); int c1= (int) (c); System.out.println(" Max value = " + c1); 

(a / b) * b + (b / a) * a – (a / b) * (b / a) * a + (abs (a – b)% a)% b

Hay una manera

  public static int Min(int a, int b) { int dif = (int)(((uint)(a - b)) >> 31); return a * dif + b * (1 - dif); } 

y uno

 return (a>=b)?b:a; 

Supongo que podemos simplemente multiplicar los números con sus comparaciones bit a bit, por ejemplo:

 int max=(a>b)*a+(a< =b)*b;