4. hét: számábrázolás, bitek

Czirkos Zoltán, Nagy Gergely, Pohl László · 2016.08.28.

Gyakorlófeladatok a 4. előadás anyagához kapcsolódóan.

1. Számrendszerek, bitműveletek

Mennyi?

Kis ZH-ban voltak

Mennyi 27|13? Írd le mindkét számot, valamint az eredményt is kettes számrendszerben! Az eredményt tízes számrendszerben is add meg!

Megoldás

  27 = 11011
 |13 = 01101
------------
  31 = 11111

Mennyi 45&57? Írd le mindkét számot, valamint az eredményt is kettes számrendszerben! Az eredményt tízes számrendszerben is add meg!

Megoldás

 45 = 101101
&57 = 111001
------------
 41 = 101001

Mennyi 27^13? Írd le mindkét számot, valamint az eredményt is kettes számrendszerben! Az eredményt tízes számrendszerben is add meg!

Megoldás

 27 = 11011
^13 = 01101
-----------
 22 = 10110

Mennyi (~20) & 13? Írd le mindkét számot, valamint az eredményt is kettes számrendszerben! Az eredményt tízes számrendszerben is add meg!

Megoldás

 20  = 00010100
~20  = 11101011
&13  = 00001101
---------------
   9 = 00001001

Mennyi 0x2A | 0x82? Írd le mindkét számot, valamint az eredményt is kettes számrendszerben! Az eredményt tizenhatos számrendszerben is add meg!

Megoldás

 0x2A = 00101010
|0x82 = 10000010
----------------
 0xAA = 10101010

Mennyi 20|13? Írd le mindkét számot, valamint az eredményt is kettes számrendszerben! Az eredményt tízes számrendszerben is add meg!

Megoldás

 20 = 10100
|13 = 01101
-----------
 29 = 11101

Mennyi 42&54? Írd le mindkét számot, valamint az eredményt is kettes számrendszerben! Az eredményt tízes számrendszerben is add meg!

Megoldás

 42 = 101010
&54 = 110110
------------
 34 = 100010

Mennyi 0x2A ^ 0x36? Írd le mindkét számot, valamint az eredményt is kettes számrendszerben! Az eredményt tizenhatos számrendszerben is add meg!

Megoldás

 0x2A = 101010
^0x36 = 110110
--------------
 0x1C = 011100

Mennyi (~22) & 10? Írd le 22-t, ~22-t és 10-et, valamint az eredményt is kettes számrendszerben!

Megoldás

 22 = 010110
~22 = 101001
 10 = 001010
------------
  8 = 001000

Hexadecimális

Készíts programot, mely a felhasználó által megadott decimális (poz. egész) számot átváltja 16-os számrendszerbe (hexadecimális), és az eredményt kiírja a képernyőre.
(Ehhez a printf()-fel is lehet ügyeskedni.)

Igazságtábla

Készíts programot, mely elkészíti az alábbi logikai függvények igazságtáblázatát, és kiírja a képernyőre: a.) ÉS b.) VAGY c.) NOT d.) NOR e.) XOR.

Bináris szám megadása

Írj programot, mely bekér egy max 16 hosszú bitsorozatot karakterlánc formában karakterenként úgy, hogy csak 0-ás és 1-es karakterek bevitelét engedélyezi. A bevitel végét az enter megnyomása jelzi. Ezután írja ki az ilyen módon kettes számrendszerben megadott szám tízes számrendszerbeli alakját! (Elsőleg legnagyobb helyiértéket adja meg a felhasználó.)

Egyszerű bitműveletek

Írjunk programot, amelyik kér egy nemnegatív számot. Írja ki ezt a számot binárisan. Utána állítsa 1-be a 7. bitjét; állítsa 0-ba a 6. bitjét, és végül negálja a 0. bitjét. Írja ki az így megváltoztatott számot!

Megoldás

#include <stdio.h>

/* A kiirast megvalosito fuggveny */
void kiir(unsigned a) {
    int n;  /* az n-- és n>=0 miatt ez csak int lehet, unsigned nem! */

    for (n = 7; n >= 0; n--)        /* 7-tol nullaig a fejlec */
        printf("%d", n);
    printf("\n");
    for (n = 7; n >= 0; n--)        /* a kapott szam bitjei */
        printf("%d", (a & 1 << n) ? 1 : 0);
    printf("\n");
}

int main(void) {
    unsigned x;

    printf("Kerem a szamot! ");
    scanf("%u", &x);
    printf("Eredeti:\n");
    kiir(x);

    /* a feladat altal eloirt muveletek */
    x = x | (1 << 7);     /* 1-be billentjuk a 7-es bitet */
    x = x & ~(1 << 6);    /* 0-ba billentjuk a 6-os bitet */
    x = x ^ 1 << 0;       /* negaljuk a 0-s bitet */
    printf("1-be a 7-es, 0-ba a 6-os, negalva a 0-s:\n");
    kiir(x);
    if (x & 1 << 5)
        printf("Az 5. bit egyes.\n");
    else
        printf("Az 5. bit nullas.\n");

    return 0;
}

Bitek cseréje – adott sorszámú bitek

Írj egy programrészt, amelyik egy nemnegatív egész számban megcseréli két adott sorszámú bitjét! Az így keletkező számot kell előállítani. A 0. bit a legkisebb helyiértékű.

Megoldás

A lenti megoldás gondolatmenete a következő. Az a_bit és b_bit változókba elmentjük az a. és b. helyiértéken álló számot. Ezután az eredményben mindkét helyen kinullázuk a biteket, aztán ha az egyik helyen 1-es volt, akkor a másik helyen billentjük be 1-esbe utólag, és fordítva. Az a_bit és b_bit változókat logikai értéknek használjuk.

#include <stdio.h>

void kiir(unsigned a) {
    int n;
    for (n = 7; n >= 0; n--)
        printf("%d", n);
    printf("\n");
    for (n = 7; n >= 0; n--)
        printf("%d", (a & 1 << n) ? 1 : 0);
    printf("\n");
}

// a. es b. bitet csereli - ez a feladat megoldasa
unsigned csere(unsigned be, int a, int b) {
    /* ezeket a maszkokat vegig hasznaljuk */
    unsigned a_mask = 1 << a;
    unsigned b_mask = 1 << b;
    /* kivesszuk az adott bitet */
    unsigned a_bit = be & a_mask;
    unsigned b_bit = be & b_mask;
    unsigned eredmeny;

    /* kinullazzuk mindket helyen a biteket */
    /* a_mask|b_mask egy olyan szam, amely mindket helyen
     * 1-est tartalmaz */
    eredmeny = be & ~(a_mask | b_mask);
    /* tulajdonkepp itt tortenik meg a csere.
     * ha a_bit 1-es, akkor a b helyere rakunk
     * be 1-est, es forditva. */
    if (a_bit)
        eredmeny |= b_mask;
    if (b_bit)
        eredmeny |= a_mask;
    return eredmeny;
}

int main(void) {
    kiir(23);
    kiir(csere(23, 1, 3));

    return 0;
}

Másik megoldás: kiveszem a biteket, és egyből eltolom őket a 0. helyiértékre (így az a_bit és b_bit változók 0-t vagy 1-et tartalmaznak). Ezek után kinullázhatom őket az eredeti számban; és az így keletkező számhoz hozzávagyolom a biteket újra, de mindig a másik helyre tolva az elmentett bitet. Még elég sok különböző megoldást ki lehetne találni.

#include <stdio.h>

void kiir(unsigned a) {
    int n;
    for (n = 7; n >= 0; n--)
        printf("%d", n);
    printf("\n");
    for (n = 7; n >= 0; n--)
        printf("%d", (a & 1 << n) ? 1 : 0);
    printf("\n");
}

int main(void) {
    unsigned szam = 23;

    int a = 1, b = 3;   /* ezek lesznek megcserélve */
    /* ezeket a maszkokat vegig hasznaljuk */
    unsigned a_mask = 1 << a;
    unsigned b_mask = 1 << b;
    /* kivesszuk az adott bitet */
    unsigned a_bit = szam & a_mask;
    unsigned b_bit = szam & b_mask;

    /* kinullazzuk mindket helyen a biteket */
    /* a_mask|b_mask egy olyan szam, amely mindket helyen
     * 1-est tartalmaz */
    unsigned eredmeny = szam & ~(a_mask | b_mask);
    /* tulajdonkepp itt tortenik meg a csere.
     * ha a_bit 1-es, akkor a b helyere rakunk
     * be 1-est, es forditva. */
    if (a_bit)
        eredmeny |= b_mask;
    if (b_bit)
        eredmeny |= a_mask;

    kiir(szam);
    kiir(eredmeny);

    return 0;
}

Tükrözve

Készíts programot, mely egy unsigned char típusú változóban tükrözi a biteket, vagyis a legnagyobb helyiértékű bit helyet cserél a legkisebbel (0↔7), a második legnagyobb a második legkisebbel (1↔6) stb.

Adott bitek invertálása

Írj olyan programrészt, amely egy előjel nélküli x számban p pozíciótól kezve n bitet invertál! Például bemenet: x=10110 (binárisan), p=2, n=3-ra a kimenet x=01010.

Páros számú 1-es bit

Kis ZH-ban volt

Írj programrészt, amely bemenetként kap egy pozitív egész számot, és logikai igazat állít elő, ha a szám páros számú 1-es bitet tartalmaz!

Megoldás

int db = 0;
for (; szam != 0; szam >>= 1)
    db += szam & 1;
bool paros = db % 2 == 0;

Mind a 32 bit cseréje

Írj programrészt, amely bemenetként kap egy előjel nélküli egész számot, melyről feltételezzük, hogy 32 bites. Cserélje fel a szám összes szomszédos bitpárját (0. az 1.-vel, 2. a 3.-kal, … 30. a 31.-kel)!

Megoldás

Egy egyszerű megoldás:

unsigned long int miben = 123;   /* bemenet */

int i;
unsigned long int eredmeny = 0;
for (i = 0; i < 32; i += 2) {
    if (miben & 1 << i)
        eredmeny |= 1 << (i + 1);
    if (miben & 1 << (i + 1))
        eredmeny |= 1 << i;
}

Egy nagyon trükkös megoldás:

unsigned long int miben = 123;   /* bemenet */

unsigned long int eredmeny = ((szam & 0xaaaaaaaa)>>1) | ((szam & 0x55555555)<<1);

Bitek cseréje – bármekkora változóra

Vizsga volt

Írj egy olyan programrészt, amely bemenetként kap egy előjel nélküli egész számot, és kimenetként szintén egy előjel nélküli egész számot állít elő! Az utóbbi szám úgy keletkezik, hogy a paraméterként átvett számban megcseréli a szomszédos bitpárokat. Nem tudjuk, hogy az adott gépen hány bites az egész, de biztosan páros bitszámú. Pl. be: 25 → 011001, ki: 100110 → 38.

Megoldás

Itt a 0. bittől érdemes haladni. Két dologra kell figyelni:

  • Mindig az i. és az i+1. bitet cseréljük; utána i-t 2-vel növeljük.
  • És ezt addig csináljuk, amíg a számból ha levágjuk az utolsó i bitet, akkor az eredmény nem 0. Mert ha 0, akkor ott már nincs több 1-es, amit cserélgetni kellene – akármekkora is az int.

Az alábbi minta egy függvényként tartalmazza a megoldást.

#include <stdio.h>

unsigned long int bitcsere(unsigned long int szam) {
    unsigned long int eredmeny = 0;

    int i = 0;
    while ((szam >> i) > 0) {
        /* megjegyezzuk... */
        int egyik = (szam >> i) & 1;
        int masik = (szam >> (i + 1)) & 1;
        /* es rakjuk be oket forditva.
         * fent egyik<->i es masik<->i+1,
         * itt egyik<->i+1 es masik<->i! */
        eredmeny = eredmeny | egyik << (i + 1) | masik << i;
        /* kettesevel tovabb */
        i += 2;
    }
    return szam;
}

int main(void) {
    printf("%lu\n", bitcsere(25));
    printf("%lu\n", bitcsere(38));

    return 0;
}

Hány 0 értékű bit?

Kis ZH volt

Írj programrészt, amely paraméterként kap egy előjel nélküli egész számot, és megadja, hogy a szám hány 0 értékű bitet tartalmaz! A számról feltételezhető, hogy 32 bites.

Megoldás

unsigned long int szam = 123;

int db = 0, i;
for (i = 0; i < 32; szam >>= 1, i++)
    if ((szam & 1) == 0)
        ++db;

Egyesek egymás mellett

Kis ZH volt

Írj programrészt, amely bemenetként kap egy egész számot, melyről feltételezzük, hogy 16 bites. Adjon meg ez egy logikai értéket, amely akkor legyen igaz, ha a számban bárhol található egymás mellett két 1-es értékű bit, amúgy hamis! Pl. 138=10001010 esetén hamis a válasz, 154=10011010 esetén pedig igaz.

Megoldás

unsigned int szam = 138;

bool talalat = false;
int i;
for (i = 0; i < 15; i++)
    if (((szam >> i) & 3) == 3)
        talalat = true;

Egy trükkös megoldás. (Ha egymás mellett két egyes van, eggyel léptetve azok át fogják fedni egymást. Az így kapott számot az eredetivel bitenkénti ÉS-elve ezért nem nullát adnak.)

unsigned int szam = 138;
bool talalat = (szam & (szam << 1)) != 0;

Mindkét oldalról 0

Kis ZH-ban volt

Írj programrészt, amely bemenetként kap egy előjel nélküli egész számot, és megadja, hogy hány olyan 1-es bit van a számban, amelyet mindkét oldalról 0 bit határol! (Értelemszerűen a legalsó és legfelső bit nem lehet ilyen.) Pl. ha a bemenő bitminta 1011101000010101011001010011111, akkor az eredmény 6. A bemeneti számról feltételezhető, hogy 32 bites.

Megoldás

Az alábbi nem a triviális, hanem egy trükkös megoldás. Ha egymás melletti három bitet vizsgálunk, akkor ehhez 010-t kell lássunk. A szam&7 kivág három bitet (mert 7 = 111), ahol ez a 010 (értéke: 2) kell legyen.

unsigned long int szam = ...;

int db = 0, i;
for (i = 0; i < 30; i++, szam >>= 1)
    if ((szam & 7) == 2)
        db++;

Pontosan hat darab 1-es

Kis ZH volt

Írj programrészt, amely bemenetként kap egy pozitív egész számot, és logikai igazat ad meg, ha a szám pontosan 6 db 1-es bitet tartalmaz!

Megoldás

unsigned int szam = 123;

int db = 0;
for (; szam != 0; szam >>= 1)
    db += szam & 1;

bool eredmeny = db == 6;

Rotálás

Kis ZH volt

Írj programrészt, amely bemenetként kap két előjel nélküli egész számot (mit, db), és mit-et db számú bittel forgatja el jobbra, és ezt az értéket adja meg (az előjel nélküli egészeket 32 bitesnek feltételezzük)! A jobbra forgatás azt jelenti, hogy mit bitjei db számú bittel jobbra tolódnak, és a „kieső” bitek a szám elejére kerülnek vissza. Pl. be:
00000000111111111111101010101010 és db = 4, ki:
10100000000011111111111110101010.

Megoldás

/* a naív megoldás, függvényként */
unsigned rotr1(unsigned mit, int db) {
    unsigned eredmeny = 0, i;
    for (i = 0; i < 32; i++)
        if (mit & (1 << ((i + db) % 32)))
            eredmeny |= 1 << i;
    return eredmeny;
}

/* a trükkös megoldás, függvényként */
unsigned rotr2(unsigned mit, int db) {
    return (mit >> db) | (mit << (32-db));
}

Bájtsorrend

Készíts programrészt, amelyik egy 32 bites előjel nélküli szám bájtsorrendjét megfordítja. Például, ha a bemenet 0x11223344, a kimenet legyen 0x44332211. Tételezd fel, hogy az unsigned int a futtató gépen 32 bites!

2. Számábrázolási problémák

Lottó 5-ös

Hányféleképpen lehet n valamiből kiválasztani k valamit? Ezt a kombinatorikában kombinációnak nevezik („n alatt a k”). A lottóban 90 szám van, és 5-öt kell választani; a biztos 5-ös találathoz majdnem 44 millió szelvényt kell kitölteni:

90·89·88·87·86
────────────── = 43 949 268
   1·2·3·4·5

Feladat: írd meg a programot, amely kéri a felhasználótól n és k értékét. (A lottóban n=90 és k=5.) Ellenőrizd a program által adott eredményt! Vajon hibás a programod? Kövesd a változók értékét a nyomkövetőben (különösen a számláló kiszámításánál), és hasonlítsd össze azt a Számológép alkalmazásban kapottal!

/* A nem igazán működő megoldás */
#include <stdio.h>

int main(void) {
    int n, k;
    int i, komb;

    printf("n=");
    scanf("%d", &n);
    printf("k=");
    scanf("%d", &k);

    /* 1, hogy ezt szorozgassuk tovabb */
    komb = 1;
    for (i = n; i > n - k; i--)
        komb = komb * i;
    /* es utana osztjuk a faktorialissal */
    for (i = 1; i <= k; i++)
        komb = komb / i;

    printf("Cnk=%d", komb);

    return 0;
}

Miért helytelen az eredmény? Ellenőrizd a nyomkövető segítségével a gép által végzett számítást. Miért ott téveszti el, ahol? Az egyik fentebbi alapján, az unsigned típus bitjei számának ismeretében magyarázd meg az eredményt!

Hogyan lehetne javítani? Megoldható úgy is, ha maradunk az egész számoknál. Figyeld meg: k=1 esetén a számláló csak 90, a nevező 1. k=2 esetén a számláló 90·89, a nevező 1·2. A nevező miatt osztunk kettővel, de a számlálóban a két tényező közül az egyik biztosan páros, mert n·(n-1) alakú. Ugyanígy k=3-nál a számlálóban van egy szám, amely biztosan osztható 3-mal. Ha a ciklusban minden szorzás után rögtön az osztást is elvégezzük, akkor nem kell tárolnunk a 90·89·88·87·86 művelet eredményét, hanem végig csak kisebb számokat. Írd így meg a programot!

Megoldás

/* A fenti ötlettel javított megoldás */
#include <stdio.h>

int main(void) {
    int n, k;
    int i, komb;

    printf("n=");
    scanf("%d", &n);
    printf("k=");
    scanf("%d", &k);

    komb = 1;
    /* szorzunk es osztunk - lasd a magyarazatot */
    for (i = 1; i <= k; i++) {
        komb = komb * (n + 1 - i);
        komb = komb / i;
    }

    printf("Cnk=%d", komb);

    return 0;
}

Gyök kettő – számábrázolási kérdések

A √2 számjegyei egyesével meghatározhatóak. A számítás elvégzése közben azonban könnyű számábrázolási problémákba botlani.

  • Írj programot, amely a fenti algoritmussal 10−10 pontossággal meghatározza √2 értékét!
  • Milyen típust kell ehhez használni? Meg tudod határozni a gyököt 10−20 pontossággal? Mi történik, ha megpróbálod, és miért?
  • Hasonlítsd össze ezt az algoritmust Hérón módszerével. Vajon melyik gyorsabb? Melyik ad kevesebb lépésből pontosabb megoldást?

Megoldás

#include <stdio.h>

double gyok(double szam) {
    double tipp, novekmeny;
    unsigned lepesszam;

    tipp = 1;
    novekmeny = 1;
    lepesszam = 0;

    do {
        do {
            tipp += novekmeny;
            ++lepesszam;
        } while (szam > (tipp * tipp));

        tipp -= novekmeny;
        novekmeny /= 10;
    } while (novekmeny > 1e-10);

    /* printf("Lepesszam: %d\n", lepesszam); */

    return tipp;
}

int main(void) {
    printf("2 gyoke: %.10f\n", gyok(2));

    return 0;
}

Végtelen ciklus?

Az alábbi program egy olyan ciklust tartalmaz, mely addig fut, amíg egy szám és egy nála eggyel nagyobb szám nem egyenlő egymással. Ha a lebegőpontos típusaink végtelenül pontosak lennének, ez végtelen ciklust eredményezne. Mi a helyzet a gyakorlatban? Próbáld ki float és double típussal is!

#include <stdio.h>

int main(void) {
   float e = 0.0, f = 1.0;

   while (e != f) {
      f *= 2.0;
      e = f+1;
   }
   printf("%f\n%f\n", e, f);

   return 0;
}

Gyökkeresés

Tudjuk, hogy az x3-9x2+23x-15=0 egyenlet egy gyöke 2.2 és 4.5 között található. Írj programot, amely intervallumfelezéses módszerrel kiszámítja az egyenlet gyökét!

Tipp

Az intervallumfelezés módszere egy x_also és egy x_felso értékből indul ki, az ezekhez tartozó függvényértékekről tudjuk, hogy ellentétes előjelűek. Kiszámítjuk az x_kozepe=(x_also+x_felso)/2 értéket: ha az ehhez tartozó függvényérték előjele az x_also-hoz tartozó függvényérték előjelével egyezik meg, akkor x_also=x_kozepe, egyébként x_felso=x_kozepe. (Vagyis az x_also és x_felso távolságát felére csökkentjük úgy, hogy a gyök továbbra is a két határ között legyen.) Az eljárást addig folytatjuk, míg x_also és x_felső „elég közel” nem kerül egymáshoz (pl. epszilon=10-6). Ekkor a gyöknek x_also-t, x_felso-t, vagy az átlagukat tekinthetjük.

Ha sikerült kiszámítanod a gyököt, írd át a programot float típusra (ha eddig nem az volt), és epszilont csökkentsd 10-8-ra (C nyelven 1e-8). Mit tapasztalsz?

(x-1)(x-10n)=0

Írj függvényt, amely megoldja az (x-1)(x-10n)=0 egyenletet! Ehhez alakítsd át az egyenletet x2-(1+10n)x+10n=0 alakba és az együtthatókat helyettesítsd be a megoldóképletbe. A függvény bemeneti paramétere n legyen. Próbáld ki a függvényt n = 1, 2, 4, 8 esetekre és float valamint double típusokkal is! Figyeld meg, hogy mi történik és adj rá magyarázatot!

Megoldás

#include <stdio.h>
#include <math.h>

void megold(int n) {
    float b, c;     /* vagy double: érdemes kipróbálni */
    int i;
    /* a 10 hatványának kiszámolása */
    c = 1;
    for (i = 0; i < n; i++)
        c *= 10;
    b = -(c + 1);
    /* Megoldások kiszámolása/kiírása */
    printf("x1=%f x2=%f\n", (-b + sqrt(b * b - 4 * c)) / 2, (-b - sqrt(b * b - 4 * c)) / 2);
}

int main(void) {
    /* Próba... */
    megold(1);
    megold(2);
    megold(4);
    megold(8);

    return 0;
}

A nagy átverés

Hány olyan x egész szám van, amelyre x = -x?

Megoldás

    bitek      érték

  876543210


  100000000        0

 - 10000000     -128
 ──────────
   10000000     -128

Matematikában egy (a nulla), a számítógépen a kettes komplemens számábrázolás miatt kettő (a nulla és a legnegatívabb szám). Ugyanis a legnegatívabb ábrázolható szám a kettes komplemens esetén nem ugyanakkora, mint a legpozitívabb. 8 biten például -128 és +127, és a -128 bitenkénti ábrázolása pont az, mint ami a +128-é lenne (ha beleférne). Ezért ha 8 biten a -128-at kivonjuk 0-ból, vagyis az ellentettjét vesszük, túlcsordulást kapunk, és saját maga az eredmény.

#include <stdio.h>

int main(void) {
    signed char c;

    c = -128;
    printf("%d\n", c);

    c = -c;
    printf("%d\n", c);

    return 0;
}