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

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

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

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

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

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

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

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

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

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

A feladat érdekes része a ciklus megírása: nem ágyazhatunk egymásba a programkódban annyi ciklust, ahány bitünk lesz, hiszen a számuk csak a megoldás közben derül ki.

Viszont tudjuk, hogy pl. 4 bit esetén 0000-tól 1111-ig megyünk; az 1111 értéke (vagy éppen 10000 értéke) meghatározható bitműveletekkel.

#include <stdio.h>

int main() {
    int bitek;
    printf("Bitek száma?\n");
    scanf("%d", &bitek);

    /* táblázat fejléc */
    for (int i = 0; i < bitek; ++i)
        printf("%c", 'A'+i);
    printf("|Q\n");
    for (int i = 0; i < bitek; ++i)
        printf("-");
    printf("+-\n");

    /* 0-tól 1<<bitek-ig megyünk, azaz pl. 0000-tól 1111-ig */
    for (int x = 0; x < 1<<bitek; ++x) {
        for (int i = bitek-1; i >= 0; --i)
            printf("%c", (x >> i) & 1 ? '1' : '0');
        /* akkumuláció; kezdeti érték = első bit */
        unsigned acc = x & 1;
        for (int i = 1; i < bitek; ++i)
            acc = acc & ((x >> i) & 1);
        printf("|%c\n", acc ? '1' : '0');
    }
}

#include <stdio.h>

/* A kiirast megvalosito fuggveny */
void kiir(unsigned a) {
    for (int n = 7; n >= 0; n--)    /* 7-tol nullaig a fejlec */
        printf("%d", n);
    printf("\n");
    for (int 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;
}

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) {
    for (int n = 7; n >= 0; n--)
        printf("%d", n);
    printf("\n");
    for (int 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) {
    for (int n = 7; n >= 0; n--)
        printf("%d", n);
    printf("\n");
    for (int 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;
}

unsigned szam = ..., honnan = ..., db = ...;

unsigned eredmeny = 0, tolt = szam >> (honnan - 1);
for (int i = 0; i < db; i++)
    eredmeny |= tolt & (1 << i);

Pohl László trükkös megoldása az alábbi. (A temp az alsó helyiértékein már a kivágandó biteket tartalmazza. Ebből eldobva az alsó db darabot, invertálva saját magával, az összes többi 1-es eltűnik.)

unsigned temp = szam >> (honnan-1);
unsigned eredmeny = temp ^ (temp >> db << db);

Benedek Zsófia ötlete. (Balra csúsztatva a felső bitek dobhatóak el (aztán vissza), jobbra csúsztatva az alsók. Ez 32 bitesen működik. A két jobbra shift egyébként összevonható.)

unsigned eredmeny = (szam<<(32-(honnan-1)-db)>>(32-(honnan-1)-db))) >> (honnan-1);

Estók Dániel megoldása. (0 = csupa 0, ~0 = csupa 1, ~0<<db = csupa 1, de alul db darab 0, ~(~0<<db) = csupa 0, de alul db darab 1-es, és ez pont a maszk, ami kell.)

unsigned eredmeny = (szam>>(honnan-1)) & ~(~0 << db);

Abonyi József megoldása. (1<<db a fenti maszknál pont eggyel nagyobb szám, ami ráadásul pont kettő hatványa. Ezzel modulózva kivághatók az alsó bitek.)

unsigned eredmeny = (szam>>(honnan-1)) % (1<<db);

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

Egy egyszerű megoldás:

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

unsigned long int eredmeny = 0;
for (int 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);

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 eredmeny;
}

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

    return 0;
}

unsigned long int szam = 123;

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

unsigned int szam = 138;

bool talalat = false;
for (int 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;

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

unsigned int szam = 123;

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

bool eredmeny = db == 6;

/* a naív megoldás, függvényként */
unsigned rotr1(unsigned mit, int db) {
    unsigned eredmeny = 0, i;
    for (int 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));
}

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

int main(void) {
    int n, k;
    printf("n=");
    scanf("%d", &n);
    printf("k=");
    scanf("%d", &k);

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

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

    return 0;
}

#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;
}

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.

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

void megold(int n) {
    float b, c;     /* vagy double: érdemes kipróbálni */
    /* a 10 hatványának kiszámolása */
    c = 1;
    for (int 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;
}

    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;
}