Bit Rotation bzw Circular Bit Shift mit Python Boardmittel?

[akis.kapo]

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]

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))

[akis.kapo]

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?

[keppla]

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]

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.