Diskuze: bitové operátory příklad

Naučíme tě pracovat na home-office.

Zjistit více...

V předchozím kvízu, Online test znalostí Python 2.7, jsme si ověřili nabyté zkušenosti z kurzu.

Aktivity

Zdenek zapletal

Člen

Zdenek zapletal :8.11.2022 16:35

Ahoj, mám takový problém, musím udělat za úkol program v pythonu, který na vstupu dostane číslo, poté s ním pracuje ve dvojkové soustavě. Můžete si to představit jako větev, na které sedí ptáci v podobě jedniček. každá jednička musí mít vedle sebe vlevo,nebo v pravo souseda jedničku, jinak se z ní stane nula. to znamená, že např. 11010 -> mi vrátí 11000, nebo 01011011 mi vrátí 00011011.

háček je ale v tom, že jediné co můžu v řešení použít jsou bitové operátory (and (&),or(|),xor(^),negace(~), a bitový posun vlevo(<<), nebo vpravo (>>) ) .
kod se totiž v testech kontroluje proti použití loopů,knihoven,build-in funkcí, atd...

mohli byste mi prosím někdo poradit co s tím?

Zkusil jsem: v bitových operátorech tak trošku plavu, zkoušel jsem dohledávat na internetu, jak s nimi počítat tak abych dosáhl výsledku, ale nic jsem nenašel, a z toho co jsem našel jsem toho moc nepobral.

Odpovědět

8.11.2022 16:35

DarkCoder

Člen

DarkCoder:8.11.2022 20:30

Pokud Vám učitel/profesor dal takovýto úkol, pak Vám jistě ukázal jak pracovat s bitovými operátory. Není třeba někde hledat a když už tak toho je plný internet. K vyřešení úkolu nepotřebuješ víc než znalost toho co operátor dělá a představivost. Porovnáš stejné bity pro oba operandy, negace má jeden operand.

Význam bitových operátorů:

AND (&) - oba bity 1 pak 1 jinak 0
OR - alespoň jeden bit 1 pak 1 jinak 0
RIGHTSHIFT - posun bitu o n míst doprava, zprava bity mizí, zleva se doplňují nuly
LEFTSHIFT - posun bitu o n míst doleva, zleva bity mizí, zprava se doplňují nuly
NOT - jeli bit 0 pak 1, jeli 1 pak 0
XOR - oba bity různé, pak 1 jinak 0

A nyní k samotnému řešení:

Máš nějaké číslo. Zjištění, zda na sousedním bitu je 1, je prosté. Abys mohl porovnat bity nalevo a napravo od daného bitu, musíš je dostat na stejnou pozici. Takže na stejné číslo aplikuješ RSHIFT a LSHIFT. bit nalevo dostaneš na pozici testovaného bitu pomocí RSHIFT, bit napravo dostaneš na pozici testovaného bitu pomocí LSHIFT. Nyní bity porovnáš. Jelikož je jedno zda je jedna nalevo nebo napravo, použiješ bitový OR na výsledek SHIFT operací. Tím získáš informaci o tom, zda testovaný bit má souseda 1 nebo ne. Nakonec to musíš uplatnit na původní číslo, takže bit bude jedničkový když oba bity budou jedničkové. Použiješ tedy bitový AND. Výsledkem je nové číslo jehož bity jsou jedničkové pokud sousední bit byl také jedničkový.

Konkrétně:

Např. číslo 91d je 01011011b.

num = 91
lshift = num << 1 dává výsledek 182
rshift = num >> 1 dává výsledek 45
neigbour = lshift | rshift dává výsledek 191
num = num & 91 dává výsledek 27

cože je:

num = num & ((num << 1) | (num >> 1));

což je:

num &= ((num << 1) | (num >> 1));

výsledek je 27d což je 00011011b.

Akceptované řešení
+20 Zkušeností
+2,50 Kč

Nahoru Odpovědět

8.11.2022 20:30

"I ta nejlepší poučka postrádá na významu, není-li patřičně předána." - DarkCoder

Peter Mlich

Člen

Peter Mlich:8.11.2022 20:55

google = Bitová operace pravdivostni tabulky
https://cs.khanacademy.org/…se-operation

0 AND 0 = 0   |   NOT (0 AND 0) = 1 (vsude, kde dava "p AND q"  vysledek 0 bude NOT vysledek 1 a opacne
0 AND 1 = 0   |   NOT (0 AND 1) = 1
1 AND 0 = 0   |   NOT (1 AND 0) = 1
1 AND 1 = 1   |   NOT (1 AND 1) = 0

0 OR 0 = 0   |   NOT (0 OR 0) = 1
0 OR 1 = 1   |   NOT (0 OR 1) = 0
1 OR 0 = 1   |   NOT (1 OR 0) = 0
1 OR 1 = 1   |   NOT (1 OR 1) = 0

0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0

NOT 0 = 1
NOT 1 = 0

Abys to chapal, tohle jsou pravdivostni tabulky.
Slovo pravdivostni je matematicky pojem pro "je pravda", "neni pravda" pro vyslovenou vetu, neboli true/false, neboli 0/1
Uplna prav. tabulka znamena, ze tabulka popisuje vsechny mozne kombinace vstupnich promenych a ukazuje, jaky bude vystup.

Vetsinou se pravdivostni tabulky zapisuji jinak nez ty na khan academy, ale prislo mi, ze to lip asi pochopis. Proste to vypada jako tabulka. a, b jsou vstupy, c, vystup. (nebo se pouziva jeste do zahlavi p q a sloupce operaci a napise se to v jedne velke tabulce vse, viz https://wikijii.com/…/Truth_table - nadpis na strance: Tabulka pravdivosti pro všechny binární logické operátory

operace XOR (vzorecek: a XOR b = c)
a b | c
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 0

Cili, ve tvem pripade, mas zadani:
" každá jednička musí mít vedle sebe vlevo,nebo v pravo souseda jedničku, jinak se z ní stane nula."

11010 -> mi vrátí 11000, nebo
01011011 mi vrátí 00011011


1.
11010 -> mi vrátí 11000, nebo
110.. = abc

2.
každá jednička musí mít vedle sebe vlevo,nebo v pravo souseda jedničku, jinak se z ní stane nula.
kdyz b = 1, pak a = 1 nebo c = 1
return (b==1 AND a==1) OR (b==1 AND c==1) // zjednodusim si to, ze dam b doprostred (na vysledku to nic nezmeni, ale muzu pak dosazovat v poradi a b b c)
return (a==1 AND b==1) OR (b==1 AND c==1)
Soucasne z toho plyne, ze se nejspis prvni bit retezce opisuje a nebo se zanedbava cast podminky a to ale neni receno.

3. takze, kdyz to nakodujes... (text z ukazky prepisu po jednom bitu na radek, 11010)

vzorecek: (a==1 AND b==1) OR (b==1 AND c==1)
1 => opises, [1]
1 => a=1, b=1, c=0 => vzorecek (1==1 AND 1==1) OR (1==1 AND 0==1) => true OR false => true, [1]
0 => a=1, b=0, c=1 => vzorecek (1==1 AND 0==1) OR (0==1 AND 1==1) => false OR false => false, [0]
1 => a=1, b=0, c=1 => vzorecek (0==1 AND 1==1) OR (1==1 AND 0==1) => false OR false => false, [0]
0 => opisujes [0]
cili 11010 se zmeni na 11000, coz odpovida zadani

4. dobra, a jak to udelat pomoci aritmetickych operaci?

11010 - kdyz mas toto binarni cislo, tak
110100 - aritmeticky shift vlevo pridava na konec 0
1101 - aritmeticky shift vpravo maze posledni bit

Co to ale znamena? jedno IT kouzlo... bity preci musis mit vsech stejny pocet. Takze ty operace take muzes prepsat jako

011010 - puvodne:11010
110100 - aritmeticky shift vlevo, puvodne 110100
001101 - aritmeticky shift vpravo, puvodne 1101

A shodou okolnosti, kdyz si vemes bity pod sebou, tak je to sikovne pro ten vzorecek
a=1, b=1, c=0
01b010 - puvodne:11010
11a100 - aritmeticky shift vlevo, puvodne 110100
00c101 - aritmeticky shift vpravo, puvodne 1101
Takze to muzes andovat, orovat jako celek, puvodni cislo, cislo shiftnute vlevo, vpravo.

Predpokladam, ze je to mysleno takhle. A jeste to musis prepsat do pythonu. Tusim, ze se pouzivaji jine operatory pro AND pro cisla typu bit a pro cisla typu integer.

Editováno 8.11.2022 20:57

Nahoru Odpovědět

8.11.2022 20:55

Zdenek zapletal

Člen

Zdenek zapletal :9.11.2022 6:55

Super, díky moc za dovysvetleni, už to chápu lépe.

Nahoru Odpovědět

9.11.2022 6:55

Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 4 zpráv z 4.