Bit Rotation bzw Circular Bit Shift mit Python Boardmittel?

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Benutzeravatar
akis.kapo
User
Beiträge: 127
Registriert: Freitag 1. September 2006, 12:58

Bit Rotation bzw Circular Bit Shift mit Python Boardmittel?

Beitragvon akis.kapo » Freitag 1. September 2006, 13:12

Hallo.

Ich suche nach einer Möglichkeit echte Bit Rotation bzw Circular Bit Shifts in Python hinzukriegen.

Siehe: http://en.wikipedia.org/wiki/Bitwise_op ... e_no_carry

Ausserdem wäre es nett wenn ich Integers als Binärzahlen ausgeben könnte.
Bisher habe ich der wiki.pyhton nur entnehmen können, wies umgekehrt geht: print int('10101010', 2)

Ich danke für eure Antworten im voraus.

bye!

PS: http://cobweb.ecn.purdue.edu/~kak/dist/ ... r-1.0.html
Obigen Link hab ich noch zum Thema gefunden, aber wenn ich ehrlich bin sieht mir das nach "too much" aus. Ausserdem such ich ja einen "kürzeren" und "allgemeineren" Weg.
BlackJack

Beitragvon BlackJack » Freitag 1. September 2006, 13:42

Eine Möglichkeit das ganze zu implementieren:

Code: Alles auswählen

def int2bitstr(value):
    result = list()
    while value:
        result.append(value & 1)
        value >>= 1
    else:
        result.append(0)
    result.reverse()
    return ''.join(map(str, result))

def rotate_left(length, value):
    mask = 2**length - 1
    carry_pos = 2**(length - 1)
    return ((value << 1) | int(bool(value & carry_pos))) & mask

def rotate_right(length, value):
    return (value >> 1) | ((value & 1) << (length - 1))
Benutzeravatar
akis.kapo
User
Beiträge: 127
Registriert: Freitag 1. September 2006, 12:58

Beitragvon akis.kapo » Freitag 1. September 2006, 14:36

Obiges Beispiel habe ich nicht verstanden.
Wie man das anwendet weis ich leider auch nicht,
da kommen immer dieselben Zahlenwerte raus.
Bist du sicher dass dein Code korrekt ist?
Einzig das mit dem int2bitstr() habe ich verstanden und anwenden können.

Eigentlich dachte ich da gibt es schon was in Python für Bitrotationen.
Hier meine Lösung:

Code: Alles auswählen

#!/usr/bin/python -O

def rotate_byte_left_by_one(input_byte):
    input_byte %= 256
    result = (input_byte << 1) % 256

    if input_byte == 255 or input_byte == 0:
        return input_byte
    elif input_byte > 127:
        return result | 1
    else:
        return result

def rotate_byte(input_byte, step_length):
    input_byte %= 256
    step_length %= 8

    if step_length == 0:
        return input_byte

    while step_length > 0:
        result = rotate_byte_left_by_one(input_byte)
        input_byte = result
        step_length -= 1
    return result


Könntest du dein Beispiel bitte kurz erklären?
Benutzeravatar
keppla
User
Beiträge: 483
Registriert: Montag 31. Oktober 2005, 00:12

Beitragvon keppla » Montag 4. September 2006, 23:47

ich bin mir nicht sicher, ob das richtig funktioniert, aber was hieltest du von diesem hier:

Code: Alles auswählen

def rotate(value, dist, bitcount=8):
  dist %= bitcount # damit auch negative und "zu grosse" shifts funktionieren
  left = (value << dist) % (2 ** bitcount) # die linke hälfte der neuen zahl
  right = value >> (bitcount - dist) # die rechte hälfte der neuen zahl
  return left | right
BlackJack

Beitragvon BlackJack » Dienstag 5. September 2006, 07:17

akis.kapo hat geschrieben:Obiges Beispiel habe ich nicht verstanden.
Wie man das anwendet weis ich leider auch nicht,
da kommen immer dieselben Zahlenwerte raus.
Bist du sicher dass dein Code korrekt ist?


Relativ sicher. Das erste Argument ist die Länge in Bits und das zweite der Wert. Wenn Du also ein Byte rotieren möchtest, dann ist das erste Argument eine 8 und das zweite der Wert der um 1 Bit rotiert werden soll.

Eigentlich dachte ich da gibt es schon was in Python für Bitrotationen.


Das braucht man eher sehr selten.

Könntest du dein Beispiel bitte kurz erklären?


Code: Alles auswählen

def rotate_left(length, value):
    mask = 2**length - 1
    carry_pos = 2**(length - 1)
    return ((value << 1) | int(bool(value & carry_pos))) & mask


Zuerst wird eine Bitmaske zum Ausblenden der Bits über `length` berechnet. Dann eine weitere in der das Bit gesetzt ist, was "links rausgeschoben" wird beim verschieben.

In der letzten Zeile passieren 3 Dinge: `value` wird ein Bit nach links verschoben, das unterste Bit wird entsprechend dem Bit an `carry_pos` gesetzt und am Schluss werden noch alle Bits oberhalb von `length` ausmaskiert.

Code: Alles auswählen

def rotate_right(length, value):
    return (value >> 1) | ((value & 1) << (length - 1))


Rechtsverschieben ist etwas einfacher. `value` wird ein Bit nach rechts verschoben, das unterste Bit wird isoliert, an die entsprechende oberste Stelle verschoben und dort dann per Oder-Verknüfung eingefügt.

Wer ist online?

Mitglieder in diesem Forum: brainstir