Il confronto tra due numeri interi, senza alcun confronto

È possibile trovare il più grande dei due numeri interi, senza alcun confronto? Ho trovato alcune soluzioni:

if(!(a/b)) //if a is less than b then division result will be zero.
{
    cout << " b is greater than a";
}
else if (!(a-b)) //we know a is greater than or equal to b now.  check whether they are equal.
{
    cout << "a and b are equal";
}
else
    cout << "a is greater than b";

Ma se(c) o se(!c) è un confronto a zero. Inoltre non funziona per i numeri negativi. In realtà ho bisogno di una soluzione che evita qualsiasi istruzione if. Invece devo utilizzare le istruzioni di switch e gli operatori aritmetici. ThanX.

  • Perché è il mio lavoro!
  • … e questo è il motivo per cui la maggior parte delle cose che si imparano su di programmazione nella scuola oggi è inutile.
  • in realtà questo era un utile speedup hack quando ancora c’era nessun hw condizionale spostare. E non ricordo più se la Gpu ora il supporto em, così ci si può ancora essere necessario. Essere attenti nel valutare l’ignoranza 🙂
  • E oltre ad essere “scuola” problema di programmazione, questa è la domanda molto comune nella programmazione di interviste – quando vogliono vedere come la pensate.
  • Non si tratta di imparare a confrontare due numeri interi, senza alcun confronto. Si tratta di imparare come pensare a un problema. Estremamente utile.
InformationsquelleAutor Ameer Jewdaki | 2009-01-24



13 Replies
  1. 36

    Sottrarre loro e controllare il segno con brutte po ‘ con le mani in mano hack

    http://graphics.stanford.edu/~seander/bithacks.html

    Non fare questo nel codice di produzione se gli altri programmatori sapere dove si vive.

    • D’accordo con il finale ultima frase. Se questa è una buona idea per la vostra piattaforma, il compilatore dovrebbe fare questa ottimizzazione per voi 🙂
    • b ^ ( (((a-b)>>(sizeof(a)*8-1) & 1) – 1) & (a^b)) stavo per dire che un CS corso dovrebbe guardare sotto il compilatore, ma molte architetture di CPU MAX e MIN istruzioni comunque.
    • Confrontare questo MODO domanda: stackoverflow.com/questions/227383/…
    • Forse questi studenti potranno eventualmente essere iscritto compilatori ottimizzati?
    • Allora certamente bisogno di saperlo. Non mi piace nel codice di produzione dal momento che l’ottimizzazione è probabile che sia dipendente dall’architettura e la leggibilità è peggio a mio parere.
  2. 5

    Ecco un divertente bit-giocherellando versione che non ha condizionali.

    int g = (int)"greater";
    int l = (int)"less";
    int e = (int)"equal";
    
    int a = 7;
    int b = 10;
    
    char *result = (char*)((((a - b) >> 31) & l) | (((b - a) >> 31) & g) | ((~((a - b) | (b - a))) >> 31) & e);
    cout << result;
  3. 1

    Non uno dei campioni presentati nella domanda o per eventuali risposte finora protegge dalla divisione per zero. Perché sulla terra si sta cercando di evitare un ‘se’ istruzione? Ho il sospetto che i compiti domanda ?: operatori.

    cout << "Maximum is: " << ((a>b)?a:b)

    Ci siamo.

    Non è possibile confrontare due numeri senza un confronto. È possibile fondente e fare un indiretti di funzionamento, ma alla fine della giornata si sta confrontando qualcosa. Fiducia al compilatore di ottimizzare il codice e selezionare le migliori operazioni.

  4. 1

    Si potrebbe sfruttare il fatto che il segno del calcolo a - b dipende da quale numero è maggiore. Questo è usato in molte implementazioni di confronto. Ma credo che non sarai mai in grado di evitare completamente il confronto. In questo caso, è ancora necessario almeno per valutare il contenuto del segno bandiera sul processore.

    Se avete solo bisogno di visualizzare il numero più basso, è anche possibile utilizzare l’aritmetica trucchi:

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

    MODIFICA erm … ti è permesso di utilizzare switch?

    Dovrei usare le istruzioni switch e gli operatori aritmetici.

    switch è fondamentalmente lo stesso come incatenato if e, come tale, si utilizza anche il confronto. Questo suona come se si dovrebbe infatti basta confrontare a zero per vedere a quale segno a - b ha.

  5. 1
    char c;
    c=0x3D + (!(b/a) && (a-b)) - (!(a/b) && (a-b));
    printf("a %c b",c);
  6. 0
    (!(a/b) ?  cout << " b is greater than a" : (!(b-a) ? cout << "a and b are equal" :  cout << "a is greater than b") :  cout << "a is greater than b");

    Che diventa un po ‘ disordinato, anche se

    Edit: È questo lavoro?

    • E spero di non avere dimenticato di chiudere nulla. Questo è un condizionale se btw, non so se è quello che ti serviva
    • Come ho aggiunto la domanda che questa soluzione non funziona per i valori negativi.
  7. 0

    Ho appena cant vedere alcun buon motivo per farlo : chi vorrebbe un programma senza “se” ?

    una possibile risposta è :

    ( ( a + b ) + abs ( a-b) /2

    Credo “abs” semplicemente nasconde un “se” da qualche parte, così come l’operatore ternario che è solo un altro nome per “se” …

    • Hai ragione. abs utilizza istruzioni if.
    • La risposta alla tua prima domanda è gente che utilizza pesantemente gasdotti, o macchine SIMD. Rami mettere in difficoltà.
  8. 0

    L’Idea Perversa: utilizzare un array di puntatori a funzione. Poi con un po di aritmetica e di operazioni bit per bit ottenere un indice nell’array.

  9. 0

    Come un inutile esercizio, ecco un modo di attuazione di un cond funzione – per servire lo scopo di if, supponendo (e switch, e ?:) aveva in qualche modo scomparsa dal linguaggio, e si utilizza C++0x.

    void cond(bool expr, std::function<void ()> ifTrue, std::function<void ()> ifFalse)
    {
        std::function<void ()> choices[2] = { ifTrue, ifFalse };
        choices[expr == false]();
    }

    ad esempio

    cond(x > y,
        /*then*/ [] { std::cout << "x is greater than y"; },
        /*else*/ [] { std::cout << "x is not greater than y"; });

    Come mi piace dire, inutile.

    • Ha-Ha! Tenendo conto che kvphxga sembra essere un principiante, è molto divertente risposta! 🙂
    • ‘==’ è un operatore di confronto
    • no, è l’operatore di uguaglianza. Tuttavia > è un operatore di confronto, in cui compare anche in questa risposta.
    • ok io riformulare; “a == b” è il confronto a-b. Va bene abbastanza bashing, ha già detto che è inutile.
    • L’operatore di uguaglianza è un confronto/tiva operatore, perché sono ancora in discussione, di questo non ho idea.
  10. 0

    Provare questo, testato, funziona bene.

    public static int compare(int a, int b)
    {
        int c = a - b;
        return (c >> 31) & 1 ^ 1;
    }
  11. 0

    Credo che questo metodo è migliore di un altro, è possibile utilizzare questa logica c e java entrambi i linguaggi di programmazione, ma int dovrebbe essere di 4 byte, se int è di 2 byte, quindi fare 15 byte maiusc di destra, invece di 31 byte.

    enter code here
    
    #include<stdio.h>
    
    main()
    {
       int a, b;
       printf("Enter three numbers\n");
       scanf("%d %d", &a, &b);
       printf("Largest number is %d \n",findMax( a,b ));
    }
    int findMax( int x, int y)
    {
      int z = x - y;
      int i  = (z  >>  31)  &  0x1;
      printf("i = %d shift = %d \n", i, (z>>31));
      int  max  =  x - i  *  z;
      return max;
    }
  12. 0

    Per ottenere il maggior numero possibile senza l’utilizzo di confronto/operatore relazionale

    void PrintGreatestNumber(int a, int b)
    {
       int [] x = new int[] { -1, 0, 1 };
       int greatestNumber =  ((a+b)+ x[ 1 + ((a-b) >> 31) - (-(a-b) >> 31)] * (a-b)) /2;  
       Console.WriteLine(greatestNumber);
    }
  13. -2
    void greater(int a, int b) {
        int c = a - b;
        switch(c) {
            case 0:
                cout << "a and b are equal" << endl;
                break;
            default:
                int d = c & (1<<31);
                switch(d) {
                    case 0:
                        cout << "a is bigger than b" << endl;
                        break;
                    default:
                        cout << "a is less than b" << endl;
                }
        }
    }
    • ebbene, tutte queste sottrarre i metodi hanno un problema, almeno: si consideri un numero grande e una piccola (negativo) il numero b. se si a-b, quindi si, in effetti “a+b”, che può overflow int e quindi, eventualmente, essere negativo. il tuo codice è errato assumere b è più grande di allora.

Lascia un commento