6. labor: számrendszerek, bitműveletek

#include <stdio.h>

/* Bitmintát kiíró függvény */
void bitminta(unsigned char c)
{
    int i;
    /* Ciklus 7-0ig (hogy a legnagyobb helyiérték legyen az első) */
    for (i=7; i>=0; i--)
        /* Minden lépésben elcsúsztatjuk i-vel a számot */
        /* hogy az adott bitje kerüljön a legkisebb helyiértékre */
        /* majd az &1-el levágunk mindent, kivéve a legkisebb helyiértéket */
        printf("%u", (c>>i) & 1);
}

int main()
{
    unsigned char i;

    for (i=0; i<20; i++) {
        bitminta(i);
        printf("\n");
    }

    return 0;
}

#include <stdio.h>

 /* Bitmintát kiíró függvény */
void bitminta(unsigned c)
{
    int i;              
    /* Adott helyiértékű bit kiírása (szóköz vagy 'X') */
    for (i=31; i>=0; i--)
        printf("%c", ((c>>i)&1) ? 'X' : ' ');
}

int main()
{
    unsigned szamok[9]={ 0, 1934128004, 2219346506, 2219346513,
                    1685621663, 340306449, 3813175825, 2048, 0 };
    int i;
    for (i=0; i<9; i++) {
        bitminta(szamok[i]);
        printf("\n");
    }
    return 0;
}

#include <stdio.h>

unsigned bitset(unsigned eredeti, unsigned bit)
{
     /* Veszünk egy 1-est (00...01) amit elshiftelünk az adott helyre */
     /* majd a kapott értéket VAGY kapcsolatba hozzuk az eredetivel */
     /* így az eredetinek az adott értékén biztos 1-es lesz */
     /* a többi pedig nem változik */
    return eredeti | (1<<bit);
}

unsigned bitreset(unsigned eredeti, unsigned bit)
{
     /* Veszünk egy 1-est (00...01) amit elshiftelünk az adott helyre */
     /* a kapott értéket negáljuk, így az adott helyiérték 0 lesz */
     /* a többi pedig 1 (pl. 11110111) */
     /* Ezt ÉS kapcsolatba hozzuk az eredetivel, így az eredeti adott bitje */
     /* biztos 0 lesz, a többi pedig nem változik */
    return eredeti & (~(1<<bit));
}

unsigned bitnegal(unsigned eredeti, unsigned bit)
{
     /* Veszünk egy 1-est (00...01) amit elshiftelünk az adott helyre */
     /* majd a kapott értéket XOR kapcsolatba hozzuk az eredetivel */
     /* így az eredetinek az adott értéke invertálódik */
     /* a többi pedig nem változik */
    return eredeti ^ (1<<bit);
}

 /* Bitmintát kiíró függvény (az előző feladatból) */
void bitminta(unsigned c)
{
    int i;              /* Adott helyiértékű bit kiírása */
    for (i=31; i>=0; i--)
        printf("%c", ((c>>i)&1) ? '1' : '0');
}

int main()
{
    unsigned c = 51;
    bitminta(c); printf("\n");
    c=bitset(c, 5);
    bitminta(c); printf("\n");
    c=bitreset(c, 7);
    bitminta(c); printf("\n");
    c=bitnegal(c, 3);
    bitminta(c); printf("\n");
    return 0;
}

#include <stdio.h>

int main()
{
    unsigned i=1; /* i=00.....01 */
    int hossz=0;  /* Hossz */
    while (i!=0) { /* Amíg el nem tűnik a bal oldalon az 1-es */
        i=i<<1;    /* Addig shifteljük egyesével balra */
        hossz++;   /* És számoljuk, hogy hányszor shiftelődött */
    }

    printf("unsigned hossza: %d bit\n", hossz); /* Eredmény */

    return 0;
}

1. 1e+60
2. inf
3. 1e+30
4. 1000000000000000019884624838656.000000
5. hamis
6. igaz

A 2-es sorban nem két double, hanem két float értéket osztunk el egymással. Az eredmény már nagyobb, mint a legnagyobb, float típus által ábrázolható szám, ezért a gép végtelen nagynak veszi.

A 4-es sorban az látszik, hogy a 10³⁰ értéket a gép nem tudja pontosan ábrázolni (mivel az kettes számrendszerben nem egész szám.)

Az 5-ös és 6-os sor hasonló az előző feladathoz: míg a 10¹⁰+1 értéke különbözik 10¹⁰-től, mivel a két szám nem tér el túlzottan egymástól nagyságrendben, a 10³⁰+1 esetén ez már nem igaz.

Eltérő géptípusok és fordítók esetén az eredmények kicsit mások lehetnek.

#include <stdio.h>

/* Bitmintát kiíró függvény */
void bitminta(unsigned char c)
{
    int i;             /* Adott helyiértékű bit kiírása */
    for (i=7; i>=0; i--)
        printf("%c", ((c>>i)&1) ? '1' : '0');
}

/* Szomszádos bitek cseréje */
unsigned char bitcsere(unsigned char c)
{
    int i;
    /* Végigmegyünk a biteken kettesével */
    /* Kivesszük az i. és i+1. biteket */
    /* Ha nem egyeznek nem egyeznek meg, akkor mindkettőt invertáljuk */
    /*    úgy, hogy egy 3-ast (00000011) a megfelelő helyre shiftelünk, */
    /*    majd XOR kapcsolatba hozzuk az eredetivel, így az adott 2 bit */
    /*    invertálódik */
    /* Ha megegyeznek, akkor nem kell semmit csinálni */
    for (i=0; i<8; i+=2)
        if (((c>>i)&1) != ((c>>(i+1))&1))
            c = c ^ (3<<i);
    return c;
}

int main(){
    unsigned char c=46;
    bitminta(c); printf("\n");
    c=bitcsere(c);
    bitminta(c); printf("\n");

    return 0;
}

#include <stdio.h>

int main()
{
    /* A tömb mérete */
    enum { MERET=1000 };
    unsigned char prim[MERET];
    int i=0;

    /* uresen indulunk - mindent primszamnak tekintunk. */
    /* a feladat itt minden bitet 1-be rakni. kis magia, hogy
     * nem szamonkent megyek, hanem inkabb charonkent. olyan
     * erteket rakok a charokba, ami csupa 1-bol all. */
    for (i=0; i<MERET; i++)
        prim[i]=~0;         /* ~0 - csupa egyesből allo */

    /* megyunk a szitan - MERET*8-ig lehet! */
    for (i=2; i<MERET*8; i++)
        /* es amit talalunk primet */
        /* itt kiszedek egy bitet; a kifejezes erteke 0, vagy az
         * 1, 2, 4, 8... szamok valamelyike. Azok hasznalhatok
         * logikai erteknek: 0, ha nem prim! */
        if (prim[i/8] & 1<<(i%8)) {
            int sz;

            printf("%8d", i);
            for (sz=i*2; sz<MERET*8; sz+=i)
                /* 0-ba allitom azt a bitet. */
                prim[sz/8]=prim[sz/8] & ~(1<<(sz%8));
        }
    printf("\n");

    return 0;
}

Néhány tudnivaló:

• Érdemes összehasonlítani a programot az előző óraival. Az algoritmus tökéletesen megegyezik, csak a tömbbel kapcsolatos műveletek bonyolódtak kicsit.
• Fontos, hogy a szabvány nem köti meg a char előjeles vagy előjel nélküli voltát. Ha számot tárolunk benne, akkor írjuk ki mindig, hogy signed vagy unsigned.
• Amikor egy szám prím voltát teszteljük, akkor a tömbből egy adott bitet kell megvizsgálni. Ha összetett számként jelöljük meg, akkor az adott bitet 0-ba kell állítani.
• Egy unsigned char-ba 8 bitnyi információ fér. Ezért a tömböt [i/8]-cal kell indexelni. A vizsgált bit sorszáma pedig ennek megfelelően i%8 lesz, amely kifejezésnek az értéke 0..7 között változik.

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

int main()
{
    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;
}

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

int main()
{
    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;
}

#include <stdio.h>
#include <math.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()
{
    printf("2 gyoke: %.10f\n", gyok(2));

    return 0;
}

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

void megold(int n)
{
    float b,c;
     /* double b,c; */
    int i;
     /* 10 hatvány 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()
{
     /* Próba... */
    megold(1);
    megold(2);
    megold(4);
    megold(8);

    return 0;
}

#include <stdio.h>
#include <stdlib.h>

/* a betűkre karakterként (számként) tekintek.
 * mivel ábécé sorban vannak, a számjegyek pedig növekvő
 * sorrendben, ezért kisebb/nagyobb összehasonlítást
 * végezhetek, és kivonhatom őket egymásból. */


/* igazat ad vissza, ha a megadott koordinatak nem
 * egy helyes mezot adnak (a1->h8). */
int helytelen_mezo(char o, char s)
{
    return o<'a' || o>'h' || s<'0' || s>'8';
}


/* kivételes eset mindegyik figuránál, ha nem lépett
 * sehova (o1==o2 és s1==s2), hiszen az nem is lépés.
 * ha a két kapott koordinátapár ilyen, a függvény
 * igazzal tér vissza. */
int mozdulatlan(char o1, char s1, char o2, char s2)
{
    return o1==o2 && s1==s2;
}


/* a király egyet léphet valamelyik irányba. ez
 * azt jelenti, hogy a sor- és az oszlopugrás
 * távolságának abszolút értéke maximum egy, de
 * az nem helyes lépés számára, ha mozdulatlan marad. */
int kiralynak(char o1, char s1, char o2, char s2)
{
    return abs(o1-o2)<=1 && abs(s1-s2)<=1 && !mozdulatlan(o1, o2, s1, s2);
}


/* a ló nehéznek tűnik, de nem az. az L alak
 * azt jelenti, hogy a vízszintes elmozdulás 1,
 * a függőleges 2, vagy fordítva. itt a képlet
 * kizárja a mozdulatlanságot. */
int huszarnak(char o1, char s1, char o2, char s2)
{
    return (abs(o1-o2)==2 && abs(s1-s2)==1) || (abs(o1-o2)==1 && abs(s1-s2)==2);
}


/* a bástyánál az oszlop- vagy a sor változatlan.
 * de mindkettő nem lehet ugyanaz, azaz nem lehet
 * mozdulatlan a figura, mert az nem lépés. */
int bastyanak(char o1, char s1, char o2, char s2)
{
    return (o1==o2 || s1==s2) && !mozdulatlan(o1, s1, o2, s2);
}


/* a futónál mindkét irányba ugyanannyit kell
 * mozdulni, úgy jön ki az átlós lépés. */
int futonak(char o1, char s1, char o2, char s2)
{
    return abs(o1-o2)==abs(s1-s2) && !mozdulatlan(o1, s1, o2, s2);
}


/* a királynő mint a bástya és a futó együtt. */
int vezernek(char o1, char s1, char o2, char s2)
{
    return bastyanak(o1, s1, o2, s2) || futonak(o1, s1, o2, s2);
}


int main()
{
    /* a kapott mezők koordinátái */
    char o1, s1, o2, s2;

    /* megkérdezzük a felhasználót. */
    /* a scanf-nél a szóközök elnyelik a whitespace karaktereket. */
    printf("Írd be az első mezőt, pl. d6!\n? ");
    scanf(" %c %c", &o1, &s1);
    printf("Írd be a második mezőt, pl. f8!\n? ");
    scanf(" %c %c", &o2, &s2);

    if (helytelen_mezo(o1, s1) || helytelen_mezo(o2, s2)) {
        printf("Hibás sor- vagy oszlopmegadás!\n");
    } else {
        if (kiralynak(o1, s1, o2, s2)) {
           printf("Ez szabályos a király számára.\n");
        }
        if (huszarnak(o1, s1, o2, s2)) {
            printf("Huszár számára szabályos.\n");
        }
        if (bastyanak(o1, s1, o2, s2)) {
            printf("Egy bástya léphet így.\n");
        }
        if (futonak(o1, s1, o2, s2)) {
            printf("Egy futó számára ez helyes lépés lehet.\n");
        }
        if (vezernek(o1, s1, o2, s2)) {
            printf("A vezér léphet ilyet.\n");
        }
    }

    return 0;
}

A feladat megoldása nagyon jó példa a hátultesztelő ciklus alkalmazására. Minimum egy tippet kérnünk kell – a ciklusmag, amely a tippet kéri, és a beírt számot ellenőrzi, egyszer legalább lefut. Illetve a gép minimum egy számot kitalál, és utána várja a felhasználótól a megfejtést.

A belső ciklusmagban az egyenlőséget nem is kell ellenőrizni, mert azt a ciklus feltétele megteszi. Ha egyenlő a tipp a gondolt számmal, akkor kijövünk a ciklusból, és ott viszont gondolkodás nélkül ki lehet írni, hogy talált.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
    char meg;

    /* Generator inicializalasa. */
    srand(time(0));

    do {
        int gondolt, tipp;

        gondolt=rand()%1000+1;
        printf("Gondoltam egy szamot 1 es 1000 kozott. Talald ki!\n");
        do {
            printf("Mi a tipped? ");
            scanf("%d", &tipp);
            if (gondolt>tipp)
                printf("Nagyobbra gondoltam!\n");
            if (gondolt<tipp)
                printf("Kisebbre gondoltam!\n");
        } while (tipp!=gondolt);
        printf("Gratulalok, kitalaltad! A gondolt szam %d.\n", gondolt);

        printf("Akarsz meg jatszani (i/n)? ");
        scanf(" %c", &meg);
    } while (meg=='i' || meg=='I');

    return 0;
}

scanf()-guruknak: a %c előtti szóköz azt jelenti, hogy a bemeneten eldobjuk a whitespace karaktereket. A %c beolvassa azt is, egyébként semmi más nem. Erre azért van szükség, mert a legutolsó tipp utáni entert az előző scanf még a bemeneten hagyta.

Egy háromdimenziós vektor x, y, és z komponensekből áll. Ezeket egy struktúrába tehetjük, mivel összetartozó értékek, elválaszthatatlanok egymástól, és együtt adnak ki egy vektort.

typedef struct Vektor {
   double x, y, z;
} Vektor;

/* kiirja egy vektor komponenseit */
void kiir(Vektor v)
{
   printf("(%g;%g;%g)", v.x, v.y, v.z);
}

/* osszead ket vektort, visszater az osszeggel */
Vektor osszead(Vektor a, Vektor b)
{
   Vektor ossz;
   
   /* a kivon()-hoz hasonlóan is lehetne */
   ossz.x=a.x+b.x;
   ossz.y=a.y+b.y;
   ossz.z=a.z+b.z;
   
   return ossz;
}

/* kivon ket vektort, visszater a kulonbseggel */
Vektor kivon(Vektor a, Vektor b)
{
   /* az osszead()-hoz hasonloan is lehetne */
   Vektor eredm={a.x-b.x, a.y-b.y, a.z-b.z};
   
   return eredm;
}

/* visszater a ket vektor skalarszorzataval */
double skalarszorzat(Vektor a, Vektor b)
{
   return a.x*b.x + a.y*b.y + a.z*b.z;
}