Práce s bitovým polem realizovaného pomocí pole celočíselného typu

Úkol

Napište modul (hlavičkový a zdrojový soubor) pro práci s bitovým polem libovolné délky. Pole je realizováno vhodným celočíselným datovým typem a navržené funkce umožňují práci s jednotlivými bity v tomto poli.

Napište funkce, které v daném poli umožní:
- nastavení daného bitu
- nulování daného bitu
- zjištění hodnoty daného bitu
- změnu hodnoty daného bitu (0 <->1)

Názvy souborů budou bitmain.c, fbit.c, fbit.h.

Doporučený postup:

1. Zvolíme vhodný datový typ pro uložení pole. Jelikož pracujeme s bitovými operátory/operacemi bude to typ bezznaménkový celočíselný. Zvolíme unsigned int.
   Jelikož se jedná o pole s rozměrem je možné ho též realizovat jako strukturu dat a délky.

2. Zjistíme počet bitů v jedné proměnné daného typu PocetBitu. Jelikož počet bitů v daném typu je v jazyce C závislý na platformě a procesoru, nelze pro počet bytů (a tedy ani bitů) použít hodnoty z prostředí, kde právě pracujeme.
   Pro zjištění počtu bytů daného typu použijeme klíčové slovo jazyka _____________________.
   Výsledná délka typu je v násobcích byte (char vrací hodnotu 1). Kolik bitů obsahuje jeden char je určeno v knihovně limits.h v proměnné CHAR_BIT.
   Počet bitů v jedné proměnné daného typu je: PoceBitů = PocetBytů * CHAR_BIT

3. Na základě požadovaného počtu bitů určíme potřebnou délku pole. Pro začátek zkusíme pole o tisíci bitech. Zjistěte potřebný počet prvků typu unsigned int. Vzorec výpočtu si můžete vyzkoušet na úvaze, že pro jeden až osm bitů je potřeba jeden byte. Tedy najít vzorec, který pro vstup od jedné do osmi dá výsledek jedna (od 9 do 16 výsledek 2 ...).
   Alokujte pole pro tisíc bitů. Nezapomeňte ho odalokovat.
   Zkontrolujte, zda vám vypočet dává správné výsleky pro N = {1,7,8,9,11,14,15,16,17,31,32,33,63,64,65}.
   Pozn. Počet bitů jde od jedné, ale indexy od nuly.

4. Dále provedeme nastavení pole pomocí funkce Init. Funkce Init má tři parametry: pole, jeho délku v bitech a hodnotu 1 nebo nula, která určí zda chceme dané pole naplnit jedničkami nebo nulovat.
   void Init(usigned int *aPole, size_t aPocetBitu, int aValue)
   Pole nemusíme plnit po bitech, ale můžeme ho naplnit po bytech hodnotou nula, nebo hodnotou složenou pouze s jedniček (tu vytvoříme bitovou negací bezznaménkové nuly). Uvědomte si, že standardně psaná „0“ (nula) je typu int; „0.“ (nula s tečkou) je typu double; „0l“ (nula s „el“) je typu long.
   Ve funkci main vytvořte dvě proměnné po tisíci bitech – jednu vynulujte (Prom0) a jednu nastavte na jedničky (Prom1). Obě proměnné (v cyklu ve funkci main, pomocí tisku hexa čísel) vytiskněte a ověřte správnost nastavení.

5. Napište funkci Nastav pro nastavení daného bitu v poli. Funkce Nastav bude mít tři parametry: pole, jeho délku v bitech a číslo bitu, který se má nastavit na jedničku.
   int Nastav(unsigned int *aPole, size_t aPocetBitu, size_t aIndexBitu)
   Nejdříve provedeme kontrolu, zda je požadovaný bit uvnitř pole (je nezáporný a menší než délka pole). V případě chyby vrátíme hodnotu 1, jinak 0.
   Následně určíme prvek (index) v poli, ve kterém se nalézá daný bit (použijeme celočíselné dělení daného bitu počtem bitů v jednom prvku pole).
   Má-li tedy zvolený datový typ délku 16bitů , potom při požadavku na zápis 33 bitu, určíme, že se nachází v prvku pole s indexem dva (tj. třetí prvek!!!; prvek s indexem nula má bity 0-15, s indexem jednamá bity 16-31 a bit 33 je tedy až ve třetím prvku pole, který má pro číslování v C, které je od nuly index dva).
   Známe tedy prvek pole ve kterém bit leží a musíme určit kde bit leží v tomto prvku. Stejně jako pro indexaci pole (počáteční prvek s indexem nula je prvním prvkem pole) je i zde možné přijmout konvenci, že první bit má index nula nebo jedna. Zvolili jsme číslování bitů od nuly. Pro výpočet polohy bitu v prvku je výhodné použít operaci zbytek po celočíselném dělení (to je funkci modulo s operátorem %). Bit 33 tedy bude bitem s váhou jedna v daném prvku (existuje ovšem i bit s váhou nula, takže je to druhý bit od kraje prvku).
   Tímto jsme určili prvek v poli a pozici bitu v tomto prvku, který je nutné nastavit. K nastavení použijeme funkci OR. K určení který bit se nastaví použijeme proměnnou stejného typu jako je pole, kterou nastavíme na jedničku, kterou následně posuneme o úsek odpovídající vypočtenému počtu bitů.
   Pozn. V celém programu musíme tedy dodržet konvenci indexace poloh od nuly.
   Jelikož se určování pozice prvku v poli a bitu v prvku bude často opakovat, nabízí se vytvořit pro zjištění těchto hodnot funkci. Protože se však v podstatě jedná o výpočty jednoduché, bylo by vhodnější realizovat (funkčním) makrem.
   Ve funkci main pomocí funkce Nastav nastavte každý druhý bit v proměnné Prom0. Proměnnou vytiskněte.

6. Obdobně jako funkci Nastav vytvoříme funkce Nuluj ( pomocí bitové operace AND, kdy po nalezení pozice bitu jedničku bitově invertujeme, čímž vznikne proměnná, která má všede jedničky kromě určeného místa. Takže operace AND zachová všechny bity kromě vybraného, který vynuluje). Další funkcí bude Zmen, která změní hodnotu daného bitu z 1 na 0, nebo z 0 na 1 (pomocí bitové operace XOR), a funce Zjisti, která vrátí jedničku nebo nulu podle toho jakou hodnotu má daný bit.
   Ve funkci main pomocí funkce Nuluj vynulujte každý druhý bit v proměnné Prom1. Proměnnou vytiskněte.
   Ve funkci main pomocí funkce Zmen změňte všechny bity v proměnné Prom0. Proměnnou vytiskněte.
   Ve funkci main vytiskněte po jednom bitu pomocí funkce Zjisti proměnnou Prom0 od nejvyššího bitu.

7. Funkce z předchozích bodů realizujeme jako makra – NASTAV, NULUJ, ZMEN, ZJISTI. (Lze realizovat převodem jedna funkce jedno makro (celá funkce se ale pokud možno musí vlézt do jednoho příkazu), nebo pomocí hierarchie maker).

8. Funkčnost maker demonstrujte na stejných příkladech jako funkce.
   
   
   

   
   
   
   

Pozn.:

1. Jazyk C má přímo typ „bitové pole“. Způsob práce s ním a tedy i okruh využití je odlišný od námi realizovaného bitového pole pomocí pole celočíselného typu.

Hledání pročísel

Pro demonstraci práce s bitovým polem se používá algoritmus hledání prvočísel. Pro toto hledání prvočísel existuje metoda nazývaná Eratostenovo síto (postupů je několik, uvedený algoritmus je tedy jednou z variant).
Pozn. Lze pracovat i s polem charů, kdy v každém bude uložen „jeden bit“, tím ale dochází k mrhání pamětí. Tohle je příklad na procvičení bitů. Proto je myšlenka taková, že každý bit v poli reprezentuje jedno číslo – pokud je nastaven, znamená to, že číslo je prvočíslo. Vezmeme-li tedy pole dvou charů (tj. Dva byty), budou bity při zvolené indexaci například reprezentovat čísla :
15 14 13 12 11 10 9 8 / 7 6 5 4 3 2 1 0 a výsledné nastavení bitů pro prvočísla bude:
0 0 1 0 1 0 0 0 / 1 0 1 0 1 1 1 0.
Pro zjištění prvočísel do hodnoty 16 použijeme tedy pouze dva byty. Jedná se vlastně o reprezentaci množiny čísel, kdy přítomnost každého čísla je zaznamenána pomocí jediného bitu.

Poslední změna 2019-02-14