operadores - Operaciones bitwise equivalentes a mayor que operador
bitwise operators python (8)
Estoy trabajando en una función que esencialmente verá cuál de dos ints es más grande. Los parámetros que se pasan son 2 ints de 32 bits. El truco es que los únicos operadores permitidos son ! ~ | & << >> ^ ! ~ | & << >> ^ ! ~ | & << >> ^ (sin conversión, otros tipos de datos además de int firmado, *, /, -, etc.).
Mi idea hasta ahora es ^ los dos binarios juntos para ver todas las posiciones de los 1 valores que no comparten. Lo que quiero hacer es tomar ese valor y aislar el 1 más a la izquierda. A continuación, ver de cuál de ellos tiene ese valor en él. Ese valor entonces será el más grande. (Supongamos que utilizamos ints de 8 bits en lugar de 32 bits). Si los dos valores pasados fueron 01011011 y 01101001 , usé ^ en ellos para obtener 00100010 . Entonces quiero hacerlo 00100000 en otras palabras 01xxxxxx -> 01000000 Entonces & con el primer número !! El resultado y devolverlo. Si es 1 , entonces el primer # es más grande.
¿Alguna idea sobre cómo 01xxxxxx -> 01000000 o algo más para ayudar?
Se olvidó de tener en cuenta: no ifs, whiles, fors etc ...
EDITAR:
Bueno, hubo algunos problemas con el código, pero lo revisé y los siguientes trabajos.
Esta función auxiliar compara el dígito significativo de los números ''n'':
int compare ( int a, int b, int n )
{
int digit = (0x1 << n-1);
if ( (a & digit) && (b & digit) )
return 0; //the digit is the same
if ( (a & digit) && !(b & digit) )
return 1; //a is greater than b
if ( !(a & digit) && (b & digit) )
return -1; //b is greater than a
}
Lo siguiente debe devolver recursivamente el número más grande:
int larger ( int a, int b )
{
for ( int i = 8*sizeof(a) - 1 ; i >= 0 ; i-- )
{
if ( int k = compare ( a, b, i ) )
{
return (k == 1) ? a : b;
}
}
return 0; //equal
}
Aquí hay una versión sin bucles que compara enteros sin signo en operaciones O (lg b) donde b es el tamaño de palabra de la máquina. Tenga en cuenta que el OP no indica ningún otro tipo de datos que el signed int , por lo que parece probable que la parte superior de esta respuesta no cumpla las especificaciones del OP. (Versión Spoiler como en la parte inferior.)
Tenga en cuenta que el comportamiento que queremos capturar es cuando la falta de coincidencia de bits más significativa es 1 para b 0 para b . Otra forma de pensar acerca de esto es que cualquier bit en a ser más grande que el bit correspondiente en b significa que a es mayor que b , siempre que no haya un bit anterior en a que sea menor que el bit correspondiente en b .
Para ese fin, calculamos todos los bits en mayor que los bits correspondientes en b , y de la misma manera calculamos todos los bits en menor que los bits correspondientes en b . Ahora queremos enmascarar todos los bits "mayores que" que están por debajo de cualquier bit "inferior a", por lo que tomamos todos los bits "menores que" y los difuminamos todos a la derecha para crear una máscara: el bit más significativo establece todos el camino hasta el bit menos significativo ahora es 1 .
Ahora todo lo que tenemos que hacer es eliminar los bits "mayores que" establecidos mediante el uso de una lógica de enmascaramiento de bits simple.
El valor resultante es 0 si a <= b y distinto de cero si a > b . Si queremos que sea 1 en el último caso, podemos hacer un truco similar y solo echar un vistazo al bit menos significativo.
#include <stdio.h>
// Works for unsigned ints.
// Scroll down to the "actual algorithm" to see the interesting code.
// Utility function for displaying binary representation of an unsigned integer
void printBin(unsigned int x) {
for (int i = 31; i >= 0; i--) printf("%i", (x >> i) & 1);
printf("/n");
}
// Utility function to print out a separator
void printSep() {
for (int i = 31; i>= 0; i--) printf("-");
printf("/n");
}
int main()
{
while (1)
{
unsigned int a, b;
printf("Enter two unsigned integers separated by spaces: ");
scanf("%u %u", &a, &b);
getchar();
printBin(a);
printBin(b);
printSep();
/************ The actual algorithm starts here ************/
// These are all the bits in a that are less than their corresponding bits in b.
unsigned int ltb = ~a & b;
// These are all the bits in a that are greater than their corresponding bits in b.
unsigned int gtb = a & ~b;
ltb |= ltb >> 1;
ltb |= ltb >> 2;
ltb |= ltb >> 4;
ltb |= ltb >> 8;
ltb |= ltb >> 16;
// Nonzero if a > b
// Zero if a <= b
unsigned int isGt = gtb & ~ltb;
// If you want to make this exactly ''1'' when nonzero do this part:
isGt |= isGt >> 1;
isGt |= isGt >> 2;
isGt |= isGt >> 4;
isGt |= isGt >> 8;
isGt |= isGt >> 16;
isGt &= 1;
/************ The actual algorithm ends here ************/
// Print out the results.
printBin(ltb); // Debug info
printBin(gtb); // Debug info
printSep();
printBin(isGt); // The actual result
}
}
Nota: Esto también debería funcionar para enteros con signo si invierte el bit superior en ambas entradas, por ejemplo, a ^= 0x80000000 .
Alerón
Si desea una respuesta que cumpla con todos los requisitos (incluidos 25 operadores o menos):
int isGt(int a, int b)
{
int diff = a ^ b;
diff |= diff >> 1;
diff |= diff >> 2;
diff |= diff >> 4;
diff |= diff >> 8;
diff |= diff >> 16;
diff &= ~(diff >> 1) | 0x80000000;
diff &= (a ^ 0x80000000) & (b ^ 0x7fffffff);
return !!diff;
}
Me iré explicando por qué te funciona.
Creo que tengo una solución con 3 operaciones:
Suma uno al primer número, restalo del mayor número posible que puedas representar (todos los 1). Agregue ese número al segundo número. Si se desborda, entonces el primer número es menor que el segundo.
No estoy 100% seguro de si esto es correcto. Es posible que no necesite agregar 1, y no sé si es posible verificar el desbordamiento (si no es así, simplemente reserve el último bit y pruebe si es 1 al final).
EDITAR: Las restricciones hacen que el enfoque simple en la parte inferior no sea válido. Estoy agregando la función de búsqueda binaria y la comparación final para detectar el mayor valor:
unsigned long greater(unsigned long a, unsigned long b) {
unsigned long x = a;
unsigned long y = b;
unsigned long t = a ^ b;
if (t & 0xFFFF0000) {
x >>= 16;
y >>= 16;
t >>= 16;
}
if (t & 0xFF00) {
x >>= 8;
y >>= 8;
t >>= 8;
}
if (t & 0xf0) {
x >>= 4;
y >>= 4;
t >>= 4;
}
if ( t & 0xc) {
x >>= 2;
y >>= 2;
t >>= 2;
}
if ( t & 0x2) {
x >>= 1;
y >>= 1;
t >>= 1;
}
return (x & 1) ? a : b;
}
La idea es comenzar con la mitad más significativa de la palabra que nos interesa y ver si hay algunos bits establecidos allí. Si los hay, entonces no necesitamos la mitad menos significativa, por lo que apartamos los bits no deseados. Si no, no hacemos nada (la mitad es cero de todos modos, por lo que no se interpondrá en el camino). Ya que no podemos hacer un seguimiento de la cantidad cambiada (requeriría una suma), también cambiamos los valores originales para que podamos hacer la final and para determinar el número mayor. Repetimos este proceso con la mitad del tamaño de la máscara anterior hasta que colapsamos los bits interesantes en la posición de bit 0.
No agregué el caso igual aquí a propósito.
Respuesta antigua:
El método más simple es probablemente el mejor para una tarea. Una vez que tenga el valor de bit de discordancia, comience con otra máscara en 0x80000000 (o la posición de bit máxima adecuada para su tamaño de palabra), y continúe desplazándola a la derecha hasta que alcance un bit que se establece en su valor de discordancia. Si su cambio a la derecha termina con 0, entonces el valor de la falta de coincidencia es 0.
Supongo que ya sabe el paso final necesario para determinar el número más grande.
Para convertir 001xxxxx a 00100000 , primero ejecuta:
x |= x >> 4;
x |= x >> 2;
x |= x >> 1;
(esto es para 8 bits; para extenderlo a 32, agregue turnos de 8 y 16 al comienzo de la secuencia).
Esto nos deja con 00111111 (esta técnica a veces se llama " 00111111 bits"). Luego podemos cortar todos menos el primer bit 1:
x ^= x >> 1;
dejándonos con 00100000 .
Por mucho que no quiera hacer la tarea de otra persona, no pude resistirme a esta ... :) Estoy seguro de que otros pueden pensar en una más compacta ... pero aquí está la mía ... funciona bien, incluidos los números negativos. .
Edición: hay un par de errores sin embargo. Lo dejaré al OP para que lo encuentre y lo arregle.
#include<unistd.h>
#include<stdio.h>
int a, b, i, ma, mb, a_neg, b_neg, stop;
int flipnum(int *num, int *is_neg) {
*num = ~(*num) + 1;
*is_neg = 1;
return 0;
}
int print_num1() {
return ((a_neg && printf("bigger number %d/n", mb)) ||
printf("bigger number %d/n", ma));
}
int print_num2() {
return ((b_neg && printf("bigger number %d/n", ma)) ||
printf("bigger number %d/n", mb));
}
int check_num1(int j) {
return ((a & j) && print_num1());
}
int check_num2(int j) {
return ((b & j) && print_num2());
}
int recursive_check (int j) {
((a & j) ^ (b & j)) && (check_num1(j) || check_num2(j)) && (stop = 1, j = 0);
return(!stop && (j = j >> 1) && recursive_check(j));
}
int main() {
int j;
scanf("%d%d", &a, &b);
ma = a; mb = b;
i = (sizeof (int) * 8) - 1;
j = 1 << i;
((a & j) && flipnum(&a, &a_neg));
((b & j) && flipnum(&b, &b_neg));
j = 1 << (i - 1);
recursive_check(j);
(!stop && printf("numbers are same../n"));
}
Una variante sin firmar dado que se puede usar lógico (&&, ||) y comparación (! =, ==).
int u_isgt(unsigned int a, unsigned int b)
{
return a != b && ( /* If a == b then a !> b and a !< b. */
b == 0 || /* Else if b == 0 a has to be > b (as a != 0). */
(a / b) /* Else divide; integer division always truncate */
); /* towards zero. Giving 0 if a < b. */
}
!= y == pueden ser eliminados fácilmente, es decir:
int u_isgt(unsigned int a, unsigned int b)
{
return a ^ b && (
!(b ^ 0) ||
(a / b)
);
}
Para los firmados se puede expandir a algo como:
int isgt(int a, int b)
{
return
(a != b) &&
(
(!(0x80000000 & a) && 0x80000000 & b) || /* if a >= 0 && b < 0 */
(!(0x80000000 & a) && b == 0) ||
/* Two more lines, can add them if you like, but as it is homework
* I''ll leave it up to you to decide.
* Hint: check on "both negative" and "both not negative". */
)
;
}
Puede ser más compacto / eliminar operaciones. (al menos uno) pero ponlo así para mayor claridad.
En lugar de 0x80000000 se podría decir, por ejemplo:
#include <limits.h>
static const int INT_NEG = (1 << ((sizeof(int) * CHAR_BIT) - 1));
Usando esto para probar:
void test_isgt(int a, int b)
{
fprintf(stdout,
"%11d > %11d = %d : %d %s/n",
a, b,
isgt(a, b), (a > b),
isgt(a, b) != (a>b) ? "BAD!" : "OK!");
}
Resultado:
33 > 0 = 1 : 1 OK!
-33 > 0 = 0 : 0 OK!
0 > 33 = 0 : 0 OK!
0 > -33 = 1 : 1 OK!
0 > 0 = 0 : 0 OK!
33 > 33 = 0 : 0 OK!
-33 > -33 = 0 : 0 OK!
-5 > -33 = 1 : 1 OK!
-33 > -5 = 0 : 0 OK!
-2147483647 > 2147483647 = 0 : 0 OK!
2147483647 > -2147483647 = 1 : 1 OK!
2147483647 > 2147483647 = 0 : 0 OK!
2147483647 > 0 = 1 : 1 OK!
0 > 2147483647 = 0 : 0 OK!
Una versión completamente sin sucursales de la función isGt más pequeña de Kaganar podría verse así:
int isGt(int a, int b)
{
int diff = a ^ b;
diff |= diff >> 1;
diff |= diff >> 2;
diff |= diff >> 4;
diff |= diff >> 8;
diff |= diff >> 16;
//1+ on GT, 0 otherwise.
diff &= ~(diff >> 1) | 0x80000000;
diff &= (a ^ 0x80000000) & (b ^ 0x7fffffff);
//flatten back to range of 0 or 1.
diff |= diff >> 1;
diff |= diff >> 2;
diff |= diff >> 4;
diff |= diff >> 8;
diff |= diff >> 16;
diff &= 1;
return diff;
}
Esto incluye aproximadamente 60 instrucciones para el cálculo real (compilador MSVC 2010, en un arco x86), más 10 operaciones de pila adicionales o menos para el prólogo / epílogo de la función.