C rompecabezas de operación de bit

/* 
* ezThreeFourths - multiplies by 3/4 rounding toward 0, 
* Should exactly duplicate effect of C expression (x*3/4), 
* including overflow behavior. 
* Examples: ezThreeFourths(11) = 8 
*    ezThreeFourths(-9) = -6 
*    ezThreeFourths(1073741824) = -268435456 (overflow) 
* Legal ops: ! ~ &^| + << >> 
* Max ops: 12 
* Rating: 3 
*/ 

int ezThreeFourths(int x) { 
    int z = x+x+x; 
    int sign_z = z>>31; 
    return ((z>>2)&(~sign_z)) + (((z>>2)+1)&sign_z); 
}

me trató de resolver este rompecabezas, peroC rompecabezas de operación de bit

 

ERROR: Test ezThreeFourths(-2147483648[0x80000000]) failed... 
...Gives -536870911[0xe0000001]. Should be -536870912[0xe0000000]

compilado con gcc (GCC) 4.1.2 20080704 (Red Hat 4.1.2-51)

¿Qué hay de malo ¿esta solución?

Fuente

2012-02-08 user1114371

Hm ... Ejecuté una prueba con este código en mi pc y tengo que decir que parece estar funcionando para los casos de prueba y los ejemplos que dio aquí. Incluso obtengo el resultado correcto para 2147483647 – Lefteris

¿Qué compilador estás usando? –

¿Lo descompusiste para ver todos los valores intermedios? – EboMike

me da buenos resultados usando Embarcadero C++ 6.43:

// x = 2147483647 
int ezThreeFourths(int x) 
{ 
    int z = x+x+x; 
    // z = 2147483645 (6442450941[0x17FFFFFFD] truncated to 32-bits!) 

    int sign_z = z>>31; 
    // sign_z = (2147483645 >> 31) = 0 

    return ((z>>2)&(~sign_z)) + (((z>>2)+1)&sign_z); 
    // = ((2147483645 >> 2) & (~0)) + (((2147483645 >> 2) + 1) & 0) 
    // = (536870911 & 0xFFFFFFFF) + ((536870911+1) & 0) 
    // = (536870911 & 0xFFFFFFFF) + (536870912 & 0) 
    // = (536870911 & 0xFFFFFFFF) + 0 
    // = (536870911 & 0xFFFFFFFF) 
    // = 536870911 
}

Fuente

2012-02-08 03:05:39

Su enfoque para la fabricación de los números negativos vuelta hacia cero no está funcionando correctamente en el caso de valores de entrada que dividen uniformemente por 4. 0x80000000 es un ejemplo de ello , pero tal vez sea más fácil ver el problema si lo intenta con un valor pequeño.

Por ejemplo: ezThreeFourths (-8) = -5 [debe ser -6]

Fuente

2012-02-08 05:58:05

Aquí es lo que hice:

#include <stdio.h> 
#include <limits.h> 

int ThreeFourths(int x) 
{ 
    int x3 = x + x + x; 
    return (x3 >= 0) ? (x3 >> 2) : -(int)((UINT_MAX - x3 + 1) >> 2); 
} 

int testData[] = 
{ 
    0, 
    1, 
    -1, 
    2, 
    -2, 
    3, 
    -3, 
    4, 
    -4, 
    5, 
    -5, 
    -9, 
    11, 
    INT_MAX/2 + 1, 
    INT_MIN 
}; 

int main(void) 
{ 
    int i; 

    for (i = 0; i < sizeof(testData)/sizeof(testData[0]); i++) 
    { 
    printf("  %d * 3/4 = %d\n", 
      testData[i], testData[i] * 3/4); 
    printf("ThreeFourths(%d) = %d\n", 
      testData[i], ThreeFourths(testData[i])); 
    } 
    return 0; 
}

Salida:

 0 * 3/4 = 0 
ThreeFourths(0) = 0 
     1 * 3/4 = 0 
ThreeFourths(1) = 0 
     -1 * 3/4 = 0 
ThreeFourths(-1) = 0 
     2 * 3/4 = 1 
ThreeFourths(2) = 1 
     -2 * 3/4 = -1 
ThreeFourths(-2) = -1 
     3 * 3/4 = 2 
ThreeFourths(3) = 2 
     -3 * 3/4 = -2 
ThreeFourths(-3) = -2 
     4 * 3/4 = 3 
ThreeFourths(4) = 3 
     -4 * 3/4 = -3 
ThreeFourths(-4) = -3 
     5 * 3/4 = 3 
ThreeFourths(5) = 3 
     -5 * 3/4 = -3 
ThreeFourths(-5) = -3 
     -9 * 3/4 = -6 
ThreeFourths(-9) = -6 
     11 * 3/4 = 8 
ThreeFourths(11) = 8 
     1073741824 * 3/4 = -268435456 
ThreeFourths(1073741824) = -268435456 
     -2147483648 * 3/4 = -536870912 
ThreeFourths(-2147483648) = -536870912

La razón por la que no usar los cambios a la derecha en enteros negativos es simple. El resultado de estos cambios está definido por la implementación (según el estándar C) y no se garantiza que sea el mismo que el cambio a la derecha con extensión de signo que podríamos esperar debido a que es la implementación más común.

escribí (UINT_MAX - x3 + 1) en lugar de simplemente -x3, ya que puede dar lugar a un desbordamiento firmado (cuando = INT_MIN que es una potencia menos de 2), que ha indefinido comportamiento (por el estándar de C, de nuevo). E incluso si se sabe que este comportamiento indefinido es inofensivo, la negación simple aún no puede producir un número positivo (debido a la asimetría en la representación del complemento a 2 de los enteros con signo).

x + x + x todavía puede producir desbordamiento firmado como x * 3 puede. Entonces, este es el mismo comportamiento indefinido.

Por cierto, dado que los desbordamientos firmados dan como resultado UB, ni siquiera debería pedírsele legalmente que los consiga, y mucho menos tener expectativas específicas sobre los resultados cuando ocurra el UB.

Fuente

2012-02-08 08:03:39

int ezThreeFourths(int x) { 


    int z = x+x+x; 
    int sign_z = z>>31; 


    return ((z>>2)&(~sign_z)) + (((z>>2)+1)&sign_z); 

}

Funciona con números no negativos. Además, no debe mentir sobre code "you" wrote. Teniendo en cuenta el código exacto fue escrito en "2008-01-26"

Fuente

2012-02-08 13:29:06

C rompecabezas de operación de bit

Respuesta

Cuestiones relacionadas