Wert anhand von Bitnummer ermitteln

Was ist die schnellste Methode, um eine Zahl folgendermaßen umzuwandeln:

0 --> 0
1 --> 1
2 --> 3
3 --> 7
4 --> 15
5 --> 31
6 --> 63
7 --> 127

Also sprich: Ich möchte den Wert 0 nach links shiften, nur dass bei jedem Shift auf der rechten Seite eine 1 reinkommen soll:

z.B.
0 << 3
soll 00000111 ergeben.

Was ist hier die schnellste Lösung, ohne vorgefertigte Funktionen (wie pow) zu benutzen?

Ich könnte mir vorstellen:

~(0xFF << bits)

Gibt es da noch was besseres/schnelleres, das weniger Rechenschritte erfordert?

Andromeda

(1<<n)-1 sollte auch gehen.

Vielleicht interessant für dich: https://de.wikipedia.org/wiki/Mersenne-Zahl

dachschaden

Marguss schrieb:

Also sprich: Ich möchte den Wert 0 nach links shiften, nur dass bei jedem Shift auf der rechten Seite eine 1 reinkommen soll

Das kommt aber beim Shiften von 0 nicht raus. Das kommt nie beim Shiften von 0 raus.

#include <stdio.h>

int main(void)
{
    size_t i;
    for(i = 0;i < 64; i++)
        printf("%02zu: %019zu\n",i,(1ULL << i) - 1ULL);
    return 0;
}

Wenn du das nicht berechnen willst, kannst du auch gleich ein statisches Array mit allen Werten einrichten und brauchst einfach nur i als Index zu nehmen. Bei 64 Bits sind das 64 8-Byte-Werte, also 8 64-Byte-Cache-Lines. Die im Speicher zu halten kann teurer sein als das mal eben schnell zu berechnen (CPUs können Bitoperationen echt schnell berechnen), aber wer weiß, vielleicht ist es genau das richtige für dich.

dachschaden schrieb:

Das kommt aber beim Shiften von 0 nicht raus. Das kommt nie beim Shiften von 0 raus.

Äh, ja, das ist mir auch klar.
Was meinst Du wohl, wieso ich gefragt habe, wie ich so etwas erreichen kann?
Wenn ich glauben würde, dass 0 << 3 tatsächlich den Wert 00000111 ergibt, dann hätte ich ja wohl nicht gefragt, sondern dann hätte ich geglaubt, meine Lösung schon zu besitzen.

Welche Variante ist auf Machinenebene kürzer?
(1 << bits) - 1
oder
~(0xFF << bits)
?

Andromeda

Marguss schrieb:

Welche Variante ist auf Machinenebene kürzer?
(1 << bits) - 1
oder
~(0xFF << bits)
?

Das kommt auf den Prozessor an. Und beides ist auch nicht das Selbe.
Wenn schon, dann müsste das untere ~(0xFF << n)&0xff heißen.

dachschaden

Marguss schrieb:

Äh, ja, das ist mir auch klar.
Was meinst Du wohl, wieso ich gefragt habe, wie ich so etwas erreichen kann?
Wenn ich glauben würde, dass 0 << 3 tatsächlich den Wert 00000111 ergibt, dann hätte ich ja wohl nicht gefragt, sondern dann hätte ich geglaubt, meine Lösung schon zu besitzen.

Dann möchtest du nicht den Wert, sondern die Nullstellen nach links verschoben haben.

Marguss schrieb:

Welche Variante ist auf Machinenebene kürzer?
(1 << bits) - 1
oder
~(0xFF << bits)
?

~(0xFF << bits) sorgt nicht mal im Ansatz für das von dir gewünschte Ergebnis:

00: 18446744073709551360
01: 18446744073709551105
02: 18446744073709550595
...

Und selbst wenn es das täte, hast du nicht die Maschine spezifiziert, auf der der Code dann später laufen soll. Und selbst wenn du das hättest, hieße das nicht, dass der Compiler das nicht direkt für dich wegoptimieren würde. Und selbst, wenn er das nicht täte, heißt "kürzer" nicht automatisch "schneller". Und dann kommt es wieder darauf an, was du dem Compiler gesagt hast, wie er optimieren soll (nach Größe oder nach Geschwindigkeit).

@Andromeda: dein Code geht auch nur bis 255:

01: 0000000000000000001
02: 0000000000000000003
03: 0000000000000000007
04: 0000000000000000015
05: 0000000000000000031
06: 0000000000000000063
07: 0000000000000000127
08: 0000000000000000255
09: 0000000000000000255
10: 0000000000000000255
11: 0000000000000000255
12: 0000000000000000255
13: 0000000000000000255

Andromeda

dachschaden schrieb:

@Andromeda: dein Code geht auch nur bis 255:

Bis 127 reicht ihm doch. Wenn nicht, dann nimmt er eben die erste Version. Die geht über die voll Länge.

dachschaden

Andromeda schrieb:

Bis 127 reicht ihm doch.

Noch.