python odwraca binarny wzorzec w liczbie całkowitej

Sep 02 2020

Czy istnieje szybka możliwość odwrócenia liczby binarnej w Pythonie?

Przykład: mam liczbę 11 w postaci binarnej 0000000000001011 z 16 bitami. Teraz szukam szybkiej funkcji f, która zwraca 1101000000000000 (53248 dziesiętnie). Tabele wyszukiwania nie są rozwiązaniem, ponieważ chcę, aby były skalowane do liczb 32-bitowych. Dziękuję za Twój wysiłek.

Edytować:

Przedstawienia . Kilkakrotnie testowałem kod dla wszystkich wzorców 2 ^ 16.

  • zwycięzcami są tabele częściowo przeglądane: 30 ms

  • 2. int(format(num, '016b')[::-1], 2)z komentarzy: 56 ms

  • 3 x = ((x & 0x00FF) << 8) | (x >> 8): 65 ms

  • Nie spodziewałem się, że moje podejście będzie tak strasznie powolne, ale tak jest. około. 320 ms. Mała poprawa dzięki użyciu + zamiast | 300 ms

  • bytes(str(num).encode('utf-8'))walczył o 2 miejsce, ale kod jakoś nie dawał prawidłowych odpowiedzi. Najprawdopodobniej popełniłem błąd, przekształcając je ponownie w liczbę całkowitą.

bardzo dziękuję za wkład. Byłem dość zaskoczony.

Odpowiedzi

3 HL Sep 02 2020 at 04:36

Może to być szybsze przy użyciu małej 8-bitowej tabeli przeglądowej:

num = 11
# One time creation of 8bit lookup
rev = [int(format(b, '08b')[::-1], base=2) for b in range(256)]

# Run for each number to be flipped.
lower_rev = rev[num & 0xFF] << 8
upper_rev = rev[(num & 0xFF00) >> 8]
flipped = lower_rev + upper_rev
1 Ethan Sep 02 2020 at 03:55

Myślę, że możesz po prostu użyć krojenia, aby uzyskać to, czego szukasz:

b=bytes('0000000000001011'.encode('utf-8'))
>>> b
b'0000000000001011'
>>> b[::-1]
b'1101000000000000'
1 superbrain Sep 02 2020 at 04:27

Jest to, ale w Pythonie wydaje się wolniejsze niż rozwiązanie zaproponowane przez Matthiasa int-> str-> int.

x = ((x & 0x5555) << 1) | ((x & 0xAAAA) >> 1)
x = ((x & 0x3333) << 2) | ((x & 0xCCCC) >> 2)
x = ((x & 0x0F0F) << 4) | ((x & 0xF0F0) >> 4)
x = ((x & 0x00FF) << 8) | (x >> 8)
1 DuDa Sep 02 2020 at 03:48

Moje obecne podejście polega na dostępie do bitów poprzez przesuwanie bitów i maskowanie oraz przesuwanie ich w numerze lustrzanym, aż dotrą do celu. Nadal mam wrażenie, że jest miejsce na poprawę.

num = 11
print(format(num, '016b'))

right = num
left = 0
for i in range(16):
  tmp = right & 1
  left = (left << 1 ) | tmp
  right = right >> 1


print(format(left, '016b'))