N-te kleinste Zahl mit n Bits, die auf 1 gesetzt sind

Es gibt eine Folge von steigenden Zahlen, die dieselbe Anzahl von binären 1s enthalten. Gegeben n (die Anzahl von 1 Bits, die in jeder Zahl in der Reihe gesetzt sind) schreibe einen Algorithmus oder ein C-Programm, um die n-te Zahl in der Reihe zu finden.N-te kleinste Zahl mit n Bits, die auf 1 gesetzt sind

Ich habe diese Frage im Internet gefunden und ich denke, die Antwort ist nur ((1 < < (n + 1)) - 1) & ~ 2). Ist das nicht richtig? Ich habe einige beängstigende Programme gefunden, um die Antwort zu berechnen.

Quelle

2011-01-04 Anil Katti

Es sollte nicht schwer sein, ein Programm zu schreiben, um das zu überprüfen! –

Sind die beiden 'n' Variablen gleich? Mit anderen Worten, ist die Frage "Wenn jede Zahl 5 Einsen hat, finde die fünfte solche Zahl?" – cdhowie

Ja, das ist richtig. –

(1 << n+1) - 3 ist eine prägnantere Möglichkeit, das Ergebnis auszudrücken, aber ja, ich glaube, Ihr Ausdruck ist auch richtig.

Quelle

2011-01-04 23:45:42

Das macht Sinn. –

Oder, besser, '(2 << n) - 3' – ruslik

@ruslik: tatsächlich. –

Ich glaube, Sie haben Recht. ~~Ein einfacher Weg, es zu schreiben, obwohl sein wird: ((1 < < n) - 1) < < 1.~~

Quelle

2011-01-04 23:34:31 krakover

Nein, dieser Ausdruck entspricht nicht meinem. –

Entschuldigung. Du hast Recht (es ist noch eins). – krakover

Ja, es ist wahr. Wenn wir 3 Bits haben:

1: 00000111 
2: 00001011 
3: 00001101 // bit 1 will be 0 
4: 00001110

so ist die Antwort n + 1 Bits, wobei Bit 1 ist 0.

Quelle

2011-01-04 23:41:32 ruslik

Seine Formel, für n = 3, ergibt 13. Dies ist die Nummer, die Sie in Zeile 3 auflisten, so dass seine Formel für mich richtig aussieht. Die Formel von krakover ist falsch. –

@Martin: behoben. – ruslik

Nein Ruslik, in diesem Fall wird mein Ausdruck 00001101 ergeben - nicht wahr? ((1 << 4) - 1) & (11111101)) = 00001101 –

-1

Die Frage ist nicht zu spezifizieren scheint, wo die Sequenz beginnt, oder wie viel die Zahl wird jedes Mal erhöht, während Ihre Antwort davon ausgeht, dass die Sequenz mit 011111 beginnt, dann zu 101111 geht und so weiter. Es könnte möglicherweise mit 0011111000 beginnen, und das nächste Element könnte 1111100000.

bearbeiten

Die Frage, wie bei https://groups.google.com/group/algogeeks/browse_thread/thread/5fda06c0be475c41/ angegeben ist unter dem Titel „n-te Nummer der Serie“, so der Titel dieses Beitrags ("N-te kleinste Zahl mit n Bits auf 1 gesetzt") hält den Ursprung der Frage nicht wirklich aufrecht.

Quelle

2011-01-04 23:41:53 StriplingWarrior

Nein: Für 11 Bit ist 11111 eindeutig eine Nummer in der Sequenz und ist deutlich kleiner als 0011111000. Die Sequenz kann also nicht mit beginnen 0011111000. –

Es ist die n-te kleinste Ganzzahl mit n Bits, die auf 1 gesetzt sind. Um genauer zu sein, sollte es eine Ganzzahl ohne Vorzeichen sein. –

Die Frage lautet: "Es gibt eine Folge von steigenden Zahlen, die die gleiche Anzahl von binären 1s in ihnen haben." Es sagt Ihnen nicht, dass die Sequenz mit der kleinstmöglichen Zahl beginnen muss. Es ist nicht dasselbe wie zu sagen "Sequenz S ist definiert als alle positiven Zahlen mit der gleichen Anzahl von binären 1en in ihnen, in aufsteigender Reihenfolge." – StriplingWarrior

N-te kleinste Zahl mit n Bits, die auf 1 gesetzt sind

Antwort

Verwandte Themen