Spiega questo frammento che trova il massimo di due interi senza utilizzare if-else o altri operatori di confronto?

Trova il massimo di due numeri. Non si dovrebbe usare if-else o qualsiasi altro operatore di confronto. Ho trovato questa domanda sulla bacheca online, quindi ho pensato che dovrei chiedere in StackOverflow

ESEMPIO Ingresso: 5, 10 Uscita: 10

Ho trovato questa soluzione, qualcuno può aiutarmi a capire queste righe di codice

int getMax(int a, int b) { int c = a - b; int k = (c >> 31) & 0x1; int max = a - k * c; return max; } 

 int getMax(int a, int b) { int c = a - b; int k = (c >> 31) & 0x1; int max = a - k * c; return max; } 

Analizziamo questo. Questa prima riga sembra semplice: memorizza la differenza di b . Questo valore è negativo se a < b è diverso da Negativo. In realtà qui c'è un bug: se la differenza tra i numeri b è così grande che non può rientrare in un numero intero, ciò porterà a un comportamento indefinito: oops! Quindi supponiamo che non succeda qui.

Nella riga successiva, che è

 int k = (c >> 31) & 0x1; 

l'idea è di verificare se il valore di c è negativo. In praticamente tutti i computer moderni, i numeri sono memorizzati in un formato chiamato complemento a due in cui il bit più alto del numero è 0 se il numero è positivo e 1 se il numero è negativo. Inoltre, la maggior parte dei inte sono 32 bit. (c >> 31) sposta il numero in basso di 31 bit, lasciando il bit più alto del numero nel punto per il bit più basso. Il prossimo passo di prendere questo numero e ANDarlo con 1 (la cui rappresentazione binaria è 0 ovunque tranne l'ultimo bit) cancella tutti i bit più alti e ti dà solo il bit più basso. Poiché il bit più basso di c >> 31 è il bit più alto di c , questo legge il bit più alto di c come 0 o 1. Poiché il bit più alto è 1 iff c è 1, questo è un modo per verificare se c è negativo (1) o positivo (0). Combinando questo ragionamento con quanto sopra, k è 1 se a < b ed è 0 altrimenti.

Il passo finale è quello di fare questo:

 int max = a - k * c; 

Se a < b , allora k == 1 e k * c = c = a - b , e così via

 a - k * c = a - (a - b) = a - a + b = b 

Qual è il massimo corretto, dal momento che a < b . Altrimenti, se a >= b , allora k == 0 e

 a - k * c = a - 0 = a 

Che è anche il massimo corretto

Eccoci: (a + b) / 2 + |a - b| / 2 (a + b) / 2 + |a - b| / 2

Usa hack bit a bit

 r = x ^ ((x ^ y) & -(x < y)); // max(x, y) 

Se si conosce INT_MIN <= x - y <= INT_MAX, è ansible utilizzare quanto segue, che è più veloce perché (x - y) deve essere valutato solo una volta.

 r = x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))); // max(x, y) 

Fonte: Bit Twiddling Hacks di Sean Eron Anderson

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

Questo si basa sulla stessa tecnica della soluzione di mike.dld , ma qui è meno “ovvio” quello che sto facendo. Un’operazione “abs” sembra che tu stia paragonando il segno di qualcosa, ma io sto approfittando del fatto che sqrt () ti restituirà sempre la radice quadrata positiva, quindi io sto quadrando (ab) scrivendolo in full-square radicandolo nuovamente, aggiungendo a + b e dividendo per 2.

Vedrai che funziona sempre: ad esempio l’esempio dell’utente di 10 e 5 ottieni sqrt (100 + 25 – 100) = 5, quindi aggiungi 10 e 5 ti dà 20 e dividi per 2 ti dà 10.

Se usiamo 9 e 11 come i nostri numeri otterremmo (sqrt (121 + 81 – 198) + 11 + 9) / 2 = (sqrt (4) + 20) / 2 = 22/2 = 11

La risposta più semplice è qui sotto.

 #include  int Max(int x, int y) { return (float)(x + y) / 2.0 + abs((float)(x - y) / 2); } int Min(int x, int y) { return (float)(x + y) / 2.0 - abs((float)(x - y) / 2); } 
 int max(int i, int j) { int m = ((ij) >> 31); return (m & j) + ((~m) & i); } 

Questa soluzione evita la moltiplicazione. m sarà 0x00000000 o 0xffffffff

Usando l’idea del cambiamento per estrarre il segno come postato da altri, ecco un altro modo:

 max (a, b) = new[] { a, b } [((a - b) >> 31) & 1] 

Questo spinge i due numeri in una matrice con il numero massimo dato dall’elemento-matrice il cui indice è un bit di segno della differenza tra i due numeri.

Prendi nota che:

  1. La differenza (a - b ) può traboccare.
  2. Se i numeri non sono firmati e l’operatore >> fa riferimento a uno spostamento logico a destra, il segno & 1 non è necessario.

Ecco come penso che farei il lavoro. Non è leggibile come potrebbe piacerti, ma quando inizi con “come faccio X senza usare il modo ovvio di fare X, devi aspettarti una cosa del genere. In teoria, anche questa porta a una certa portabilità, ma tu” Devo trovare un sistema abbastanza insolito per vedere un problema.

 #define BITS (CHAR_BIT * sizeof(int) - 1) int findmax(int a, int b) { int rets[] = {a, b}; return rets[unsigned(ab)>>BITS]; } 

Questo ha alcuni vantaggi rispetto a quello mostrato nella domanda. Prima di tutto, calcola la dimensione corretta del turno, invece di essere codificato per gli inserti a 32 bit. In secondo luogo, con la maggior parte dei compilatori possiamo aspettarci che tutta la moltiplicazione avvenga in fase di compilazione, quindi tutto ciò che rimane in fase di esecuzione è la manipolazione bit triviale (sottrazione e spostamento) seguita da un carico e un ritorno. In breve, questo è quasi certo essere abbastanza veloce, anche sul più piccolo microcontrollore, dove l’originale ha usato la moltiplicazione che doveva accadere in fase di esecuzione, quindi mentre è probabilmente piuttosto veloce su una macchina desktop, sarà spesso piuttosto un un po ‘più lento su un piccolo microcontrollore.

Ecco cosa stanno facendo quelle linee:

c è ab. se c è negativo, a

k è 32nd bit di c che è il bit di segno di c (supponendo numeri interi a 32 bit. Se fatto su una piattaforma con interi a 64 bit, questo codice non funzionerà). È spostato di 31 bit a destra per rimuovere i 31 bit più a destra lasciando il bit di segno nella posizione più a destra e quindi aggiungendolo a 1 per rimuovere tutti i bit a sinistra (che verrà riempito con 1 se C è negativo). Quindi k sarà 1 se c è negativo e 0 se c è positivo.

Quindi max = a – k * c. Se c è 0, significa a> = b, quindi max è a – 0 * c = a. Se c è 1, significa che a

Nel complesso, è sufficiente utilizzare il bit di segno della differenza per evitare di utilizzare operazioni maggiori o minori rispetto alle operazioni. È onestamente un po ‘sciocco dire che questo codice non usa un confronto. c è il risultato del confronto di aeb. Il codice non usa un operatore di confronto. Si potrebbe fare una cosa simile in molti codici assembly semplicemente sottraendo i numeri e saltando in base ai valori impostati nel registro di stato.

Dovrei anche aggiungere che tutte queste soluzioni presuppongono che i due numeri siano interi. Se sono float, double o qualcosa di più complicato (BigInts, numeri razionali, ecc.), Allora devi davvero usare un operatore di confronto. I trucchi non lo faranno generalmente per quelli.

Funzione getMax () senza alcuna operazione logica-

 int getMax(int a, int b){ return (a+b+((ab)>>sizeof(int)*8-1|1)*(ab))/2; } 

Spiegazione:

Consente di distruggere il ‘massimo’ in pezzi,

 max = ( max + max ) / 2 = ( max + (min+differenceOfMaxMin) ) / 2 = ( max + min + differenceOfMaxMin ) / 2 = ( max + min + | max - min | ) ) / 2 

Quindi la funzione dovrebbe assomigliare a questo-

 getMax(a, b) = ( a + b + absolute(a - b) ) / 2 

Adesso,

 absolute(x) = x [if 'x' is positive] or -x [if 'x' is negative] = x * ( 1 [if 'x' is positive] or -1 [if 'x' is negative] ) 

Nel numero intero positivo il primo bit (bit di segno) è- 0 ; in negativo è- 1 . Spostando i bit a destra (>>) è ansible catturare il primo bit.

Durante il passaggio a destra lo spazio vuoto viene riempito dal bit del segno. Quindi 01110001 >> 2 = 00011100 , mentre 10110001 >> 2 = 11101100 .

Di conseguenza, per lo spostamento del numero a 8 bit, 7 bit produrranno 1 1 1 1 1 1 1 [0 o 1] per il negativo o 0 0 0 0 0 0 0 [0 o 1] per il positivo.

Ora, se l’operazione OR viene eseguita con 00000001 (= 1) , il numero negativo restituisce 11111111 (= -1) e positivo- 00000001 (= 1) .

Così,

 absolute(x) = x * ( 1 [if 'x' is positive] or -1 [if 'x' is negative] ) = x * ( ( x >> (numberOfBitsInInteger-1) ) | 1 ) = x * ( ( x >> ((numberOfBytesInInteger*bitsInOneByte) - 1) ) | 1 ) = x * ( ( x >> ((sizeOf(int)*8) - 1) ) | 1 ) 

Finalmente,

 getMax(a, b) = ( a + b + absolute(a - b) ) / 2 = ( a + b + ((ab) * ( ( (ab) >> ((sizeOf(int)*8) - 1) ) | 1 )) ) / 2 

static int mymax (int a, int b)

  { int[] arr; arr = new int[3]; arr[0] = b; arr[1] = a; arr[2] = a; return arr[Math.Sign(a - b) + 1]; } 

Se b> a allora (ab) sarà negativo, il segno ritornerà -1, aggiungendo 1 otteniamo l’indice 0 che è b, se b = a allora ab sarà 0, +1 darà 1 indice quindi non importa se restituiamo a o b, quando a> b allora ab sarà positivo e il segno tornerà 1, aggiungendo 1 otteniamo l’indice 2 dove a è memorizzato.

 #include main() { int num1,num2,diff; printf("Enter number 1 : "); scanf("%d",&num1); printf("Enter number 2 : "); scanf("%d",&num2); diff=num1-num2; num1=abs(diff); num2=num1+diff; if(num1==num2) printf("Both number are equal\n"); else if(num2==0) printf("Num2 > Num1\n"); else printf("Num1 > Num2\n"); } 

Il codice che sto fornendo è quello di trovare il massimo tra due numeri, i numeri possono essere di qualsiasi tipo di dati (intero, variabile). Se i numeri di input sono uguali, la funzione restituisce il numero.

 double findmax(double a, double b) { //find the difference of the two numbers double diff=ab; double temp_diff=diff; int int_diff=temp_diff; /* For the floating point numbers the difference contains decimal values (for example 0.0009, 2.63 etc.) if the left side of '.' contains 0 then we need to get a non-zero number on the left side of '.' */ while ( (!(int_diff|0)) && ((temp_diff-int_diff)||(0.0)) ) { temp_diff = temp_diff * 10; int_diff = temp_diff; } /* shift the sign bit of variable 'int_diff' to the LSB position and find if it is 1(difference is -ve) or 0(difference is +ve) , then multiply it with the difference of the two numbers (variable 'diff') then subtract it with the variable a. */ return a- (diff * ( int_diff >> (sizeof(int) * 8 - 1 ) & 1 )); } 

Descrizione

  • La prima cosa che la funzione prende gli argomenti come double e ha restituito type double. La ragione di ciò è che per creare una singola funzione che può trovare il massimo per tutti i tipi. Quando vengono forniti numeri di numeri interi o uno è un numero intero e l’altro è il punto mobile, anche a causa della conversione implicita la funzione può essere utilizzata anche per trovare il massimo per gli interi.
  • La logica di base è semplice, diciamo che abbiamo due numeri a & b se ab> 0 (vale a dire la differenza è positiva) quindi a è massimo altrimenti se ab == 0 quindi entrambi sono uguali e se ab <0 (cioè diff è - ve) b è il massimo.
  • Il bit di segno viene salvato come il bit più significativo (MSB) nella memoria. Se MSB è 1 e viceversa. Per verificare se MSB è 1 o 0, spostiamo l’MSB nella posizione LSB e Bitwise & con 1, se il risultato è 1, allora il numero è -ve altro no. è + ve. Questo risultato è ottenuto dalla dichiarazione:

    int_diff >> (sizeof (int) * 8 – 1) e 1

Qui per ottenere il bit di segno da MSB a LSB lo spostiamo a destra in bit k-1 (dove k è il numero di bit necessari per salvare un numero intero nella memoria che dipende dal tipo di sistema). Qui k = sizeof (int) * 8 come sizeof () indica il numero di byte necessari per salvare un numero intero per ottenere no. di bit, lo moltiplichiamo con 8. Dopo il passaggio a destra, applichiamo il bitwise & con 1 per ottenere il risultato.

  • Ora dopo aver ottenuto il risultato (assumiamo come r) come 1 (per -ve diff) e 0 (per + ve diff) moltiplichiamo il risultato con la differenza dei due numeri, la logica è data come segue:

    1. se a> b allora ab> 0 cioè, è + ve quindi il risultato è 0 (cioè r = 0). Quindi a- (ab) * r => a- (ab) * 0, che dà ‘a’ come il massimo.
    2. se a a- (ab) * 1 => a-a + b => b, che dà ‘b’ come il massimo.
  • Ora ci sono due punti rimanenti 1. l’uso del ciclo while e 2. perché ho usato la variabile ‘int_diff’ come un numero intero. Per rispondere correttamente, dobbiamo comprendere alcuni punti:

    1. I valori di tipo floating non possono essere utilizzati come operandi per gli operatori bit a bit.
    2. A causa del motivo sopra, abbiamo bisogno di ottenere il valore in un valore intero per ottenere il segno della differenza utilizzando operatori bit a bit. Questi due punti descrivono la necessità della variabile ‘int_diff’ come tipo intero.
    3. Ora diciamo che troviamo la differenza nella variabile ‘diff’ ora ci sono 3 possibilità per i valori di ‘diff’ indipendentemente dal segno di questi valori. (un). | diff |> = 1, (b). 0 <| diff | <1, (c). | Diff | == 0.
    4. Quando assegniamo un doppio valore alla variabile intera, la parte decimale viene persa.
    5. Per il caso (a) il valore di ‘int_diff’> 0 (cioè, 1,2, …). Per altri due casi int_diff = 0.
    6. La condizione (temp_diff-int_diff) || 0.0 verifica se diff == 0, quindi entrambi i numeri sono uguali.
    7. Se diff! = 0 allora verifichiamo se int_diff | 0 è vero cioè, case (b) è vero
    8. Nel ciclo while, proviamo a ottenere il valore di int_diff come non-zero in modo che anche il valore di int_diff riceva il segno di diff.

Qui ci sono un paio di metodi di bit-twiddling per ottenere il massimo di due valori interi:

Metodo 1

 int max1(int a, int b) { static const size_t SIGN_BIT_SHIFT = sizeof(a) * 8 - 1; int mask = (a - b) >> SIGN_BIT_SHIFT; return (a & ~mask) | (b & mask); } 

Spiegazione:

  • (a – b) >> SIGN_BIT_SHIFT – Se a > b allora a - b è positivo, quindi il bit di segno è 0 e la maschera è 0x00.00 . Altrimenti, a < b so a - b è negativo, il bit del segno è 1 e dopo lo spostamento, otteniamo una maschera di 0xFF..FF
  • (a & ~ mask) - Se la maschera è 0xFF..FF , quindi ~mask è 0x00..00 e quindi questo valore è 0 . Altrimenti, ~mask è 0xFF..FF e il valore è a
  • (b & mask) - Se la maschera è 0xFF..FF , allora questo valore è b . In caso contrario, la mask è 0x00..00 e il valore è 0 .

Finalmente:

  • Se a >= b allora a - b è positivo, otteniamo max = a | 0 = a max = a | 0 = a
  • Se a < b allora a - b è negativo, otteniamo max = 0 | b = b max = 0 | b = b

Metodo 2

 int max2(int a, int b) { static const size_t SIGN_BIT_SHIFT = sizeof(a) * 8 - 1; int mask = (a - b) >> SIGN_BIT_SHIFT; return a ^ ((a ^ b) & mask); } 

Spiegazione:

  • La spiegazione della maschera è la stessa del Metodo 1 . Se a > b la maschera è 0x00..00 , altrimenti la maschera è 0xFF..FF
  • Se la maschera è 0x00..00 , quindi (a ^ b) & mask è 0x00..00
  • Se la maschera è 0xFF..FF , allora (a ^ b) & mask è a ^ b

Finalmente:

  • Se a >= b , otteniamo a ^ 0x00..00 = a
  • Se a < b , otteniamo a ^ a ^ b = b

La logica descritta in un problema può essere spiegata come se il primo numero fosse inferiore, quindi 0 verrà sottratto, altrimenti la differenza verrà sottratta dal primo numero per ottenere il secondo numero. Ho trovato un’altra soluzione matematica che ritengo sia più semplice capire questo concetto.

Considerando a e b come numeri dati

 c=|a/b|+1; d=(c-1)/b; smallest number= a - d*(ab); 

Di nuovo, l’idea è di trovare k che è wither 0 o 1 e moltiplicarlo con la differenza di due numeri.E infine questo numero dovrebbe essere sottratto dal primo numero per ottenere il più piccolo dei due numeri. PS questa soluzione fallirà nel caso in cui il secondo numero sia zero

 int a=151; int b=121; int k=Math.abs(ab); int j= a+b; double k1=(double)(k); double j1= (double) (j); double c=Math.ceil(k1/2) + Math.floor(j1/2); int c1= (int) (c); System.out.println(" Max value = " + c1); 

(a / b) * b + (b / a) * a – (a / b) * (b / a) * a + (abs (a – b)% a)% b

C’è un modo

  public static int Min(int a, int b) { int dif = (int)(((uint)(a - b)) >> 31); return a * dif + b * (1 - dif); } 

e uno

 return (a>=b)?b:a; 

Immagino che possiamo semplicemente moltiplicare i numeri con i loro confronti bit a bit, ad esempio:

 int max=(a>b)*a+(a<=b)*b;