C operazione po 'di puzzle

Question

/* 
* 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); 
} 

ho cercato di risolvere questo enigma, ma

 

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

compilato con gcc (GCC) 4.1.2 20.080.704 (Red Hat 4.1.2-51)

Cosa c'è di sbagliato con questa soluzione?

Answer 1

funziona bene per me 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 
} 

Answer 2

vostro approccio per rendere i numeri negativi tutto a zero non funziona correttamente nel caso di valori di ingresso che dividono uniformemente 4. 0x80000000 è un esempio , ma forse è più facile vedere il problema se provi con un piccolo valore.

Ad esempio: ezThreeFourths (-8) = -5 [dovrebbe essere -6]

Answer 3

Ecco quello che ho fatto:

#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; 
} 

uscita:

 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 

Il motivo per cui non ha usato i turni giusti sugli interi negativi è semplice. Il risultato di questi spostamenti è definito dall'implementazione (secondo lo standard C) e non è garantito che sia lo stesso di un passaggio a destra con estensione di segno che potremmo aspettarci perché è l'implementazione più comune.

ho scritto (UINT_MAX - x3 + 1) invece di limitarsi a -x3 perché può causare un overflow firmato (quando = INT_MIN che è una potenza meno di 2), che ha undefined comportamento (per lo standard C, ancora una volta). E anche se questo comportamento indefinito è noto per essere innocuo, la semplice negazione potrebbe ancora non riuscire a produrre un numero positivo (a causa dell'asimmetria nella rappresentazione del complemento a 2 degli interi con segno).

x + x + x può ancora produrre overflow con segno proprio come x * 3 can. Quindi, questo è lo stesso comportamento indefinito.

Btw, dal momento che gli overflow firmati risultano in UB, non dovrebbe nemmeno essere richiesto legalmente da te per raggiungerli, per non parlare delle aspettative specifiche sui risultati quando UB si verifica.

Answer 4

int ezThreeFourths(int x) { 


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


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

} 

Funziona con numeri non negativi. Inoltre non dovresti mentire su code "you" wrote. Considerando il codice esatto è stato scritto in "2008-01-26"