Cvičení Bitových operátorů z knihy o jazyku C

Cvičení Bitových operátorů z knihy o jazyku C
« kdy: 05. 08. 2019, 12:36:53 »
Zdravím,

právě se učím jazyk C z knihy "Programovací jazyk C" od K&R (B. W. Kernihgan & D. M. Ritchie) vydáno Computer Press 2013.

V druhé kapitole, která pojednává mimo jiné o bitových operátorech jsou tato cvičení:


Cvičení 2.6: Napište funkci   nastavbity(x,p,n,y)    , která vrátí X s N bity začínajícími na pozici P nastavenými podle N nejpravějších bitů v Y a ostatní ponechá beze změny.


Cvičení 2.7: Napište funkci    invertuj(x,p,n)    , která vrátí X s N invertovanými bity (to znamená s 1 změněnými na 0 a naopak) začínajícími na pozici P a ostatní ponechá beze změny.


Pozn.: Předpokládá se, že bitová pozice začíná číslem 0 a je na pravé straně. Použil jsem kapitálky proměnných (X,P,N,Y) pro odlišení od ostatního textu. Jinak jsou proměnné samozřejmě psány malými písmeny. Předpokládá se že proměnné mají smysluplné hodnoty.

Ve cvičeních je překladatelská chyba, protože v knize jsou uvedeny funkce:


nastavbity(x,p,n)    a    invertuj(x,p,n,y)


jsou tedy prohozeny parametry mezi oběma cvičeními. Ve výše zmíněných Cvičeních jsem chybu opravil.

Trochu jsem se s tím potrápil, ale nakonec jsem vše vyřešil takto:

Cvičení 2.6:

Kód: [Vybrat]
#include <stdio.h>

int nastavbity(unsigned x, unsigned p, unsigned n, unsigned y);

int main()
{
unsigned x = 150, p = 5, n = 3, y = 11;
unsigned vysledek = nastavbity(x,p,n,y);

printf("%d\n", vysledek);
}



int nastavbity(unsigned x, unsigned p, unsigned n, unsigned y)
{
return x | (y & ~(~0 << (p+1-n))) << (p+1-n);
}


a Cvičení 2.7:

Kód: [Vybrat]
#include <stdio.h>

int invertuj(unsigned x, unsigned p, unsigned n);

int main()
{
unsigned x = 173, p = 5, n = 4;
unsigned vysledek = invertuj(x,p,n);

printf("%d\n", vysledek);
}



int invertuj(unsigned x, unsigned p, unsigned n)
{
unsigned mask; /* maska pro vypocet */

mask = ~(~0 << n) << (p+1-n);

return (x | mask) & ~(x & mask);
}


Chtěl bych se zeptat, jestli máte někdo jiné a lepší řešení. Případně, jestli někdo máte řešení zmíněných cvičení z výše jmenované knihy ke stažení (protože to nikde nemohu najít).

novomente


Re:Cvičení Bitových operátorů z knihy o jazyku C
« Odpověď #1 kdy: 05. 08. 2019, 13:12:10 »
Tak jsem nakonec precijen nasel reseni cviceni na strankach: https://clc-wiki.net/wiki/K&R2_solutions

Tady jsou...(jen jsem uvedl hlavni kody bitovych operaci)

Cviceni 2.6
Kód: [Vybrat]
return ((x & ~(~(~0 << n) << p+1-n)) | ((~(~0 << n) & y) << p+1-n));
Cviceni 2.7
Kód: [Vybrat]
unsigned mask = (~(~0 << p)) ^ ~(~0 << p-n);
return ((x & ~mask) | (~x & mask));

Re:Cvičení Bitových operátorů z knihy o jazyku C
« Odpověď #2 kdy: 05. 08. 2019, 13:18:47 »
To první je určitě špatně, protože takhle nikdy nemůžete vrátit nulu tam, kde původní x mělo jedničku, musel byste použít něco podobného jako máte v tom invertuj(). Ty masky jsou IMHO taky špatně, spíš by to mělo být
Kód: [Vybrat]
~(~(unsigned int)0 << n) << p V invertuj() bude jednodušší použít x ^ mask, což vám invertuje právě ty bity, které jsou v masce a ponechá zbytek.

Pokud víte, kolik má typ bitů (a máte ošetřené nesmyslné vstupy), pak si můžete ušetřit jednu negaci a použít
Kód: [Vybrat]
(~(unsigned)0 >> BITS_PER_INT - n) << p Často se také používá trik s (1U << n) - 1, ale pak je potřeba ošetřit nebo vyloučit n rovné přímo bitové délce typu.

Re:Cvičení Bitových operátorů z knihy o jazyku C
« Odpověď #3 kdy: 07. 08. 2019, 00:58:13 »
Ta inverze muze nad uint32_t vypadat treba takto:
Kód: [Vybrat]
    /* K&R Invert(x, p, n)
     * n = 0..32
     * p >= n - 1; p = 0 points to lsb
     */
    uint32_t x = ...
    x ^= (((uint64_t)1U << n) - 1U) << (p + 1U - n);
coz umoznuje pretypovani na unsigned int o vetsim ranku nez ma x (zde 2^64).

V souvislosti s tim me napadaji 2 veci:
1. Nejsem si zcela jist, ze K&R je dnes zrovna ta spravna literatura pro studium C, notabene pro zacatecnika.
2. Zrovna prace s posuny, mixovani unsigned/signed apod. je v C, pokud nemate nastudovano std. C99, C11,... peklo, nad nimz code reviewisti chrochtaji blahem. Nejde ani tak o algoritmicke vyjadreni problemu, jako o jeho spravny zapis v C, aby se predeslo neprijemnostem pramenicim z "integer promotions", "undefined behaviour" nebo "implementation dependent".
Schvalne si od boku zkuste tipnout, jak na vasem prekladaci dopadne toto:
a) if (-1 < 0x01U)  ...
b) a kdyz uz jsme u tech posuvu
    uint32_t n = 32U;
    uint32_t x = (((uint32_t)1U << n) - 1U);
    uint32_t y = ((1UL << n) - 1U);
    uint64_t z = ((1U << n) - 1U);
    uint32_t w = ((1U << 32U) - 1U);
Pokud vas vysledek neceho moc prekvapi, potom doporucuji kap. 6 std. C99/C11.

Re:Cvičení Bitových operátorů z knihy o jazyku C
« Odpověď #4 kdy: 07. 08. 2019, 17:38:28 »
Probirat bitove operatory nekde na zacatku knihy mi prijde take trochu obtizne. Napriklad "Ucebnice jazyka C" od Herouta probira bitove operatory az na konci knihy (1. dilu).

Kterou ucebnici byste mi doporucil? Zminena khiha od Herouta mi prijde trochu encyklopedicka, tedy u jednoho tematu se rekne hned vsechno, co se kolem daneho tematu toci. Pouzivam ji prave na to. V K&R jsou zase vysvetlene jine dulezite veci.


Re:Cvičení Bitových operátorů z knihy o jazyku C
« Odpověď #5 kdy: 07. 08. 2019, 17:53:11 »
U té učebnice C je hlavně problém v tom, že přeložili i komplet zdrojáky. Zajímalo by mě, koho taková zhovadilost napadla...

Re:Cvičení Bitových operátorů z knihy o jazyku C
« Odpověď #6 kdy: 07. 08. 2019, 22:46:16 »
Kterou ucebnici byste mi doporucil?
Po 29 letech programovani v K&R/C89/.../C11 C vim jedno naprosto jiste, a sice ze vam zadnou knihu doporucit nemohu. Tu knihu si totiz musite najit sam, nebot jeji volba zavisi na vasich dosavadnich znalostech, na tom, zda se ucite programovat, nebo se ucite jazyk, atd. A zacit hledat muzete treba zde:
https://stackoverflow.com/questions/562303/the-definitive-c-book-guide-and-list
Pokud snad mohu nejak radit, vyvarujte se knih, ktere citelne trpi nekterymi z techto problemu:
1. Jsou stare (napr. K&R v jakekoliv verzi vydani). Nereflektuji aktualni zvyklosti a zpusob prace s jazykem.
2. Snazi se uvadet analogie s jinymi jazyky, pripadne primo predpokladaji, ze ctenar prechazi z nejakeho konkretniho jazyka (u nas napr. nevim proc oblibeny Herout a jeho obsese Pascalem - treba je to v poslednich vydanich uz vyskrtane, nevim).
3. Venuji se z hlediska jazyka naprosto nepodstatnym vecem (pul knihy se resi prace s retezci, printf/scanf/getc/putc, file I/O).
4. Knihy jsou nekonecne dlouhe a atakuji hranici 1000 stran. Tvari se encyklopedicky, ale pritom je nepomerne snazsi precist si tech par klicovych odstavcu primo v std. Cxx.
5. Knihy jsou napsany naprosto chaoticky (vetsinou vysledek prace sice jiste zdatneho programatora, ale mizerneho "beletristy").
6. Knihy se utapi v mnozstvi kodu v podobe resenych prikladu, ale kvalita kodu je sporna a spise to vypada, ze autor potreboval naplnit dohodnuty pocet normostran.
Jo a jeste jedna vec z osobni zkusenosti. Rychly posun vpred zaznamenate, pokud se stanete clenem nejakeho kvalitniho pgm. tymu. Ty znalosti a zkusenosti programatorsky starsich kolegu jsou k nezaplaceni.

Re:Cvičení Bitových operátorů z knihy o jazyku C
« Odpověď #7 kdy: 08. 08. 2019, 07:27:38 »
K&R jsem volil take z toho duvodu, abych se dovedel neco o tom, proc ten jazyk C vymysleli tak, jak ho vymysleli. Zaroven bych chtel take tak trochu nakouknout do hardware.

Herouta jsem volil, protoze je prave encyklopedicky a pouzivam ho jako prirucku, kdyz se chci neco konkretniho dovedet.

Hlavne mi jde ale o knizky v cestine.