Operátorok

2. Operátorok: precedencia és asszociativitás

Operátorok: a kifejezések építőkockái

  • Pl. matematikai műveletek jelei: +, –, *, /
  • Operandusok: amiken a műveletet végzik

Mik az operandusok? – Szabályok

  • Több is lehet: a = -x unáris (unary), b = x-y bináris (binary), azaz egy- és kétoperandusú
  • Precedencia: különfélék „erőssége”, pl. 5+2*3 = 5+(2*3)
  • Asszociativitás: egyformák csoportosítása, pl. a/b/c = (a/b)/c

Az operátorok precedenciája és asszocivitása tehát nem azt határozza meg, hogy egy nagyobb kifejezés melyik részkifejezését értékeli ki időben előbb a program, hanem csak azt mondják meg, hogy melyik operátornak mi az operandusa. Pl. egy a*b+c*d kifejezésben mindegy is, hogy előbb az a*b vagy a c*d részkifejezést értékeljük ki. Ellenben az a/b/c kifejezés egészen mást jelentene, ha az osztás jobbról balra lenne asszociatív, mert akkor a/(b/c)-t értenénk alatta, ami viszont nem ugyanazt az eredményt adja.

3. Operátorok: kifejezésfák

Az operátorok által leírt műveletek ún. kifejezésfákkal ábrázolhatóak. A kifejezésfa megadja, hogy melyik operátoroknak mely értékek az operandusai.

A kifejezésfa már nem tartalmaz zárójeleket, annak a hierarchiája ugyanis egyértelműen meghatározza, hogy mely művelethez mely operandusok tartoznak. Az alábbi rajzokon sárga színnel jelöltük az operátorokat. Az ezekből lefelé kiinduló vonalak adják meg, hogy az adott operátorhoz mely operandusok tartoznak. A kék szín olyan részkifejezéseket jelöl, amelyek önmagukban kiértékelhetőek; ilyenek a változók és a konstansok. Ezekből már nem indulnak ki vonalak lefelé, nincsenek operandusaik.

3 * x + 8

6 * (y - 4)

a == -b

A 3*x + 8 kifejezés egy olyan összeget ad meg, amely két tagból áll. Az első tag egy szorzat (3*x), a második tag pedig egy konstans (8). Vegyük észre, hogy ez nem attól van így, mert a szóközökkel a tagokat csoportosítottuk, és nem is azért, mert bal oldalon van a szorzat! Hanem azért, mert a szorzás művelet magasabb rendű, azaz a * operátor magasabb precedenciájú, mint a + operátor.

Ha nem megfelelő a precedencia, zárójelek közé zárhatjuk az egyes részkifejezéseket, ezzel módosíthatjuk az operátor–operandus viszonyt. A 6 * (y-4) kifejezésben a szorzat jobb oldali tényezője a különbség; tehát egy olyan művelet eredménye (a kivonásé), amelynek a precedenciája amúgy alacsonyabb, mint a szorzásé.

Az utolsó példa az a == -b kifejezést ábrázolja. Ebben két operátor szerepel, az összehasonlítás és az ellentett képzése. Az ellentett magasabb precedenciájú, és csak egyetlen operandusa van, a b változó. Az összehasonlítás operandusai pedig az a változó, továbbá az ellentettképzés eredménye, tehát az a szám, amit a -b kifejezés kiértékelésével kapunk.

4. Operátorok: precedenciatáblázat

OperátorokLeírás
[], (), x.aindexelés, fv. hívás, attribútum elérése
**hatványozás
+x, -xpozitív, ellentett
*, /, //, %multiplikatív: szorzás, osztás, maradék
+, -additív: összeadás, kivonás
is, in, ==, !=, ...komparatív: összehasonlítás
notlogikai tagadás
andlogikai és
orlogikai vagy

2 * 3 ** 4

a * b == c * d

not a and b

Az operátorok precedenciáját (erősségét) mutatja a fenti, amúgy hiányos táblázat. (Néhány operátorról később lesz szó.)

A táblázat tetején lévő, magas precedenciájú operátorok erősebben kötődnek az operandusaikhoz, mint az alul lévők. Tehát ha egy kifejezést értelmeznénk, ezekből kell kiindulni. Ahogy az előző példákon is szerepelt, a 3 * x + 8 kifejezésben a szorzás erősebb precedenciájú, mint az összeadás, és ezért adjuk a szorzathoz hozzá a 8-at. Hasonlóképp, a 2 * 3 ** 4 kifejezés is 2 × 34-et jelent így zárójelezés nélkül is, mert a hatványozás a magasabb precedenciájú művelet. Zárójelezve a 2 * (3 ** 4) lenne ugyanez.

A precedenciatáblázatot úgy alkották meg, hogy intuitív legyen, a szokásos használatnál kevés zárójelre legyen szükség. Nem véletlen, hogy az összehasonlító operátorok alacsonyabb precedenciájúak, mint a matematikai műveletek. Például az a * b == c * d kifejezésben intuíció szerint két szorzatot hasonlítunk össze, és ezt a nyelv is pontosan így értelmezi. Ez úgy valósul meg, hogy a szorzó operátor precedenciája magasabb, az összehasonlítóé pedig alacsony; vagyis a szorzások „magukhoz vonzzák” a tényezőket, mintha (a * b) == (c * d) módon zárójelezük volna a kifejezést. Ugyanez a helyzet a not a and b kifejezéssel: a not a magasabb precedenciájú, ezért azt (not a) and b-ként kell értelmezni zárójelezés nélkül is. Az a-t tagadjuk, és az így kapott logikai értéket hozzuk ÉS kapcsolatba b-vel. Tulajdonképp lehetne akár not (a and b) is, de szándékosan nem az – ha mégis ezt szeretnénk, akkor zárójelezni kell.

Egy érdekesség: az unáris + operátor is létezik, viszont nem csinál semmit. 5 és +5 ugyanaz a szám, ahogy x és +x is ugyanannyi, függetlenül attól, hogy x pozitív vagy negatív. Ezt azért van így, hogy a kódban kiemelhessük, hogy pozitív számról beszélünk, ahogy élő szóban is időnként mondjuk ilyeneket: „plusz öt fok van”.

5. Polimorfizmus és konverziók

Előfordulhat az, hogy egy operátor többféleképp működik?

a = "alma"
b = "fa"

print(a + b) # almafa
c = 5
d = 2
print(c + d) # 7
print(str(c) + str(d)) # 52

Az operátorok jelentése függhet az operandusok típusától:

  • a + b: összeadás, pl. ha a és b is int.
  • c + d: összefűzés sztringek vagy listák esetén.

Ezt polimorfizmusnak nevezzük (többalakúság, polimorphism).

A Python nyelvben nem kell jelezni a forráskódban a változók típusát, mert azok bármilyen típusú objektumok referenciái lehetnek. Ez annyiban kellemetlen, hogy a forráskódból nem mindig látszik, hogy mi történik. Mi a helyzet egy f() + g() kifejezés esetén, ez összeadás vagy összefűzés? Nem tudjuk megmondani, amíg meg nem vizsgáljuk az f() és g() függvényeket – vagy azok dokumentációit –, hogy mit adnak vissza. Ha számokat, akkor összeadás, ha sztringeket vagy listákat, akkor összefűzés. (Ezért is fontos a jó nevek használata a programban: a nev_beolvas() függvénynek már az elnevezése mutatja, hogy sztringet ad vissza.)

Erre már az első időktől fogva figyelünk: ha egy számot akarunk beolvasni a billentyűzetről, az input() függvény visszatérési értékét, a sztringet, át kell alakítanunk: int(input()) vagy float(input()).


Lehet jelezni a konverziókat?

x = 1 # int
y = 3.14  # float
print(type(x + y)) # <class 'float'>

print(str(2) + "3")
print(2 + int("3"))

Kézi konverzió (cast):

  • típusneve(érték) alakú kifejezéssel

Típuskonverzió néha automatikusan is történik. Például egy int-et és egy float-ot összeadva (vagy egy float-ot és egy int-et, a sorrend itt mindegy) az egész számot is valóssá fogja alakítani a nyelv. Így végeredményben az összeg is egy valós szám lesz. Ez az átalakítás logikus, hiszen bővebb halmaz felé megyünk: minden egész szám benne van a valós számok halmazában is. Viszont floatint átalakítást magától nem fog csinálni a nyelv, mert adatot veszítenénk (pl. 2.3-ból 2 lenne, eltűnik a tizedes rész).

Hasonlóképp, automatikus típuskonverzió nem történik akkor, ha nem egyértelmű az eredmény. A 2 + "3" kifejezést nem lehet kiértékelni, TypeError típusú kivételt kapunk. Nem lehet eldönteni, hogy a 2-ből kellene sztringet csinálni (akkor "23" lenne az eredmény), vagy a "3" sztringből int-et (mert akkor viszont 5-öt kapnánk).

Ha szükségünk van konverzióra, akkor az az eddig megismert formában, típusneve(érték) alakú kifejezéssel tehetjük meg. Ilyenkor tulajdonképpen az adott típus konstruktorát használjuk, és az eldönti, hogy miként kell a megadott érték alapján új objektumot létrehozni; ahogyan azt a törtnél is csináltuk.

Ilyen formán a fent említett kifejezések is kiértékelhetők: str(2) + "3" értéke "23", mint sztring; illetve 2 + int("3") értéke 5, mint egész szám. Ezekben az esetekben természetesen az összeadás operátor már nem látja, mi történik; az elsőnél már sztringek vannak az összeadás két oldalán, a második esetben pedig egész számok.

szam = 123
szoveg = szam.__str__()
print(type(szoveg), szoveg)  # <class 'str'>  123

Az ilyen konverziók működését tudjuk vezérelni a saját típusaink (osztályaink) esetén .__float__(self) és .__str__(self) függvények írásával. A float és str típus konstruktorai tulajdonképp nem csinálnak mást, mint meghívják az adott objektum __float__ vagy __str__ nevű függvényeit. Emiatt tudnak bármelyik típus esetén működni, amelyekre ezek definiálva vannak. Ezt használtuk ki a régebbi tört osztályunknál: ott a tört volt sztringgé alakítható, pl. Tort(4, 5)-ből lehetett "4/5" megjelenésű szöveget előállítani.

6. Az érték és a mellékhatás fogalma

Érték és mellékhatás

def dumalos_negyzet(x):
    print("dumalos_negyzet({})".format(x))  # mellékhatás
    return x * x  # érték
    
print("Eredmény:", dumalos_negyzet(3))
dumalos_negyzet(3)
Eredmény: 9

A fenti dumalos_negyzet() függvény egyszerre két dolgot csinál:

  • Kiír valamit a kimenetre.
  • Négyzetre emeli a kapott számot, és visszatér vele.

Erre azt mondjuk, hogy a függvénynek van értéke és mellékhatása is. Az érték a megadott szám négyzete, a mellékhatás pedig a szöveg kiírása. A mellékhatás a programozásban nem jelent rosszat! Tulajdonképpen a print() függvény is egy olyan függvény, aminek mellékhatása van, hogy kiírt valamit. Sőt általában pont azért hívjuk meg, mert ezt várjuk tőle. De ettől még a kiírás technikailag egy mellékhatásnak számít.


Érték és mellékhatás: példák

Összehasonlításképp:

math.sqrt(2)

Érték (value): 1,414
Mellékhatás (side effect): nincs

print("hello")

Érték: None
Mellékhatás: szöveg kiíródása

A fenti példák két függvényhívást mutatnak, és azok értékeit, mellékhatásait. Elvileg még a print() függvényhívásnak is van értéke, mégpedig None – de erre azt szoktuk mondani, hogy nincs neki.

A mellékhatás jelentősége

a = input()
b = input()

print(a, b)
a = random.random() # [0.0, 1.0)
b = random.random()

print(a, b)

A fenti példák olyan függvényeket mutatnak be, amelyeknek mellékhatásuk és értékük is van.

Az input() esetén az érték a beolvasott szöveg. A mellékhatás pedig az, hogy az a sor be lett olvasva, és a legközelebbi híváskor újra várni fog a gép a felhasználóra, új karaktereket kell begépelni. Ha nem lenne ez a mellékhatás, akkor mindig ugyanazt a szöveget kellene kapnunk.

Hasonló a helyzet a véletlenszámok esetén. Az érték a véletlenszám, a mellékhatás pedig az, hogy a modul belső állapota (az álvéletlenszám-generátor belső változói) megváltoznak. Emiatt tud a függvény minden egyes hívásnál új számot adni. Ennek így is kell lennie: szép is lenne egy olyan „véletlen” számsor, amelyik végig csak egyforma számokból áll...

Általában igyekszünk olyan függvényeket írni, aminek csak értéke van, de mellékhatása nincs (mint pl. a math.sqrt()), vagy esetleg csak mellékhatása van, de értéke nincs (mint pl. a print()). Ezt az elvet úgy nevezzük angolul, hogy command-query-separation. Ettől érthetőbb, követhetőbb lesz a program. De látszik, hogy vannak olyan esetek, amikor ez nem teljesíthető, esetleg eleve nem is cél.

A mellékhatás jelenti a változtatás képességét. Matematikai értelemben egy függvénynek nem lehet mellékhatása (pure function), és így bárhányszor meghívva, mindig ugyanazt az értéket kell kapjuk. A fenti példákban láthatóan ez sem igaz, hiszen ugyanazokra a paraméterekre (0 darab paraméterre) mindig más a válasz.

Az értékadás egy operátor?

Egyes nyelvek néha nagyon eltérően definiálják, hogy egyes operátorok hogyan működnek. Különösen igaz ez az értékadásra. Ezt is operátornak szoktuk nevezni, de valójában a Python nyelvben ez egy utasítás.

a == b + 1
print("almafa")
[1, 2, f()]

Kifejezések

a = b + 1 # !
raise ValueError()
while x < 10:

Utasítások


Utasítás: nem írható le egy kifejezés részeként, önálló kódsor.

Egy értékadásból álló sornak nincsen értéke, és egy a = b alakú kódrészlet nem írható le egy másik kifejezés részeként (pl. 3 + (a = b) szintaktikailag helytelen). Ez nem azt jelenti, hogy a fent jelölt sorok nem tartalmaznak kifejezéseket: az a = b + 1 sorból a b + 1 egy kifejezés; az értékadás maga az, ami már utasításnak számít. Hasonlóképp, a ValueError() (függvényhívás) és az x < 10 (összehasonlítás) is kifejezések, de a raise és a while már vezérlésátadó utasítások.

7. Feltételes kifejezés: if–else, mint operátor

if–else, mint operátor

  • Formája: a if feltétel else b
  • Értéke: ha IGAZ a feltétel, a, különben b értéke.
    Mint Excel-ben a HA() függvény.

Ezt az operátort feltételes operátornak szokás nevezni. Két érték közül tudjuk kiválasztani az egyiket, a megadott feltételtől függően. A Python nyelvben a feltételt középre kell írni (sok kritika is éri emiatt). Talán azért találták így ki, mert legjobban így hasonlít a leírt kód egy angol nyelvű mondatra.


Használata

Páros vagy páratlan?

x = int(input("Adj egy számot: "))
print("páros" if x % 2 == 0 else "páratlan")

Itt a "páros" és "páratlan" sztringek közül választjuk ki az egyiket, a szám paritásától függően. A print() függvény paramétere egyetlen egy sztring lesz.

Abszolút érték:

y = -x if x < 0 else x

A kóddal tulajdonképp ezt rövidítjük:

if x < 0:
    y = -x
else:
    y = x

Melyik a nagyobb?

nagyobb = a if a > b else b

A feltételes operátor itt azért jó, mert egyértelműsíti, hogy a nagyobb nevű változónak adunk értéket. Ha utasításokkal fejtjük ki, akkor ez az értékadás már duplikáltan kell megjelenjen. Ilyenkor a kódot olvasva csak akkor fogunk rájönni, hogy a változó mindenképp kapott értéket, ha megnézzük a hamis és az igaz ágat is:

if a > b:
    nagyobb = a
else:
    nagyobb = b

8. A rövidzár tulajdonság: and, or és if–else

A logikai and, or rövidzár tulajdonsága

Gondoljunk egy pillanatra az ÉS, illetve a VAGY műveletek igazságtáblájára. Az alábbiakat mondhatjuk:

  • A and B: ha A=HAMIS, nem számít B, az egész biztosan HAMIS
  • A or B: ha A=IGAZ, a kifejezés értéke biztosan IGAZ

Ha kiderül az elsőből az eredmény, a másodikat nem értékeli ki:

A nyelv ÉS, illetve VAGY operátorai ezt figyelembe is veszik. Ha az első operandusból kiderül az eredmény, a második operandus már ki sem értékelődik. Bár matematikailag ez a két művelet kommutatív, a programozásban emiatt mégsem mindegy, hogy milyen sorrendben írjuk az operandusaikat.

A rövidzár tulajdonságot ki is tudjuk használni! Például:

if b != 0 and a / b > 3: # 0-val osztás?
    ...

if i < len(lista) and lista[i] == valami: # túlindexelés?
    ...

Az if-else kifejezések rövidzár tulajdonsága

Ne erőltessük!

z = alma() if x > y else korte()

A rövidzár tulajdonság olykor hasznos, de mellékhatásokkal kombinálva veszélyes, mert áttekinthetetlen, érthetetlen programokhoz vezet. Tegyük fel, hogy mind az alma(), mind a korte() függvények kiírnak valamit a kimenetre. Ránézésre ebben a sorban azt gondolhatnánk, hogy mindkét kiírás meg fog történni, valójában viszont csak az egyik. Ha x > y, akkor csak az alma() függvény hívódik meg, ha pedig nem nagyobb, akkor csak a korte(). Lehetőleg kerüljük az ilyesmit, ne írjunk ilyeneket! Ne használjunk olyan kifejezést a rövidzár tulajdonsággal rendelkező operátorok operandusaként, amelynek mellékhatása van!

9. Mi az a kiértékelési sorrend?

def egy():
    print("egy")
    return 1
    
def ketto():
    print("kettő")
    return 2

print(egy(), ketto())

Ha mellékhatások vannak a programban, akkor nem mindegy a műveletek sorrendje. Az a = b után b += 1 nem ugyanazt csinálja, mint a b += 1 után a = b: nem mindegy, hogy a növelés előtti vagy utáni értéket másoljuk.

A fenti programrészben meghívjuk az egy() és a ketto() függvényeket is. Az teljesen biztos, hogy az alsó print egy sorba "1 2"-t fog írni, mivel pozicionálisan balról jobbra halad a neki átadott paraméterek megjelenítésével. A kérdés csak az, hogy melyik függvény hívódik meg előbb, tehát hogy a paraméterek milyen sorrendben állnak elő; ugyanis a paramétereket előállító függvényeknek is van kimenete. Vajon előbb az egy, vagy előbb a kettő sztring jelenik meg?

Szerencsére ez definiálva van: a kiértékelési sorrend adott (evaluation order), a függvény paramétereit balról jobbra határozza meg a nyelv. Tehát biztosak lehetünk abban, hogy előbb az egy(), utána pedig a ketto() függvény hívódik.

A kiértékelési sorrend azt rögzíti, hogy az egyes kifejezések értékét milyen sorrendben határozzuk meg.

  • Kifejezésekben, listákban, függvényparamétereknél balról jobbra.
  • Értékadásnál előbb a jobb oldal, utána a bal oldal.

Példa

def beolvas():
    return int(input())


print(beolvas() / beolvas()) # wut

szamlalo = beolvas()
nevezo = beolvas()
print(szamlalo / nevezo) # :)

Elindítjuk ezt a programot, és megadunk neki két számot. Legyenek ezek 4 és 5. Mit ír ki a program, 4/5-öt, azaz 0.8-at, vagy esetleg 5/4-et, 1.25-öt? A két teljesen egyforma beolvas() függvényhívás közül melyik hajtódik végre először, amelyik az osztandót, vagy amelyik az osztót adja?

A válasz itt 0.8, mivel a kiértékelés balról jobbra halad. A bal oldali beolvas() lesz az első, vagyis az első beírt szám az osztandó, a második lesz az osztó.

Ha nem szeretnénk feleslegesen terhelni magunkat, és a programunk következő olvasóját, akkor nem érdemes ilyet írni. Jobb ez külön sorokban: tároljuk el az értékeket a változókban, adjunk azoknak a változóknak érthető nevet, és máris sokkal tisztább a kép!

szamok = [111, 222, 333]
while szamok != []:
    print(len(szamok), szamok.pop())

Ebben a kódban fordított sorrendben írjuk ki a lista elemeit: 333, 222, 111. Kérdés csak az, hogy előtte a sorszámok mik lesznek. A lista hosszát a .pop() előtt vagy után vizsgáljuk? Mert ez nem mindegy. Tegyük fel, hogy épp az utolsó elemnél tartunk, amit kivennénk. Ekkor az elem eltávolítása előtt a lista hossza még 1, utána viszont már 0.

Szerencsére ez definiálva, egyértelműsítve van: mivel a print() függvényhívás paramétereit balról jobbra haladva határozzuk meg, a len() előbb hívódik, mint a .pop().

Még egy nagyon zűrös példa:

szamok = [1, 2, 3]
szamok[int(input())] = int(input())

Adott egy lista. Ennek a felhasználó által adott indexű elemét felülírjuk egy értékkel, amit szintén a felhasználótól kaptunk. Honnan lehet tudni, hogy előbb az indexet, és utána az új értéket kell megadni, vagy fordítva? Ez nem derül ki ránézésre a kódból, hacsak nem kezdünk el a kiértékelési szabályokon gondolkodni (melyik input() hívódik előbb). De nem derül ki a felhasználó számára sem, mert szótlanul csak bemenetre várunk, ő pedig nem tudja, mi a kérdés.

Jobb a kódot így átalakítani:

szamok = [1, 2, 3]
mit = int(input("Mit: "))
hova = int(input("Hova: "))
szamok[hova] = mit

Így a felhasználó is tudja, mi a kérdés. És bármelyik programozó is, aki ránéz a kódra, tudni fogja, melyik beolvasás történik meg előbb; és mi lesz a kapott értékekkel, hogyan lesz felhasználva. A változónevek kifejezik a szándékot (intentional programming).

Számítógép, számábrázolás, számrendszerek

11. Adatok és programok

Notebook számítógép memóriája

Memória működése: számok tárolása

Ez tárolja az adatokat és a programokat.

  • Karakterek → számok
  • Képek → fényesség értékek → számok
  • Hang → levegőnyomás értékek → számok
  • Gépi utasítások (mov, add) → számok

Érdekesség: A végrehajtott program, és az adatok, amelyeken a program dolgozik, lehetnek külön memóriában is. Az első automatikusan működő számítógépek a programot nem a belső memóriájukban tárolták, hanem papírszalagról vagy lyukkártyáról olvasták be azt futás közben. Ennek egyszerűen az volt az oka, hogy nagyon költséges és bonyolult volt relékből (lásd lent) memóriát csinálni. A tervezők pedig ott spóroltak, ahol tudtak.

Ahogyan a technika fejlődött, úgy vált lehetővé, hogy a programot is a központi memóriában tárolják. Ezt az elvet Neumann János (John von Neumann) javasolta kollégáival, és ma Neumann-féle architektúrának nevezzük. Az első ilyen elven működő számítógép az EDVAC nevet viselte. Ez egyben az első kettes számrendszert használó, már nem elektromechanikus, hanem teljesen elektronikus számítógép is volt. A külön programmemória elve a fentiek ellenére nem halt ki: ezt ma Harvard architektúrának nevezzük, az EDVAC-nál régebbi Mark I számítógép nyomán.


Notebook számítógép CPU-ja

CPU működése

Processzor, CPU (central processing unit): Ez hajtja végre a gépi kóddá alakított programjainkat.

  • Elemi, egyszerű lépések: gépi utasítások
  • Ilyenek hajtódnak végre a program futása közben
x += 2
mov  eax, [1055]  ; x memóriából processzorba
add  eax, 2       ; processzor hozzáad 2-t
mov  [1055], eax  ; eredmény memóriába

A számítógép processzora rendkívül egyszerű, gépi nyelvű utasításokat tud csak végrehajtani. A gépi nyelvnél legtöbbször még egy egyszerű változónövelést is három lépésre kell bontani: 1. a változó értékének kiolvasása a memóriából, 2. az érték növelése, 3. az érték visszaírása a memóriába. A processzor a működés közben így legtöbbet a memóriával kommunikál, jóval többet, mint bármelyik perifériával. Főleg, hogy általában a számítógépeknek közös memóriájuk van az adatok és programok számára.

12. Számrendszerek (numeral system)

A római számokkal bizonyos műveleteket, pl. az összeadást nagyon könnyű elvégezni: pl. III + VIII = VIIIIII = VVI = XI. Más műveletek, a szorzás és az osztás bonyolultak. A matematikusok nagy találmánya a nullás számjegy: ez teszi lehetővé azt, hogy tömören (kevés számjeggyel), ugyanakkor helyiértékenként egységes jelölésrendszerrel tudjuk leírni a számokat. A nullás számjegy a leírt számokban helyőrzőként szerepel: a 203 számban pl. azt jelzi, hogy az 2-es a százasok számát tárolja. A hindu-arab számírásban nincs külön jele az egynek, tíznek, száznak, ezernek. (Vegyük észre: a tízes csoportosítás ettől független! A római számokban is létezik már az 1-10-100-1000 fogalma. Nem a tízes csoportosítás a lényeg, hanem a jelölésmód, ami a nulla bevezetésével válik lehetővé.)

A mindennapi életben a tízes számrendszert használjuk. Ebben az egyes helyiértékek a 10 hatványait követik. Ennek oka nagyon egyszerű: azért alakult így ki, mert tíz ujjunk van. Más számrendszerek is használhatóak, és a hindu-arab számírás logikus felépítése miatt ezekben a szabályok pontosan ugyanazok, mint a tízes számrendszerben.

1
1
1

számrendszerek
alappélda
10 decimális1203tíz = 1·103 + 2·102 + 0·101 + 3·100
8 oktális377nyolc = 3·82 + 7·81 + 7·80 = 255tíz
2 bináris1101kettő = 1·23 + 1·22 + 0·21 + 1·20 = 13tíz

A létező legegyszerűbb számrendszer a kettes alapú. Ebben csak kétféle számjegy van, a 0 és az 1. Hogy miért ez a legegyszerűbb? Mert ebben az összeadó és a szorzótábla nem tízszer tízes, hanem mindössze kétszer kettes.

bináris összeadás
+01
001
1110
bináris szorzás
×01
000
101

13. Érdekesség: kapcsolók generációi

A mai számítógépek digitális elven működnek. Csak egész számokkal tudnak dolgozni, amelyeket kettes számrendszerben tárolnak. A kettes számrendszer előnye az, hogy csak két számjegy van benne: 0 és 1. Ez elektronikusan könnyen kezelhető (nincs áram, van áram), ezért a működést kapcsolók adják. Bármi, ami kapcsolóként tud működni, az használható számítógép építésére is.

Az alábbi fényképek a számítógépek generációit mutatják. Ezek elvben nem különböznek egymástól, csak a gyakorlatban, méghozzá abból az egyetlen szempontból, hogy milyen elektronikus, vagy esetleg még elektromechanikus eszközt használtak kapcsolónak. Az első három képen lévő eszköz egyetlen kapcsolónak felel meg, míg a jobb alsó képen látható integrált áramkörön már sok millió kapcsoló van. Összehasonlításképp: 3-4000 kapcsoló használatával már egészen jól használható processzor tervezhető, egy Core i7 processzorban viszont már 730 millió darab van.

Relék (relay): az áram hatására a bennük lévő tekercsben (jobb oldalt) mágneses tér keletkezik, és így lehet vezérelni a kapcsolót (bal oldalt). Egy ilyen eszköz kb. 3-4 cm nagy. Manapság is használnak ilyet nagyobb áramok kapcsolására, pl. autókban is.

Elektroncső (tube): a bennük lévő vákuumban repülő elektronok mozgása vezérelhető az elektromos tér változtatásával. Ezek is viszonylag nagyok: 3-4 cm, ráadásul fűteni kell a belsejüket, hogy az elektronok kilépjenek a fémből.

Tranzisztor (transistor): a félvezető anyagok vezetőképessége (ellenállása) elektromos úton szabályozható, így kapcsolónak is használhatóak. A képen látható tranzisztorban a félvezető szilícium darabka 1 mm-nél is kisebb. A védő fém vagy műanyag tokozás nagyobb, 3-4 mm-es.

Integrált áramkör (integrated circuit): ebben is tranzisztorok vannak, azonban az előzőnél jóval kisebbek. Egy 1 cm2 méretű szilícium lapra akár több tízmillió transzisztor integrálható, amelyek egyesével alig néhány tíz nanométeresek (vagyis méretük egy ember hajszál vastagságának ezrede). A fenti processzor mikroszkóp alatt forgatva egy videón is látható.

14. Binary digit = bit

A számrendszerek közötti átalakítás könnyű: csak el kell osztanunk (vagy meg kell szoroznunk) a számokat, számjegyeket az adott számrendszer alapszámának hatványaival.

Átalakítás kettesből tízesbe

Az átalakítás lépései: a szám számjegyeit (alaki értékek) összeszorozzuk kettő megfelelő hatványaival (helyi értékek). Az így kapott számok (valódi értékek) összege adja az eredményt.

Kettesből tízesbe
számjegy 
helyiérték×64×32×16×8×4×2×1
valódi érték 
Szám: kettő        tíz

Átalakítás tízesből kettesbe

Az átalakítás lépései: a számot leosztjuk kettő első olyan hatványával, amely kisebb nála. Az eredmény egy számjegy, a maradékot pedig felírjuk a következő oszlopba. Így folytatjuk az egyre kisebb hatványokkal, amíg el nem érünk 0-ig. (A legutolsó esetben eggyel osztunk, aminek a maradéka biztosan nulla lesz.) Az osztások során sehol nem kaphatunk 1-nél nagyobb értéket; ha ilyen történne, akkor kettő egy nagyobb hatványától kell indulnunk.

Tízesből kettesbe
maradék 
helyiérték/64/32/16/8/4/2/1
számjegy 
Szám: tíz        kettő

A más számrendszerekbe átalakítás ugyanígy működik, csak az ottani alap hatványait kell használni.

HDD: akár 2 TiB

Bitek és bitcsoportok

bit
Az információ alapegysége: 0 vagy 1.
bájt (byte): a memória (adatkezelés) egysége
Jellemzően 8 bites csoport.
szó (word): több bájtos adategység
Általában 4 bájt (32 bit), vagy 8 bájt (64 bit).

DVD: 4.3 GiB

Előtagok (prefix)

A kettes számrendszerbeli működés miatt a szokásos mértékegységeknek megvan a bináris párja. Bár a kilo- előtag általában ezret jelent, a számítástechnikában inkább 1024-et, azaz 210-t. Ezt azért választották meg így, mert a kettő között nagyon kicsi a különbség. Sajnos gyakran keverik is a kettőt. A merevlemezgyártók például előszeretettel használják a kilo=1000 jelölést, mert így nagyobb kapacitást írhatnak rá az eladott merevlemezekre. Hogy ne kelljen mindig hozzátenni, ha pontosak akarunk lenni, hogy a bináris vagy a decimális prefixumról beszélünk, bevezették a kibibájt, mebibájt stb. jelöléseket. Egy DVD kapacitása így 4,7 gigabájt, azaz 4,3 gibibájt.

kilobájt (kB) és kibibájt (KiB)
103=1000 ≈ 210=1024 bájt.
megabájt (MB) és mebibájt (MiB)
106=1000000 ≈ 220=1048576 bájt.
gigabájt (GB, GiB), terabájt (TB, TiB)
109≈230 és 1012≈240 bájt.

Érdekesség: A „binary digit”, azaz bináris számjegy szókapcsolatot eredetileg „bigit” vagy „binit” néven rövidítették. Később a „bit” szót John Tukey, amerikai matematikus javasolta. (Ő találta ki a „software” szót is.) A bit szó tudományos írásban először Claude Shannon diplomamunkájában szerepelt, amelynek címe A Symbolic Analysis of Relay and Switching Circuits. Ebben megmutatta, hogy az addig telefonközpontokban használt relék segítségével logikai problémák is megoldhatóak. Pár évvel később megépült az első relékből felépített, kettes számrendszert használó számítógép, a Harvard Mark I. Azóta gyakorlatilag nem készül olyan számítógép, amely nem bináris elven működne.

15. Miért érdekel minket ez az egész?

Próbáljuk kiszámítani Python programban, mennyi 210000!

print(2**10000)
print(len(str(2**10000)))
1995063116880758[...]304792596709376  jó sok számjegy
3011  ennyi darab

Most pedig azt, hogy mennyi 1,99910000!

print(1.999**10000)
OverflowError: (34, 'Numerical result out of range') upsz

Mi történt?

Hogyan lehetséges az, hogy a 210000 művelet eredménye kiszámítható, és kapunk egy 3011 számjegyből álló számot – miközben az 1,99910000 kiszámítása pedig túlcsordulást okoz, vagyis olyan nagy szám adódik, amivel nem tud dolgozni a gépünk? Teljesen biztos, hogy az utóbbi kisebb, mert ahogy a hatvány alapját csökkentjük, úgy egyre kisebb az eredmény.

Ha kicsit kísérletezünk vele, rájövünk, hogy a legnagyobb valós szám, aminek a 10000-edik hatványát tudjuk venni, az kb. 1,07 értékű. Az 1,0810000 kiszámítása már ugyanúgy OverflowError hibát eredményez, mint az 1,999 ugyanilyen kitevőjű hatványozása. Pedig az 1,0810000 csak 335 számjegyből áll, vagyis jóval kevesebből, mint a 210000 szám 3011 darab számjegye, ami pedig gond nélkül kiszámítható.

16. Egész számok ábrázolása

A számokat a számítógép kettes számrendszerben, bitekkel tárolja. A biteket az alsó helyiértékektől számozzuk, aszerint, hogy 2 hányadik hatványának felel meg. 20 → 0. bit, 21 → 1. bit stb. A helyiértékek matematikából megszokott neve alapján a legkisebb helyiértékű bitet (least significant bit, LSB) legalsónak, a legnagyobb helyiértékűt (most significant bit, MSB) legfelsőnek nevezzük – lásd a Hardver alapok tárgyon tanultakat.

A számítógép processzora regisztereket tartalmaz, amelyek műveletek közben a részeredményeket tárolják. Ezek a regiszterek egy megadott számú bitből állnak, tehát létezik egy felső korlát, ameddig a processzor „közvetlenül”, hardverből képes dolgozni a számmal. Ezt a következőképpen érhetjük tetten. Számítsuk ki az 10002 értéket egymás után százezerszer, és mérjük meg, mennyi ideig tartott ez! Utána pedig csináljuk meg ugyanezt, de egy sokkal nagyobb számmal, 1000 faktoriálisával! (Ez utóbbi 2568 számjegyből áll.)

10002 – 4 számjegy

import time

x = 1000
start = time.time()
for _ in range(100000):
    y = x**2
stop = time.time()

print(stop-start, "sec")
0.055 sec

(1000!)2 – 2568 számjegy

import time, math

x = math.factorial(1000)
start = time.time()
for _ in range(100000):
    y = x**2
stop = time.time()

print(stop-start, "sec")
3.202 sec

Míg az 10002 százezerszeri kiszámításához elég volt 50 ezredmásodperc, addig a (1000!)2 százezerszeri kiszámításához több, mint 3 másodpercre volt szükség.

Amíg egész számokról van szó, a Python nyelvben bármekkora értékekkel tudunk dolgozni. Ha annyira nagyok a számok, hogy azok már nem férnek el a processzor egy regiszterében, akkor a Python környezet gondoskodik róla, hogy máshogy kezelje. Ilyenkor minél nagyobb a szám, annál több memóriát foglal hozzá, ahol a számot ábrázoló bitek, vagyis a szám kettes számrendszerbeli alakja eltárolható.

Ez nagyjából úgy kell elképzelni, mintha fognánk egy listát, és abba biteket, 0-kat és 1-eket tennénk csak: a listában tárolt egyes számok kicsik, a lista hossza viszont szabadon változhat. Ilyenkor természetesen az elvégzett műveletek is egyre lassabbak; az összeadáshoz annyi műveletet kell végezni, ahány bitből áll a szám, a szorzáshoz pedig annyit, mint a két összeszorzott szám számjegyei számának szorzata (gondoljunk az írásbeli szorzás algoritmusára, amit általános iskolában mindenki tanult). Ezért lassabb látványosan – kb. 60-szor – az 1000 faktoriálisának négyzetre emelése, mint az 1000-é.

17. Valós számok ábrázolása

Mivel a digitális elven működő hardver csak egész számokkal képes dolgozni, a törtek tárolását vissza kell vezetni egész számokra. Ez megoldható egy normálalakszerű sémával, ahol a kitevő lehet negatív is. A normálalak természetesen a gép (és a tervezőmérnökök) kényelme érdekében nem tízes, hanem kettes alapú.

Lebegőpontos ábrázolás (floating point)

± mantissza · 2karakterisztika
  • Pl. 4 = 1·22 = 100kettő, ¼ = 1·2-2 = 0.01kettő
  • Véges a méret: adott bitszám a mantisszának és a kitevőnek
  • Korlátos az ábrázolható számtartomány és a pontosság is

Lebegőpontos számok a számegyenesen

Emiatt a számítások eredménye sokszor pontatlan! Még az is előfordulhat, hogy a+b=a, ahol a egy nagy, b pedig egy kicsi szám. Ez történik (színezve az értékes jegyek):

a    10000000000000.0000000
b   +             0.0000001
    ───────────────────────
a+b  10000000000000.0000001 → 10000000000000 lesz!

Így az == és != operátorokat valós számokon elvileg nem is lenne szabad használni, de a többi is adhat váratlan eredményt. Ehelyett a módszer az, hogy az összehasonlításokat egy adott tűréssel végezzük. Például egyenlőség helyett ezt a kifejezést használuk: abs(a-b)<0.0001. Tehát ha a két szám különbsége kevesebb egy tízezrednél, akkor egyenlőnek tekintjük őket.

18. Lebegőpontos ábrázolás: furcsaságok

Néhány példa a valós számábrázolás pontatlanságaira:

if 0.1 + 0.2 == 0.3:
    print("Egyenlőek!")
else:
    print("Nem egyenlőek!")
print()

szam = 0.0
while szam < 1.0:
    print(szam)
    szam += 0.1
print()

y = 3 ** 1000
try:
    y = 3.0 ** 1000
    print(y)
except OverflowError:
    print("túl nagy")
print()
Nem egyenlőek!
0.30000000000000004
0.0
0.1
0.2
0.30000000000000004
0.4
0.5
0.6
0.7
0.7999999999999999
0.8999999999999999
0.9999999999999999
túl nagy

A tizedek nem ábrázolhatóak pontosan kettes számrendszerben, mert 1/10 = 1/(2*5), tehát nem 2 hatványa. Emiatt sem a 0,1, sem a 0,2 nem ábrázolható, csak közelítőleg; az összegük a kerekítési hiba miatt nem adja ki a 0,3 értéket, hanem 0,30000000000000004-et kaptunk, ami pedig tényleg nem ugyanannyi, mint a 0,3. (Vegyük észre, hogy tízes számrendszerben is pont azok a törtek ábrázolhatóak pontosan, amelyek nevezőjének prímtényezői 2 és 5. Minden másból végtelen, szakaszos tizedes tört lesz.)

A második rész ciklusát vizsgálva is úgy gondolnánk, az 10 sort fog a kimenetre írni. Az első szám a 0,0; az utolsó pedig a 0,9 lesz. 1,0 már nem íródik ki, mert az nem kisebb, mint 1,0.

Ha elindítjuk a programot, akkor viszont 11 sor jelenik meg. Olyan, mintha a ciklustörzs még 1,0-nál is lefutna... A kimeneten viszont látjuk a számítási pontatlanságot: az eredmény hol „eltalálja” a tizedet, hol egy kicsit „mellémegy”.

A harmadik rész egy túlcsordulást mutat. A 3 ** 1000 érték kiszámítható. Ott egész számokkal dolgozunk. A 3.0 ** 1000 már nem. Bár matematikailag a 3,0 egész szám, a tizedesrész kiírása miatt a 3.0 float típusú adatnak számít, így lebegőpontos számként tárolódik. A nagy kivetőjű hatvánnyal pedig beleütközünk a számábrázolás korlátaiba: „elhasználjuk” a legnagyobb karakterisztikát, nincs már több bitünk, ahol a kapott számot tárolni lehetne.

19. Számok a Python forráskódban

dechex
10a
11b
12c
13d
14e
15f

Egész szám (int) típusú literálisok

47: egész szám

  • 0b101111 – kettes számrendszerben (b = Bináris)
  • 0o57 – nyolcasban (o = Oktális)
  • 0x2f – tizenhatosban (x = heXadecimális)

Valós szám (float) típusú literálisok

3.14: valós szám (van benne . vagy e)

  • .45 = 0,45 (a legelső 0 elhagyható)
  • 6.022e23 = 6,022·1023 (normálalak, exponenciális alak)

Pár szó a 16-os számrendszerről. A kettes számrendszerben leírt számok nagyon sok számjegyből állnak. Ezért sokszor helyette a tizenhatos (hexadecimális) számrendszert szoktuk használni. Ez „rokon” a bináris számrendszerrel. A 10…15 alaki értékek jelölésére az a…f vagy A…F betűket használjuk. Mivel 24=16, a bitek négyes csoportokban adnak egy hexadecimális számjegyet. Például 0x9f = 0b10011111, mert 0x9 = 0x1001 és 0xf = 0b1111.

Használhatnánk a nyolcas számrendszert is azzal a céllal, hogy spóroljunk a számjegyekkel. Azzal azonban van egy kis probléma. Manapság szinte mindegyik számítógépen nyolc bites a bájt. Ha egy ilyet nyolcas számrendszerben írunk le, akkor 2-3-3 bites csoportok adódnak: 10'101'111kettő=257nyolc. Ezzel önmagában nem is lenne probléma, azonban ha egy két bájtos, azaz 16 bites számot szeretnénk átírni, akkor az egymás mellé tett bájtok nyolcas átírása eltér attól, mint a két bájtté külön. Ha az előző bitsorozatot kétszer egymás mellé írjuk, annak átírása: 1'010'111'110'101'111kettő=127657nyolc, nem pedig 257257nyolc, ahogyan a két nyolcas számrendszerbeli egymás után írása miatt gondolnánk. A tizenhatos számrendszerrel nincs ilyen probléma, mert ott nem három, hanem négy bit van egy csoportban, és egy bájt nyolc bitje pontosan két csoportot ad. A négybites csoportok angol neve a nibble (esetleg nybble).

20. Ha nagyon sok adatunk van: az array típus

Tömbök: összefüggő memóriaterület

Bizonyos típusú adatokhoz nagyon sok számot kell eltárolnunk, de tudjuk, hogy ezek korlátos tartományban lesznek. Ilyen például egy kép: a fekete színt a 0 jelképezi, a fehéret az 1, és közte a szürkék. Nem szükséges sem kisebb, sem nagyobb számokat ábrázolnunk, és tudjuk, hogy az összes képpont egyforma típusú adat lesz.

Ilyenkor sokkal hatékonyabb lehet a programunk – mind memóriahasználat, mind sebesség – terén, ha egyforma típusú adatokat nem listába tesszük, hanem egy tömbbe (array). Ez egyrészt nem referenciákat tárol, hanem az adatokat érték szerint (tehát a memóriában a tényleges számértékek egymás mellett lesznek), másrészt pedig fix, ismert típusú és méretű (ismert számú bájtból álló) adatokat egymás mellett.

Az array modul array típusával hozhatunk létre ilyen tömböt. Ennek meg kell adni az egyes tárolt számok típusát (lásd lentebb), ez meghatározza az ábrázolható számtartományt. Másrészt pedig megadhatunk kezdeti értékeket, amik meghatározzák a tömb méretét; vagy később .append() segítségével nyújthatjuk a tömböt.

a = array.array('B', itertools.repeat(0, 1000)) 

a[12] = 37
try:
    a[13] = 370
except OverflowError:
    pass
array típusok
jelölésnévméret (bájt)tartomány
b, Bbyte10 ... 255
h, Hshort20 ... 65535
l, Llong40 ... 4294967295
ffloat4≈10±38
ddouble8≈10±308

Az összefoglaló táblázat az array típus első paramétereként használható típusjeleket tartalmazza. A byte, short és long típusok egész számokat képesek tárolni. Mindegyiknek van előjeles (kisbetűs) és előjel nélküli (nagybetűs) változata. A tartományt az előjel nélküli változatra adtuk meg; előjeles változat esetén ugyanekkora tartományról van szó, de felével el van tolva a negatív irányba. (Például 'b' esetén –128 ... +127 értékű.)

A float és a double típus lebegőpontos számokat tárol. Ezek mindig lehetnek negatívak is, viszont a fentebb részletezett számítási pontatlanságok előjöhetnek a használatuk közben bármikor. Mindkét típus mérete véges, tehát adott egy pontosság: a floatnál ez kb. 6 tizedesjegy, a double-nél kb. 15), és egy ábrázolási tartomány – ahogy a táblázat mutatja. A Python kódunkban használt lebegőpontos számok egyébként az itteni double típussal egyeznek meg.

Van még két típus, amelyek a fenti array-hez hasonlóak; ezek a bytes és a bytearray. Fájlkezelésben fogjuk használni őket később. Amúgy a működésük nagyjából megegyezik a B-vel (előjel nélküli bájt típussal) használt array-ével.

21. A túlcsordulás élőben

Az alábbi példa kód létrehoz egy egyelemű tömböt, csak azért, hogy a korlátos számábrázolás azon az egy elemen bemutatható legyen.

import array


a = array.array('B', [0])   # byte
while True:
    try:
        a[0] += 1
    except OverflowError as e:
        break
print(a[0], "még belefért")
print()


f = array.array('f', [1.0]) # float
for _ in range(0, 20):
    f[0] *= 1000
    print(f[0])
print()
255 még belefért

Az első kódrészletben egy bájt típusú számon dolgozunk. Ahogy ezt növelgetjük egyesével, előbb-utóbb elérjük a 255-öt, amihez 1-et adva már 256-ot kapnánk – egy olyan számot, amelyik 8 biten már nem fér el. Érdemes kipróbálni más típusokkal is (pl. b, h vagy H – a long már nem igazán kivárható).

1000.0
1000000.0
1000000000.0
999999995904.0
999999986991104.0
9.999999843067494e+17
9.999999496721332e+20
9.999999417908338e+23
9.999999146971785e+26
9.999999394896025e+29
9.999999171244748e+32
9.999998824621537e+35
inf
inf
inf

A lebegőpontos típusok másként reagálnak a túlcsordulásra. Amellett, hogy pontatlanok, ezeknél a túlcsordulás nem eredményez kivételt – helyette egy speciális inf (végtelen) értéket vesz föl a tömbelem. Létezik -inf is a negatív túlcsordulás jelölésére.

A Python beépített float típusa egyébként az array d-vel jelölt típusának felel meg (double), és kb. ±10308 az ábrázolási tartománya.

Bitműveletek

23. Boole-féle algebra

Lásd:
Hardver alapok

A számítógépek processzorai – mivel maguk is bitekkel dolgoznak – általában tartalmaznak olyan gépi utasításokat, amelyekkel a tárolt számok egyes bitjeit tudjuk állítgatni, mégpedig a Boole-féle algebrából ismert műveletekkel. Ebben az algebrában a változóknak két értékük lehet: HAMIS és IGAZ, vagy bitekben gondolkodva 0 és 1.

A bitműveletek segítségével az egész szám típusú értékek egyes bitjeit is elérjük. Ezeket a műveleteket sok területen alkalmazhatjuk:

  • Minden bit kihasználása, tömörítés: egy 8 bites változóba 8 IGAZ/HAMIS értéket sűríthetünk.
  • Hardverközeli programozás: hardvereszközben adott bit 1-esbe állításával bekapcsolunk egy funkciót, pl. grafikus kártyán egérmutató láthatósága.
  • Hálózatprogramozás: egy internet adatcsomag adott bitjei jelzik, hogy kapcsolat létrehozása, lebontása stb. történik-e.
  • Kriptográfia és véletlenszámok: titkosítási és ellenőrző összegeket előállító algoritmusok, pszeudo-véletlenszámokat előállító algoritmusok.

A legfontosabb, a Python nyelvben is megjelenő műveletek a következők.

NEM
(NOT)
AA
01
10
ÉS
(AND)
ABAB
000
010
100
111
VAGY
(OR)
ABA+B
000
011
101
111
KIZÁRÓ VAGY
(XOR)
ABA⊕B
000
011
101
110

Érdemes megvizsgálni ezen műveletek tulajdonságait egy különös szemszögből: az egyik bemenetet változatlanul hagyva azt figyelni, hogyan reagál a kimenet a másik bemenet megváltozására. Az igazságtáblák alapján:

  • Az ÉS műveletnél: ha az egyik bemenet A = 0, akkor a másik, B bemenet értékétől függetlenül 0 jelenik a kimeneten. Ha az előbbi bemenet A = 1-es, akkor a kimenet értéke azonos lesz a másik bemenettel; mintha lemásolná azt.
  • A VAGY műveletnél: ha A = 0 bemenetet adunk, akkor a kimeneten mintha a B értéke jelenne meg. Ha A = 1-et, akkor viszont fixen 1 a kimenet. Másképp fogalmazva, ez a művelet lemásolja az egyik bemenetét, ha a másik 0, és fixen 1-et ad a tőle függetlenül, ha a másik 1.
  • XOR (exclusive or): ha az egyik bemenet 0, akkor a másikat lemásolja. Ha az előbbi 1-es, akkor pedig az utóbbit negálva másolja. Vagyis mintha egy ki-bekapcsolható inverter lenne.

A következő pontok feladatainál kiderül majd, hogy miért hasznosak ezek a megfigyelések.

Egy nagyon fontos megjegyzés előzetesen: a bitenkénti műveletek nem keverendőek a logikai műveletekkel! Míg a bitenkénti műveletek egy vagy két szám, azaz int típusú érték azonos helyiértékű bitjein dolgoznak páronként, addig a logikai műveletek bool típusú értékekkel. Míg a bitenkénti ~ művelet egy egész szám összes bitjét ellentettjére állítja, a logikai not művelet a TrueFalse értékeket cseréli. Ugyanígy, a bitenkénti | nem ugyanaz, mint a logikai or, és a bitenkénti & mást csinál, mint a logikai and művelet. A ^ kizáró vagy műveletnek nincsen logikai párja. Vagyis de: a != operátor végülis az, ha bool típusra használjuk.

24. Bitműveletek: léptetés (shift)

A léptető operátorok egy szám bitjeit eltolják.

Balra léptetés: << operátor

   10000110  előtte
10000110000  balra 3-mal
x = 134 << 3
  • Alulról három nulla jön be.
  • Mintha szoroznánk 23-nal.

Jobbra léptetés: >> operátor

01010110 előtte
  010101 jobbra 2-vel
x = 86 >> 2
  • Az alsó kettő elveszik.
  • Mintha osztanánk 22-nal.

Figyelem! A bitenkénti léptetés operátorok ugyanolyanok, mint az összeadás vagy a szorzás: két operandusuk van, és létrehoznak egy harmadik számot, az eredményt. Eközben a két operandusukat nem változtatják meg, nincs mellékhatásuk! A b = a << 3 kifejezés így az a változó értékét változatlanul hagyja, és csak b változik. A többihez hasonlóan viszont ezeknek is megvan a rövidített, értékadó párjuk:

  • x <<= 3 ugyanaz, mint x = x<<3, és
  • x >>= 2 ugyanaz, mint x = x>>2.

Feladat: írjuk ki 2 hatványait!

for i in range(0, 32):
    print("{:2}. {:10}".format(i, 1<<i))

25. A bitenkénti VAGY művelet: |

|
„pipe”,
álló vonal

A VAGY operátor | két szám bitjeit hozza VAGY kapcsolatba páronként. Ez minden helyiértéken így lesz, vagyis az egyik szám 0. bitje és a másik szám 0. bitje, az egyik szám 1. bitje és a másik szám 1. bitje, és így tovább.

A VAGY műveletnél az eredmény 1, ha bármelyik 1. Ezt adott bitek 1-be állítására szokás használni. Figyeljük meg: ha az A = 0 bemenetet választjuk, akkor a kimeneten a B értéke jelenik meg. Ha az A = 1-et, akkor pedig fixen 1 a kimenet. Tehát a VAGY művelet lemásolja az egyik bemenetét, ha a másik 0, és fixen 1-et ad a tőle függetlenül, ha a másik 1.

VAGY
 A  B A|B
000
011
101
111
VAGY – kattints a számokra!
76543210
A 00100000
B 01001010
A|B 00000000

Feladat: állítsuk egy szám 5. bitjét 1-be!

  • Olyan maszk (mask) kell, amiben az 5. bit 1-es, a többi mind 0.
  • Ez a szám az 1<<5:
    00000001 1
    00100000 1<<5
  • x = x | 1<<5 vagy egyszerűbben: x |= 1<<5

26. A bitenkénti kizáró vagy: ^

^
„caret”,
kalap

A kizáró vagy ^ két operandusának ugyanolyan sorszámú bitjeit hozza KIZÁRÓ VAGY kapcsolatba. Mivel a KIZÁRÓ VAGY műveletnél az eredmény akkor 0, ha egyformák a bemeneti bitek, és akkor 1, ha nem egyformák, ezt adott bitek negálására szokás használni. Digites terminológiában: a KIZÁRÓ VAGY kapu a vezérelhető (ki/bekapcsolható) inverter.

KIZÁRÓ VAGY
 A  B A^B
000
011
101
110
KIZÁRÓ VAGY – kattints a számokra!
76543210
A 00011000
B 01001010
A^B 00000000

Feladat: negáljuk egy szám 3. és 4. bitjét!

  • A maszk: 1<<3 | 1<<4
  • Tehát: x = x ^ (1<<3 | 1<<4)
  • Vagy másképpen: x = x ^ 1<<3 ^ 1<<4

Az x = x^y kifejezés rövidítve is írható: x ^= y, vagyis a fenti példa rövid változata: x ^= 1<<3 | 1<<4.

27. A bitenkénti ÉS művelet: &

&
„et” vagy
„és” jel

Az & operátor két operandusának ugyanolyan sorszámú bitjeit hozza ÉS kapcsolatba. Ezzel meg tudunk vizsgálni, ki tudunk vágni egy adott bitet egy számból. Miért? Mert ennél a műveletnél ha az egyik bemenet 0, akkor a másik bemenet értékétől függetlenül 0-t ad a kimeneten. Ha az előbbi bemenet 1-es, akkor viszont az utóbbit lemásolja, változatlanul megjeleníti a kimeneten. Olyan, mintha az egyik bemenet 0 értékével letiltanánk a másikat.

ÉS
 A  B A&B
000
010
100
111
ÉS – kattints a számokra!
76543210
A 00001000
B 01001010
A&B 00000000

Feladat: ellenőrizzük, egyes-e a szám 3. bitje!

  • Vágjuk ki csak azt a bitet, minden másikat nullázva
  • A maszk: 1<<3
  • Tehát: if x & 1<<3 != 0: …

28. A bitenkénti tagadás: ~

~
„tilde”,
hullámvonal

A ~ operátor a bitenkénti negálás jele. Ezt egy szám vagy változó neve elé írva olyan számot kapunk, amelyben minden bit ellenkezőjére (negáltjára) változik. Ez lényegében megegyezik -x - 1-gyel, mivel a szám belül kettes komplemens ábrázolásban tárolódik.

NEM – kattints a számokra!
76543210
A 00001000
~A 00000000

Az ÉS művelettel együtt ezt arra is használhatjuk, hogy egy adott szám valamelyik bitjét 0-ba állítsuk. Ennek segítségével lehet ugyanis könnyedén előállítani olyan maszkot, ami csupa 1-esből áll, csak egy megadott helyen van benne 0-s bit. Ezzel az 1-esek helyén „engedélyezzük”, a 0 helyén pedig „letiltjuk” a bitet.

ÉS
 A  B A&B
000
010
100
111
ÉS – kattints a számokra!
76543210
A 11110111
B 01001010
A&B 00000000

Feladat: állítsuk egy szám 3. bitjét 0-ba!

  • Maszk, amelyben csak a 3. bit 0: ~(1<<3), mert:
    00000001 = 1
    00001000 = 1<<3
    11110111 = ~(1<<3)
  • Tehát: x = x & ~(1<<3) vagy rövidebben: x &= ~(1<<3)

29. Példa: Eratoszthenész szitája, spórolósan

Egy bájtban, amennyiben az 8 bites, 8 logikai értéket lehet tárolni. Írjuk meg a labor „Eratoszthenész szitája” feladatát úgy, hogy egy bájt típusba tömörítse 8 egymás melletti szám prím/nem prím tulajdonságát – azaz csökkentsük nyolcadára az ottani program memóriahasználatát!

Ebben a programban 8000-ig fogjuk vizsgálni a prímszámokat. A létrehozott tároló most bool lista helyett 1000 elemű byte array lesz. Az eredeti változatban 8000 logikai érték (bool) volt; most 8 logikai értéket, bitet sűrítünk egy bájtba, és így a tömbnek már csak 1000 eleműnek kell lennie. Mindegyik logikai érték megtalálható ebben a tömbben, valahányadik bájt valahányadik bitjeként. Mivel minden bájt 8 bitből épül fel, egy vizsgálandó sz sorszámhoz a bájt sorszámát az sz//8 kifejezéssel kaphatjuk meg. Azon belül a bit sorszámát pedig az sz%8 kifejezés adja.

[0]01234567
[1]89101112131415
[2]1617181920212223
......
import array

prim = array.array('B')
for sz in range(1000):
    prim.append(0b11111111)
for sz in range(2, 8000):
    if prim[sz//8] & (1 << sz%8) != 0:
        for t in range(sz*2, 8000, sz):
            prim[t//8] &= ~(1 << t%8)
for sz in range(2, 8000):
    if prim[sz//8] & (1 << sz%8) != 0:
        print("{:8}".format(sz), end="")

A program elején „teli”, csupa 1-ekből álló tömbbel indulunk: mindent prímszámnak tekintünk. Ezért a tömböt feltöltjük olyan értékekkel, amely csupa 1-es bitekből áll.

Ezután megyünk végig a szitán az sz-es ciklussal. A tömb 1000 elemű, de minden elem 8 bitet tárol, ezért 8000-ig tudjuk vizsgálni a számokat. Amint találunk egy prímet, annak a többszöröseit húzzuk majd ki. A bit vizsgálatához a bitenkénti ÉS & műveletet használjuk: előállítjuk az 1 << sz%8 maszkot, amely csupa 0-ból áll, kivétel az sz%8-adik bitet, ahol 1-es van. Ezt a maszkot ÉS-elve a tömb eleméhez 0-t kapunk, ha a vizsgált bit nulla értékű, amúgy pedig nem nullát.

A t-s ciklus húzza ki az sz többszöröseit a tömbből, vagyis jelöli be, hogy nem prímek. Ehhez nullába kell állítania a többszöröshöz tartozó bitet, ami a bitenkénti ÉS & művelettel tehető meg.

A program végére a következő apró kódrészletet téve láthatóvá válik a tömb eleje:

print()
for b in range(0, 10):
    bits = "{:08b}".format(prim[b])
    print(bits[::-1])

Ebben az 1-es bitek jelölik a prímszámokat (kivéve a legelső kettőt, mert azok a 0-nak és az 1-nek felelnek meg, de azokkal nem foglalkozunk):

11110101
00010100
01010001
00000101
00000100
01010001
00000100
00010100
00010001
01000001