Slick sposób odwrócić (binarne) cyfry liczby w Pythonie?

Poszukuję uproszczonej funkcji odwracającej cyfry binarnej reprezentacji liczby.Slick sposób odwrócić (binarne) cyfry liczby w Pythonie?

Jeśli f była taka funkcja musiałbym

int(reversed(s),2) == f(int(s,2)) gdy s jest ciągiem zer i jedynek, począwszy od 1.

w tej chwili używam lambda x: int(''.join(reversed(bin(x)[2:])),2)

który jest ok, jak daleko jako zwięzły, ale wydaje się, że jest to dość okrężny sposób.

Zastanawiam się, czy był lepszy (być może szybszy) sposób z operatorami bitowymi, a co nie.

Źródło

2013-03-02 math4tots

Dlaczego masz wywołanie 'list()' w tam? 'str.join()' potraktuje każdą iterowalną. W ogóle nie uważam tego za rondo - jest napisane dokładnie tak, jak to wyjaśniasz. –

@ Legateware Dobrze, to nie było potrzebne. Czułem, że jest to okrężne w tym sensie, że manipuluję strunami, kiedy wydaje się, że to naprawdę numeryczny problem. Chociaż sugestie, jak poprawić metodę ciągów, są również fajne. – math4tots

@ math4tots: Wydaje się mało prawdopodobne, aby jakakolwiek metoda manipulacji bitami była szybsza, ponieważ nieuchronnie wiązałaby się z interpretowanymi pętlami. Jest to oczywiście ostry kontrast w stosunku do języków takich jak C, w których naturalnym rozwiązaniem jest bit twiddling. – NPE

Jak o

int('{0:b}'.format(n)[::-1], 2)

lub

int(bin(n)[:1:-1], 2)

Druga metoda wydaje się być szybsza od dwóch, jednak oba są znacznie szybsze niż dotychczasowe metody:

import timeit 

print timeit.timeit("int('{0:b}'.format(n)[::-1], 2)", 'n = 123456') 

print timeit.timeit("int(bin(n)[:1:-1], 2)", 'n = 123456') 

print timeit.timeit("int(''.join(reversed(bin(n)[2:])),2)", 'n = 123456')

 
1.13251614571 
0.710681915283 
2.23476600647

Źródło

2013-03-02 22:34:35 arshajii

Nie działa dla liczb ujemnych ... '>>> int (bin (-128) [: 1: - 1], 2) ' ' ValueError: niepoprawny literał dla int() z base 2: '00000001b'' –

Ponadto, bardzo dziwne jest to, że każda potęga 2 ma taką samą wartość "1". '>>> int (bin (4) [: 1: -1], 2) = 1',' >>> int (bin (8) [: 1: -1], 2) = 1', '> >> int (bin (16) [: 1: -1], 2) = 1', itd. To odwrócenie zdecydowanie nie jest przechodnie w Pythonie. –

@AndrewMao Tak, ponieważ moc dwójki ma binarną reprezentację w postaci '10000 ... 00', więc przeciwieństwem tego jest zawsze' 1'. – arshajii

Oto moja propozycja:

In [83]: int(''.join(bin(x)[:1:-1]), 2) 
Out[83]: 9987

sam sposób nieco uproszczony.

Źródło

2013-03-02 22:33:08 NPE

Naprawdę nie widzę, że to jest lepsze. Po prostu używa bardziej niejasnej metody odwracania go. Osobiście wolałbym raczej widzieć wersję bardziej szczegółową, ale w dużej mierze bardziej czytelną. –

Jeszcze prostsze bez sprzężenia: 'int (bin (n) [: 1: -1], 2)' –

Uważam aktualna metoda jest w porządku, ale można stracić połączenia list(), jak str.join() zaakceptuje każdy iterable:

def binary_reverse(num): 
    return int(''.join(reversed(bin(num)[2:])), 2)

Byłoby również odradzam korzystania lambda do niczego, ale najprostsze funkcje, gdzie zostanie użyty tylko jeden raz i sprawi, że otaczający kod będzie bardziej przejrzysty dzięki temu, że zostanie wstawiony.

Powód, dla którego czuję, że to jest w porządku, ponieważ opisuje, co chcesz zrobić - wziąć binarną reprezentację liczby, odwrócić ją, a następnie uzyskać numer ponownie. Dzięki temu ten kod jest bardzo czytelny, a to powinno być priorytetem.

Źródło

2013-03-02 22:36:25

Został poświęcony temu rozdziałowi cały rozdział poświęcony tej kwestii (Rozdział 7-1: Cofanie bitów i bajtów) za pomocą operacji binarnych, przesunięć bitów i innych dodatków. Wydaje się, że jest to these are all possible in Python i powinno być znacznie szybsze niż w przypadku metod binarnych do łańcuchów-i-zwrotów.

Książka nie jest dostępna publicznie, ale znalazłem ten wpis na blogu, który omawia niektóre z nich.Sposób pokazany na blogu następujący sposób następujący cytat z książki:

Bit reversal can be done quite efficiently by interchanging adjacent single bits, then interchanging adjacent 2-bit fields, and so on, as shown below. These five assignment statements can be executed in any order.

http://blog.sacaluta.com/2011/02/hackers-delight-reversing-bits.html

Źródło

2013-03-02 22:43:01

To sprawia, że domniemanie o potencjalnej wielkości liczb, które nie są w Pythonie. –

Cóż, jeśli posiadasz 32-bitowe liczby całkowite, wykonujesz 5 operacji, a jeśli masz 64-bitowe liczby całkowite, robisz 6. Nie za ciężko ... –

Z wyjątkiem Python automatycznie będzie promował numery do nieskończenie dużych reprezentacji - [dokumenty state * 'Liczba całkowita ma nieograniczoną precyzję.' *] (http://docs.python.org/3.3/library/stdtypes.html#numeric- typeses-int-float-complex). Potrzebujesz nieskończonych operacji. –

Można to zrobić z operatorami zmianowych tak:

def revbits(x): 
    rev = 0 
    while x: 
     rev <<= 1 
     rev += x & 1 
     x >>= 1 
    return rev

nie wydaje dowolny szybszy niż twoja metoda, chociaż (w rzeczywistości nieco wolniej dla mnie).

Źródło

2013-03-02 23:09:53 Kelsey

>>> def bit_rev(n): 
...  return int(bin(n)[:1:-1], 2) 
... 
>>> bit_rev(2) 
1 
>>>bit_rev(10) 
5

Źródło

2013-05-30 03:41:44

Slick sposób odwrócić (binarne) cyfry liczby w Pythonie?

Odpowiedz

Powiązane problemy