Domanda intervista: numero di bit swap necessari per convertire un numero intero in un altro

Question

In un'intervista a una mia amica è stata posta questa domanda. Non ero in grado di capire una soluzione a questo. Domanda -

Scrivere una funzione per calcolare il numero di bit swap richiesti per convertire un intero in un altro.

Answer 1

L'operazione bit che può essere utilizzato per capire quali bit sono differenti è xor.

Ogni 1 nel xor dirà il diverso bit tra i due numeri interi.

int getBitSwapCount (int x, int y) {

int count = 0; 

for(int z = x^y; z!=0; z = z>> 1) 
{ 
    count += z & 1; 
} 
return count; 

}

Answer 2

Le domande per le interviste non riguardano solo le soluzioni, ma sono anche (e in genere è ancora più importante trovare una soluzione) dandoti l'opportunità di mostrare come affrontare un nuovo problema come questo. Come inizieresti su questo? C'è qualche ulteriore informazione che vorresti sapere per aiutarti a risolverlo? Ci sono delle funzioni standard (in qualsiasi linguaggio di programmazione comunemente usato) che vorresti usare?

Dacci il tuo colpo migliore, giocheremo l'intervistatore (s) e tempestiva, come si va ...

Answer 3

non riesco a vedere nulla di speciale in questa domanda. Iterando sui bit di entrambi gli interi, combinando i bit attuali tramite XOR e incrementando un contatore se il risultato non è uguale a zero, si otterrà il numero di bit che differiscono in entrambi i valori.

Answer 4

XOR i valori e poi contare il numero di quelli nel risultato

Answer 5

approccio diverso

find e la stringa binaria e calcolare Levenshtein distance dalla programmazione dinamica

Answer 6

Prendere il XOR di 2 numeri (per esempio un & b), e contare il numero di quelle in un^b

int bitsSwapRequired (int a, int b){ 
    int count = 0; 
    for (int c = a^b; c!=0 ; c >> 1) 
     count += c & 1; 
    return count; 
} 

Possiamo fare un po 'meglio, piuttosto che semplicemente spostando c ripetutamente mentre si controlla il bit meno significativo, possiamo continuamente capovolgere il bit più a destra impostato su 1 e contare quanto tempo ci vuole per raggiungere 0. L'operazione c = c & (c-1) cancellerà il bit più a destra impostato su 1 in c.

int bitsSwapRequired (int a, int b){ 
    int count = 0; 
    for (int c = a^b; c != 0; c = c & (c-1)) 
     count ++; 
    return count; 
}