Ich bereite mich auf ein Programminterview vor. Also habe ich versucht, einige der überholten Interviewfragen zu lösen, um mich auf das kommende Interview vorzubereiten. Ich war fest entschlossen, folgende Frage zu lösen:
Eine zyklische Rechtsverschiebung der vorzeichenlosen 30-Bit-Ganzzahl Xist eine Zahl, die durch Verschieben aller Bits einer binären Darstellung von X um eine Position nach rechts und Verschieben des höchstwertigen Bits auf das niedrigstwertige Bit erhalten wird. Genau, wenn eine binäre Darstellung von X ist
X29 X28 ... X2 X1 X0
Die binäre Darstellung der rechten zyklischen Verschiebung von X ist
X28 ... X2 X1 X0 X29
Angenommen, die Zahl X (zur besseren Lesbarkeit hinzugefügte Ziffern):
00 0000 0000 0000 0000 0100 1100 0001BIN = 1217DEC
seine rechte zyklische Verschiebung ist
00 0000 0000 0000 0000 1001 1000 0010BIN = 2434DEC.
Die zyklische Verschiebungsoperation kann wiederholt werden, zum Beispiel, wenn der gleiche Wert von X gegeben ist, seine rechte zyklische Verschiebung um 3 ist:
00 0000 0000 0000 0010 0110 0000 1000BIN = 9736DEC
Schreibe eine Funktion
int maximum_right_cyclic_shift (int n);
die gegebene 30-Bit-Ganzzahl ohne Vorzeichen X findet ihrerechte zyklische Verschiebung, die den maximalen Wert hat. Zum Beispiel ist die rechte zyklische Verschiebung um 52 des Wertes X = 1217DEC 809500676DEC, und dies ist die größtmögliche rechtsseitige zyklische 30-Bit-Verschiebung von X:
11 0000 0100 0000 0000 0000 0000 0100BIN = 809500676DEC
Daher sollte die Funktion bei X = 1217 geltenreturn 52. Wenn viele rechte zyklische Verschiebung den Maximalwert ergeben, sollte die Funktion ANY von ihnen zurückgeben. Sie können annehmen, dass das Argument X immer eine vorzeichenlose 30-Bit-Ganzzahl ist.
Das ist meine Antwort:
#include <algorithm>
int largest_right_cyclic_shift ( int n ) {
long m = n;
long max = n;
int shift = 0;
for (int i = 1; i < 30; i++){
m = n << i;
if (m > max){
max = m;
shift = i;
}
}
return shift;
}
Die erwartete Antwort für die Eingangsnummer 1217 ist 22. Der obige Code hat mir jedoch einen Wert von 23 gegeben. Ich weiß, der Fehler liegt darin, dass ich die Eingabe als 32-Bit-Ganzzahlen darstelle, während in der Frage angegeben ist, dass ich die Eingabe als 30-Bit-Ganzzahlen darstellen muss. Bei Verwendung von 32-Bit-Ganzzahlen für die Darstellung von 30-Bit-Ganzzahlen bleiben die 2 linken Ziffern ganz links 0. Wenn wir also einen Linksverschiebungsoperator ausführen, wird der Wert verschoben Bit 31statt zu verschieben Bit 29.
Was ist der beste Weg, um dieses Problem zu lösen? Ich bin mir sicher, dass die Lösung einfach ist, es braucht nur etwas Wissen über Bit-Shifting.
Vielen Dank
Antworten:
3 für die Antwort № 1Was ist der beste Weg, um dieses Problem zu lösen?
m = (n << i) & 0x3fffffff;
2 für die Antwort № 2
Der Kommentar von FredOverflow sollte die richtige Antwort sein.
def largest(n) :
mx = n
p = 0
for i in range(30) :
m = n<<i & 0x3fffffff | n>>(30-i)
if m > mx :
p = i
mx = m
print(mx)
return p
>>> largest(1217)
809500676
22
>>>
1 für die Antwort № 3
Dies ist dasselbe wie beim zweiten Versuch von FredOverflow, obwohl ich einen zusätzlichen Satz Klammern hinzugefügt habe, weil ich das immer vergesse & und | Vorrang.
m = ((n << i) & 0x3fffffff) | (n >> (30-i));
Gibt mir einen Wert von 22 für den 1217-Test (VS2010 SP1)