Dati due numeri L & R, Trova AND bit per bit di tutti i numeri che si trovano tra L e R inclusivaAND bit a bit (&) per la gamma dei numeri
Vincoli 1<= L,R <= (2^32).
LL step = 1;
while(L!=R)
{
L/=2; R/=2; step*=2;
}
cout<<L*step<<endl;
Qualcuno può aiutarmi con la spiegazione o la logica dietro il codice di cui sopra?
Quindi sì, è un po 'difficile e necessita di schizzi su carta. Una volta ottenuta l'idea, è semplice. Inizierò con spiegazioni in inglese quindi semplice esempio. La cosa più importante è liberare la tua mente dal fatto che siamo bizzarramente due numeri e pensiamo ai numeri in mezzo.
In primo luogo, Diciamo alcune regole: 1) Se due numeri sono uguali, nessun numero sarà tra di loro. 2) Se due numeri non sono uguali, il numero consecutivo tra loro conterrà ZERO ad ogni cifra, quindi il loro AND bit a bit sarà ZERO.
Prima di entrare nell'esempio, dovremmo spiegare il semplice algoritmo sopra riportato.
1) Ogni divisione con due mezzi rimuove una cifra binaria dalla destra dei numeri. (Questo è come divisione in due modi in binario). 2) Ogni volta che dividiamo, raddoppiamo la variabile del passo. Semplice, la variabile passo è più simile a un contatore che detiene il valore più alto nella parte superiore prima che i due numeri diventino uguali.
Supponiamo di avere il seguente esempio:
L: 11.110.001 R: 11110011
S = 1 (00000001 in binario)
Applicando l'algoritmo su questi valori:
Poiché L e R non sono ancora uguali, tagliare una singola cifra binaria da ciascuna (dividere ciascuna per 2) e moltiplicare S per 2; Nel primo turno diventano
L: 1111000 R: 1111001
S = 2 (00000010 in binario)
Poiché non sono uguali e, di nuovo, e il risultato è:
L: 111100 R: 111100
Ora sono uguali, le interruzioni di loop e il risultato
012.351.641.061.è il numero di sinistra (o il diritto poiché sono uguali) * valore S.
Quando eseguiamo il multiplo in binario, aggiungiamo uno zero a destra. Qui abbiamo bisogno di 3 zeri poiché S è 00000010
11110000 che è come previsto.
Conclusione: continuare a tagliare dividendo fino a quando entrambi sono uguali e nulla è tra di loro.Mentre fate che l'aggiornamento mastio che passo si è in :)
Prima pensiamo ciò che fa bit a bit e da fare a due numeri, ad esempio (0b significa di base 2)
4 & 7 = 0b100 & 0b111 = 0b100
5 & 7 = 0b101 & 0b111 = 0b101
5 & 6 = 0b101 & 0b110 = 0b100
L'operatore & è mantenere quelli bit che è impostato in entrambi i numeri.
Per diversi numeri, l'operatore & sta mantenendo quei bit che è 1 in ogni numero.
In altre parole, un bit è 0 in un numero qualsiasi, con 0 nel bit corrispondente della risposta.
Ora considerare una serie
[m = 0bxyz0acd, n = 0bxyz1rst] qui xyzpacdrst sono tutte cifre in base 2.
Possiamo trovare due numeri che sono speciali nel range [m, n ]
(1) m '= 0bxyz0111 (2) n' = 0bxyz1000 L'AND bit a bit di tutti i numeri nell'intervallo [m, n] è solo AND bit a bit dei due numero speciale
ra ngeBitwiseAnd (m, n) = m '& n' = 0bxyz0000 Questo ci dice che il bit a bit e l'intervallo mantiene i bit comuni di m e n da sinistra a destra fino al primo bit in cui sono diversi, riempendo gli zeri per il riposo.