binärstelle von integer extrahieren

[Pygoscelis papua]

ich suche eine schnelle Möglichkeit eine einzelne binäre stelle eines Integers zu bekommen.
ich habe zwei Möglichkeiten gefunden, aber vielleicht kennt jemand eine bessere:

Code: Alles auswählen

#1.                    timeit wert:  0.6245423660002416
int(bin(zahl)[2+stelle]) #kommt mir 1. nicht stilvoll und außerdem ineffizient vor
#2. stelle von links!  timeit wert:  0.022492227999464376
(zahl & (2**stelle-1))>>stelle-1

um das zweite zu erklären:

Code: Alles auswählen

#zuerst löscht man alles vor der stelle:
1011010 &
0011111 =
11010
#und dann wird der rest so verschoben, dass man die vorderste stelle hat
1101
110
11
1
 

[noisefloor]

Hallo,

was ist denn bitte die "binäre Stelle eines Integers"?

Und wenn du Code-Schnipsel postest, dann wäre es total toll, wenn du auch die Eingabe- und Ausgabe mit posten würdest. Sonst ist nicht nachvollziehbar, was da eigentlich passiert.

Gruß, noisefloor

[BlackJack]

@Pygoscelis papua: Überleg mal was bei ``zahl & 2**stelle`` heraus kommt.

[miracle173]

was ist denn bitte die "binäre Stelle eines Integers"?

Binärstelle : Binärsystem = Dezimalstelle : Dezimalsystem

mfg günter

[Pygoscelis papua]

oKay nochmal etwas ausführlicher:
stelle und integer sind werte die man einsetzen kann,
miracle173 hat ganz gut erklärt was ich mit binärstelle meinte.
jetzt ein beispiel:
Ich möchte wissen, ob die 4. stelle (von links) der Zahl 55 als binärzahl 0 oder 1 ist:

Code: Alles auswählen

>>> bin(55)
'0b110111'
         ^
>>> #4. stelle = 0
# das zweite habe ich eigentlich schon erklärt:
#55 in binär: 110111
#ich möchte stelle 2 wissen, streiche also alles vorher weg:
>>>55 & (2**4-1)
7
#110111 &
#001111 # = (2**4-1)
#alles was bei dem unteren 00 ist wird weggestrichen!
>>>bin(7)
'0b111'#alles davor ist weg!
#den rest dahinter brach ich auch nicht mehr, schiebe ihn also weg
>>>a = 55 & (2**4-1)
>>>a
7
>>>7>>(4-1) #drei stellen weggeschoben
0     #jetzt weiß ich, dass die 4.stelle (von links) eine 0 ist bei 63 würde 1 rauskomen

[__LC__]

Hallo Pygoscelis papua!

Ich frage nur mal so aus Neugier! Wieso lautet deine Frage eigentlich die 4.Stelle von links? Ich finde deine Sichtweise irgendwie verwirrend, da es ja bei der Betrachtung von der Seite der höherwertigen Bits aus auch auf die Bit-Tiefe der Zahl selbst ankommt ist: Die 4. Stelle bei 8 Bit ist freilich eine andere als bei 16 oder 32 Bit.

Schöne Grüße
Falk

[noisefloor]

Hallo,

würde ich so machen;

Code: Alles auswählen

def bin_digit(number, position):
    return bin(number)[-position]

wobei hier von rechts gezählt wird - was ja auch die übliche Betrachtungsweise ist. Die Funktion so zu ändern, dass von links gezählt wird, ist ja auch kein Problem.

Gruß, noisefloor

[BlackJack]

@Pygoscelis papua: Nur dass das nicht untergeht: Meine Rückfrage ist die Lösung.

[Pygoscelis papua]

das von black Jack geht ja durchaus, aber es kommt nich 0 oder 1 raus sondern 0 oder stelle außer wenn man > 0
einfügt. Bei dem von noisefloor kommt ein string mit länge 1.
hier noch einmal Code zum performance vergleich:

Code: Alles auswählen

>>> timeit.timeit("(55 & 2**4) > 0")
0.05113330100004987
>>> timeit.timeit("(55 & (2**4-1))>>4-1")
0.022641125000006923 !!
>>> timeit.timeit("bin_digit(55, 4)", """def bin_digit(number, position):
...     return int(bin(number)[-position])""")
0.8505164209999521

das 2. ist am schnellsten.
Achso und ich habe mal wieder rechts und links vertauscht. Sorry (@ Falk)
ich wollte natürlich rechts schreiben, weil ich ja auch von rechts zähle.

Falls sich jemand fragt wieso ich mich damit beschäftige:
Ich möchte ein Schach-bitboard Programmieren siehe https://de.wikipedia.org/wiki/Schachprogramm#Bitboards

[BlackJack]

@Pygoscelis papua: Deine Messungen kann ich nicht nachvollziehen. Ist auch nicht wirklich intuitiv das etwas das sich im Grunde durch die gleichen Operationen *plus* zusätzliche Operationen unterscheidet, schneller sein soll.

Code: Alles auswählen

In [11]: %timeit (55 & 2**4) > 0
10000000 loops, best of 3: 54.7 ns per loop

In [12]: %timeit (55 & 2**4) != 0
10000000 loops, best of 3: 53.6 ns per loop

In [13]: %timeit (55 & (2**4-1))>>4-1
10000000 loops, best of 3: 72.1 ns per loop

Was den Anwendungszweck angeht wäre ich auch nur vorsichtig optimistisch dass das in Python wirklich etwas bringt. Vielleicht in PyPy, aber in CPython ist `int` ja doch etwas von dem simplen Datentyp der in ein Prozessorregister passt, entfernt.

[Pygoscelis papua]

Was mache ich denn beim Messen falsch?
Letztendlich wollte ich das eh in Cython implementieren und außerdem will ich auch nur probieren wie so ein KI funktionieren könnte.

@Pygoscelis papua: Deine Messungen kann ich nicht nachvollziehen. Ist auch nicht wirklich intuitiv das etwas das sich im Grunde durch die gleichen Operationen *plus* zusätzliche Operationen unterscheidet, schneller sein soll.

aber es ist doch nicht *plus* sondern ">>stelle-1" statt ">0"
Ich kann das mit "55 & 2**4" ja durchaus gebrauchen es ist ja auch ohne >0 sowieso das schnellere.
Vieleicht habe ich auch nur deine Messung falsch verstanden.

Hier nochmal so wie BlackJack gemessen hat:

Code: Alles auswählen

$python3 -m timeit '(55 & (2**4-1))>>4-1'
10000000 loops, best of 3: 0.0246 usec per loop
$python3 -m timeit '(55 & 2**4) != 0'
10000000 loops, best of 3: 0.0527 usec per loop
$python3 -m timeit '(55 & 2**4) > 0'
10000000 loops, best of 3: 0.0916 usec per loop

[BlackJack]

@Pygoscelis papua: Wir haben in beiden ein ``&`` und ein ``**``. Bei meinem ein ``!=`` und bei Deinem zweimal ``-`` und einmal ``>>``. Ich würde sagen Deins ist mehr, also *plus*, und ich kann mir wirklich nicht vorstellen das ein Vergleich langsamer als zwei Subtraktionen und einmal Bitverschieben sein sollte. Wenn man unsere Messungen vergleicht, dann denke ich mal das man hier einfach nicht mehr sinnvoll messen kann weil andere Faktoren offenbar einen grösseren Unterschied bewirken als die Unterschiede im Ausdruck.

Wobei Deiner mit Bitverschieben übrigens noch unnötig kompliziert ist. Wenn man erst verschiebt und dann ausmaskiert, dann braucht man sich keine Maske berechnen die von der Stelle abhängig ist die man haben möchte: ``(55 >> 4) & 1``

In C würde ich jedenfalls ein Array mit Bitmasken erstellen, damit man die Exponentation nicht ausrechnen muss, und & gefolgt von einem Vergleich mit 0 machen um eine 0 oder eine 1 zu bekommen. Wenn es nur um einen Wahrheitswert geht, kann man sich den Vergleich in C ja sogar noch sparen (in Python ja eigentlich auch).

[Pygoscelis papua]

kann man sich den Vergleich in C ja sogar noch sparen (in Python ja eigentlich auch)

Ich weiß deshalb finde ich die Idee ja auch gut es ist nur wenn man wirklich eine 0 oder 1 will (was vorkommen könnte aber !nicht! muss)
problematisch
Anscheinend hängt das wirklich vom System und so ab, also nehme ich der Übersichtlichkeit erst mal deine Idee.
Ich denke man muss jetzt auch nicht Tage darüber philosophieren, ich hatte nur gedacht, dass ich vielleicht etwas nicht gelesen hätte, was
evtl. meine Arbeit ungemein erleichtern würde.

[hans]

Hmm, kann ich fast alles nicht nachvollziehen? Vielleicht weil Sonntag ist?

ist da ein bitweiser Vergleich nicht einfacher?

Code: Alles auswählen

>>> import operator
>>> operator.and_(55,4)
4
>>> operator.and_(51,4)
0
>>> operator.xor(55,4)
51

[BlackJack]

@hans: Einfacher als was? Als ein bitweiser Vergleich? Die Funktionsaufrufe sind in CPython auf jeden Fall teurer als gleich den Operator zu verwenden. Was soll das also Bringen statt der Operatoren direkt, die Funktionen aus dem `operator`-Modul zu verwenden?

[hans]

Das kommt davon, wenn man der (python-) Suche ungeprüft glaubt. Die Operatoren sind ja ganz schön versteckt. Habe sie dann doch noch in der Referenz Abschnitt 6.9 gefunden. Am besten Ausdrucken und an die Wand nageln damit man sie immer im Blickfeld hat.

[Pygoscelis papua]

Vielleicht in PyPy, aber in CPython ist `int` ja doch etwas von dem simplen Datentyp der in ein Prozessorregister passt, entfernt.

Da müsste bei Cython doch

Code: Alles auswählen

ctypedef unsigned long long ULLong
i = ULLong
i = 2**63
print(i)

gehen oder.
Das ist dann doch direkt der 64bit Integer von C oder?

[BlackJack]

Falls ``unsigned long long`` ein 64-Bit-Integer ist, dann ist das ein 64-Bit-Integer, ja. Falls nicht, dann natürlich nicht. Ich benutze in C lieber die Definitionen aus `inttypes.h` wenn ich feste Bitbreiten brauche, das ist dann eindeutig.

[Pygoscelis papua]

und wie kann ich das in Cython nutzen?
außerdem habe ich gemerkt, das wenn ich einen 64bit integer zurückgebe, er dann zu einem normalen python int wird. kann ich dass verhindern?

[BlackJack]

@Pygoscelis papua: Die Headerdatei inkludieren und einfach verwenden würde ich sagen.

Was willst Du denn beim Rückgabewert verhindern? Mit C-Integer-Datentypen kann Python nichts anfangen, das kennt nur Python-Objekte. Wie hättest Du Dir das denn vorgestellt?