La sustitución de «==» con operadores bit a bit

Utilizando sólo los operadores bit a bit (|, &, ~, ^, >>, <<) y otros operadores como +, -, e !, es posible reemplazar el «==» a continuación?

int equal(int x, int y) {
    return x == y;
}
  • Esto es sobre todo para entender lo que realmente está pasando con «==» para ver cómo el equipo se ve en el «==» en un bit a bit de nivel y para saber si similar, los operadores pueden replicar de la misma manera.
  • «La tarea de la etiqueta…ahora es desanimado,» pero, @not_l33t, por favor (como siempre) siga directrices generales: estado de cualquier restricción especial, mostrar lo que he probado hasta ahora, y preguntar acerca de qué es exactamente lo que confundirlo.
  • ¿Cuáles son los requisitos que se acerque a una int límites? I. e. INT_MAX, INT_MIN? O sólo se tiene que trabajar para mucho más pequeña de la gama?
  • Soy bastante nuevo en la programación, y la pregunta es más para entender cómo funciona. Con esto en mente, sería ideal tener un límite infinito, aunque estoy empezando a ver que no podría realmente ser posible para mí para averiguar (bit a bit de la manipulación de las obras, porque de los 32 bits de la cadena).
  • Me gustaría mencionar para cualquier persona tratando de utilizar las operaciones bit a bit como un aumento de rendimiento que al menos en chrome 61 hay poca o ninguna diferencia entre regulares iguales y bit a bit es igual a métodos. jsperf.com/bitwise-equal/1
InformationsquelleAutor not_l33t | 2010-11-12

6 Kommentare

  1. 22

    Dos números son iguales si no hay ninguna diferencia entre ellos:

    int equal(int x, int y){
       return !(x-y);
    }
    • Me gusta este enfoque. +1
    • Aunque no es realmente el uso de un operador bit a bit.
    • Pero se utiliza un «BÁSICO» operador 🙂
    • He utilizado este método en combinación con otro método (la negación de una variable). de esa manera, yo podría utilizar un + en su lugar, lo que es más cerca de lo que la computadora lee. por lo tanto lo que es más rápido?
    • int igual(int x, int y){ return !((!x+1)+y); }
    • esto puede invocar un comportamiento indefinido si el resultado de x-y no puede ser representado en int

  2. 68

    Recuerde que un XOR es exactamente el mismo que NOT EQUALS y XNOR es exactamente el mismo que EQUALS. Así, el siguiente le dará exactamente lo que usted desea:

    return !(x ^ y);
    • Usted es la combinación de bit a bit con operadores lógicos aquí, que puede ser confuso.
    • Es mejor que la aceptación de la solución, ya que por definición XOR es más rápido que AGREGAR (add tener para el transporte de acarreo, por lo que no es muy escalable).
    • lo que si x e y ambos son ceros
    • Eh? 0 XOR 0 es igual a 0, como si x e y eran cualquier otro número del mismo.
  3. 14

    La C ! operador es en realidad la abreviatura de != 0, por lo que se utiliza parece muy cerca de la trampa 🙂

    Aquí está mi toma, utilizando sólo las operaciones bit a bit, suponiendo que una de 32 bits en complemento a dos de la máquina con aritmético a la derecha turnos (técnicamente, en C aritmético a la derecha de los turnos indefinido, pero cada compilador de C que he visto nunca en un complemento a dos de la máquina admite este correctamente):

    int t = (x - y) | (y - x); //<0 iff x != y, 0 otherwise
    t >>= 31; //-1 iff x != y, 0 otherwise
    return 1 + t; //0 iff x != y, 1 otherwise

    Que dijo, real compiladores no tienen este problema. Hardware Real en realidad tiene soporte directo para las comparaciones. Los detalles dependen de la arquitectura, pero hay dos modelos básicos:

    1. Condición de códigos devueltos para las operaciones aritméticas (por ejemplo, x86 y ARM hacer esto). En este caso, por lo general hay un «comparar» la instrucción que resta de dos valores, no volver a escribir un entero registrarse, pero establece el código de condición/indicadores basados en el resultado.
    2. Más RISC como plataformas suelen tener directa rama «si la igualdad» y «rama, si es menor de» los operandos que hacer una comparación de rama y basado en el resultado. Es básicamente equivalente a la C código

      if (a == b) goto label;

      o

      if (a < b) goto label;

      todos en una instrucción de máquina.

    • excelente ejemplo! pero, ¿por qué simplemente no uso «de retorno de t < 0 ? false : true» (si se asume el método booleano)?
    • Como yo lo entiendo, el OP excluye de ramificación
  4. 3

    Este ejemplo es igual a la resta, pero es más explícita en cuanto a cómo algunas arquitecturas de hacer el registro de comparación (como el BRAZO, creo).

    return !(1 + ~x + y);

    El 1 significa el llevar bits de entrada en la ALU. Un número x es bit a bit complementa. Tomando el complemento y la adición de 1 produce el complemento a dos del número (x se convierte en -x) y, a continuación, se añade a otro número para obtener la diferencia para determinar la igualdad.

    Por lo que si ambos números son iguales, se obtiene -x + x => 0.

    (A nivel de registro de la ! operador no está hecho, y que acaba de probar el «bit cero» de la condición de los códigos o marcas de registro, el cual se establece si el registro de la operación produce un resultado de cero, y es evidente lo contrario.)

  5. 1

    Como XOR es el mismo (!=), por lo tanto (x ^ y) devolverá 0 sólo para la igualdad de valores.
    Mi opinión es la siguiente, porque es sensible, utiliza bit a bit de operador y de trabajo.

    int notEqual(int x, int y){
            return (x ^ y);
    }
  6. 0

    Mi opinión sobre este

    int equal(int x, int y){
       if((x & ~y) == 0)
           return 1;
       else
           return 0; 
    }

    Explicación: Si x == y, entonces x & ~y evalúa a 0 de retorno de 1, de lo contrario devuelve 0 como x!=y.

    Edit1: The above is equivalent to 
    
    int equal(int x, int y){
        return !(x & ~y) ; //returns 1 if equal , 0 otherwise. 
    }

    El código anterior produce un error en ciertos casos donde el bit Más significativo se convierte en 1. La solución es añadir un 1. yo.e la respuesta correcta es

    return !(x & (~y +1) );
    • Dos problemas. 1) Esto comprueba si y tiene todos los mismos bits que x conjunto, no que x == y. 2) Usted está usando == aunque no es ni quería ni necesitaba.
    • 3) sólo tiene que volver en lugar de utilizar un if.
    • Sé que es viejo, pero ¿qué pasa si x es negativo? Digamos x = -1 y y = 0 entonces, ¿cómo debe if ( !( x & ( ~( y + 1 )) ) ) Trabajo ? ¿Y si x = -1 y y = -1? volver x ^ y:` debería funcionar.

Kommentieren Sie den Artikel

Bitte geben Sie Ihren Kommentar ein!
Bitte geben Sie hier Ihren Namen ein

Pruebas en línea