Logický bitový posun doprava v Pythonu

Jak jistě z kurzů assembleru víte, existují dva typy bitových posunů doprava: aritmetický a logický. Pokud se tento posun aplikuje na kladné číslo, tak jsou oba typy totožné. Rozdíl nastane u posuvu záporných čísel, kdy logický posun doplňuje zleva nuly, kdežto aritmetický kopíruje znaménkový bit, který je 1 u záporných čísel ve dvojkovém doplňku. Operátor >> v Pythonu je aritmetický posun doprava. Následující příspěvek se snaží o implementaci logického posunu do Pythonu.

Upozornění: V článku vycházím z jistých předpokladů o uložení čísel v Pythonu, z nichž některé jsem si neověřoval. V mé implementaci (CPython) vše funguje. Pokud ale víte, že některý z předpokladů zde učiněných je mylný, určitě to zmiňte do komentáře! Díky.

Kde je hlavní problém?

Hlavní problém je v tom, že všechna čísla v Pythonu jsou se znaménkem a nemají fixní bitovou šířku. Z toho důvodu jste schopni k číslu neustále přičítat, aniž by přeteklo (samozřejmě jen do doby, než vám dojde volná paměť). Problémem je také to, že Python standardně nepodporuje logický posun doprava, pouze aritmetický :).

OK, jak na to tedy půjdeme?

Pokud posouváme kladné číslo, pak lze využít operátor >> (u kladných čísel není žádných rozdíl). Pokud máme posouvat záporné číslo, tak to uděláme následovně: zjistíme si bitovou šířku reprezentace onoho čísla v Pythonu a převedeme toto číslo na kladné číslo tak, abychom mohli využít operátor >>. Při tom využijeme právě oné vlastnosti reprezentace libovolně velikých čísel.

Ilustruji to na příkladu. Mějme číslo -5, které chceme posunout o dva bity doprava. Nechť je -5 uloženo na 32 bitech. Jeho bitová reprezentace ve dvojkovém doplňku je následující:

         11111111 11111111 11111111 11111011

Nejmenší číslo, které již nejsme schopni na 32 bitech reprezentovat, je 2^32 = 4294967296. Jeho bitová reprezentace je (na 40 bitech) následující:

00000001 00000000 00000000 00000000 00000000

Co uděláme, tak k -5 přičteme právě toto číslo, čímž dostaneme 429496721, které je (na 40 bitech) reprezentováno následovně:

00000000 11111111 11111111 11111111 11111011

Všimněte si, že bitová reprezentace části tohoto čísla (mimo počáteční 00000000) odpovídá reprezentaci čísla -5 na 32 bitech. Co je pro nás ale důležité, tak je, že toto číslo je kladné. Nyní totiž můžeme na tomto kladném čísle aplikovat aritmetický bitový posun doprava, který je v Pythonu, a dostaneme kýžený výsledek (reprezentovatelný na 32 bitech):

         00111111 11111111 11111111 11111110

Skutečně, aritmetický bitový posun kladného čísla je shodný s jeho logickým posuvem, protože jeho nejlevější bit je 0.

A jak to bude vypadat v kódu?

Funkci si pojmenujeme lshr, a bude mít dva parametry: posouvané číslo a počet bitů posunutí:

def lshr(x, n):

Jako prví se ujistíme, že posun je nezáporný:

    assert n >= 0

Samozřejmě, místo assertu lze použít i jiný, vámi preferovaný způsob (a zdůvodnit jej v popisu funkce).

Pokud posouváme kladné číslo, tak lze přímo použít operátor bitového posunu z Pythonu:

    if x >= 0:
        return x >> n

Nyní víme, že x je záporné číslo. Vypočteme, na kolik bitech je reprezentováno x. K tomu použijeme funkci getsizeof z modulu sys:

    bitSize = sys.getsizeof(x)

Tato funkce ovšem nemusí vždy vrátit násobky mocnin dvou. Například na mém stroji pro hodnotu -1 vrátí 28 bitů. Interně se ale chová tak, že je tato hodnota uložena na 32 bitech. Z toho důvodu najdeme nejbližší mocninu dvou, a jako bitovou šířku použijeme ji:

    p = 1
    while p < bitSize:
        p *= 2
    bitSize = p

Nyní již stačí k x přičíst potřebné číslo (viz předchozí sekce) a provést aritmetický (v tomto případě již i logický) bitový posun:

    return (x + 2**bitSize) >> n;

Závorky jsou sice nadbytečné, ale pro srozumitelnost je doporučuji ponechat.

Pokud kód (včetně importu modulu sys) spustíme pro hodnoty z předchozí sekce (-5 a 2), dostaneme jako výsledek 1073741822, což je korektní výsledek.

Máš něco na závěr, co bys nám (čtenářům) chtěl říct?

Tento příspěvek vznikl z toho důvodu, že jsem potřeboval v Pythonu logický posun doprava, ale na internetu jsem nenašel žádné univerzální řešení, které by fungovalo pro číslo o libovolné bitové šířce. Pokud víte o lepším řešení, určitě se ozvěte!