Come aggiungere due numeri senza usare l'operatore + in C usando la manipolazione dei bit

Question

Recentemente ho trovato questa domanda di intervista e non sono bravo nella manipolazione dei bit. Potete ragazzi spiegare cosa fa la funzione 'f'. Non sono sicuro di cosa funzioni questa funzione ricorsiva.

unsigned int f (unsigned int a , unsigned int b) 
{ 
    return a ? f ((a&b) << 1, a ^b) : b; 
} 

ho cercato di incollare il codice in Visual Studio per testare la logica, ma compilatore sta gettando qualche messaggio di errore "non può convertire implicitamente il tipo 'uint' a 'bool'. E 'la dichiarazione di condizione (un?) Nel restituire qualcosa manca? ma sono sicuro che la domanda dell'intervista era esattamente la stessa menzionata sopra

Answer 1

Beh, già alcune persone nei commenti che citano questo aggiungono solo due numeri. Non sono sicuro di un modo migliore per capirlo basta provare alcuni input e prendere nota dei risultati:

Es:

f(5,1) --> returns f(2,4) --> returns f(0,6) --> returns 6 

1.) 5&1 = 1 bit shifted = 2: 5^1 = 4 
2.) 2&4 = 0 bit shifted = 0: 2^4 = 6 
3.) a = 0 so return b of 6 

f(4,3) --> returns f(0,7) --> returns 7 

1.) 4&3 = 0 bit shifted = 0: 4^3 = 7 
2.) a = 0 so return b of 7 

Dopo aver mostrato alcuni esempi dell'output, suppongo che si possa postulare f restituisce i due ingressi sommati.

Answer 2

Il potenziale datore di lavoro è molto accurato o gode di una punizione insolita &.

Per la risposta alla domanda, una recensione del capitolo 2 liberamente disponibile da HackersDelight vale il suo peso in oro. L'operatore di addizione nella funzione è preso da HAKMEM memo -- Item 23 e sostituisce una shift sinistro al posto di moltiplicare per 2. Il memo HAKMEM originale propone:

(A AND B) + (A OR B) = A + B = (A XOR B) + 2 (A AND B) 

o ri-scritto in C:

x + y = (x^y) + 2 * (x & y) 

il datore di lavoro creativo utilizza quindi (x & y) << 1 al posto di 2 * (x & y) e ricorsione per calcolare a riassumere e ora e b fino a = 0 momento in cui b viene restituito.

Felice che non fosse la mia intervista.