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)

Funkčnost demonstrujte na krátkém programu (druhý zdrojový text s main). Například napište funkci, která „otočí proměnnou“ - tj. první bit bude vyměněn s posledním, předposlední s druhým …
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 celočíselný, nebo reálný? Bude to typ znaménkový, nebo bezznaménkový?
   Zvolený typ je _______________ (jakýkoli typ splňující podmínky dané odpovědí na dvě předchozí otázky. Pro delší pole můžeme použít větší/delší typy, pro menší pole kratší typy).

2. Jelikož počet bitů v daném typu je v jazyce C závislý na platformě a procesoru, nelze pro počet bytů (a teoreticky ani bitů) použít hodnoty z prostředí, kde právě pracujeme.
   Pro zjištění počtu bytů použijeme klíčové slovo jazyka _____________________.
   Bytů_v_typu = ____________________.
   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.
   Bitů_v_typu = Bytů_v_typu * CHAR_BIT

3. Určíme délku pole, které budeme používat, na základě požadovaného počtu bitů v poli. Později k této činnosti použijeme dynamickou alokaci pole, nyní délku pole určíme „ručně“.
   Pro snadnější představu (kontrolu výpočtů) předpokládejme, že typ má jeden byte.
   Kolik prvků zvoleného typu (jak velké pole daného typu musíme nadefinovat) je potřeba pro realizaci pole bitů o délce N?
   Pocet_bitů = N
   Délka_pole = ____________________________ (použijte pro výpočet Pocet_bitů a Bitů_v_typu)
   Zkontrolujte, zda vám vypočet dává správné výsleky pro jednobytový typ a N = {1,7,8,9,11,14,15,16,17}. Předpokládejte, že bity v poli číslujeme od nuly. Výsledky pro dané N jsou: Délka_pole = {1,1,2,2,2,2,2,3,3}
   Určete délku pole pro datový typ long pokud potřebujeme 333 bitů a toto pole nadefinujte pro další práci.
   Nastudujte obsah knihovny překladače „float.h“, „limits.h“, „ctype.h“, zopakujte si operátor sizeof.

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. Pole nemusíme plnit po bitech, ale můžeme ho naplnit pomocí hodnoty 0 a nebo maximální hodnoty datového typu pole. Musíme ale naplnit všechny prvky v poli (ale v délce, která odpovídá danému typu ne počtu bitů, které jsou v hlavičce funkce). Jelikož se délka (počet bitů, bytů) daného typu může měnit, používáme pro získání proměnné daného typu „plné jedniček“ operátor bitové negace ~, který použijeme na nulu. Nezapomeňte, že standardně psaná „0“ (nula) je typu int; „0.“ (nula s tečkou) je typu double; „0l“ (nula s „el“) je typu long.

5. Funkce pro nastavení daného bitu Nastav. Funkce nastav bude mít tři parametry: pole, jeho délku v bitech a číslo bitu, který se má nastavit na jedničku.
   Nejdříve provedeme kontrolu, zda je požadovaný bit uvnitř pole (je nezáporný a menší než délka pole).
   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í ve třetím prvku pole (v prvním (nultém) jsou bity 0-15, ve druhém (prvním) jsou bity 16-31 a bit 33 je tedy až ve třetím prvku pole (pro číslování v C od nuly je to tedy prvek s indexem 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. Jak je výše patrno, zde byla zvoleno číslování od jedničky. Pro práci v počítači je ovšem přirozenější indexace od nuly (což povede k tomu, že budeme odečítat jedničku). Pro tento výpočet je výhodné použít zbytek po celočíselném dělení (to je funkci modulo s operátorem %). Bit 33 tedy bude prvním bitem v daném 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ů.
   
   
   

   Pole char indexy	0	1	2
   Číslování bitů v poli (naše konvence) Toto rozvržení bitů usnadní práci.	7...........0	15...........8	23...........16
   Čísla bitů v poli char (fyzicky podle váhy)	7...........0	7...........0	7...........0
   Čísla bitů v poli char – jiná konvence	8...........1	8...........1	8...........1
   Čísla bitů v poli char – jiná možnost	1...........8	1...........8	1...........8

   Jak očíslujeme bity uvnitř pole není důležité. Důležité je pouze to, aby všechny funkce pracující s polem po zadání stejného čísla (pozice bitu) pracovaly se stejným bitem.
   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.

6. Obdobně vytvoříme funkce Nuluj ( pomocí bitové operace AND, kdy po posunu jedničku bitově invertujeme, čímž vznikne nula, která po AND vynuluje daný bit a zbytek ponechá), Zmen (pomocí bitové operace XOR), a Zjisti, která vrátí jedničku nebo nulu podle toho jakou hodnotu má daný bit.

7. Funkce z bodů 2) 3) a 4) realizujeme jako makra. (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).
   
   
   

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.

2. Pokročilejší programátoři by pro realizaci pole nepoužili statické pole, ale pole dynamicky alokované, kdy je možné pružně reagovat na změny délky pole. (Pokud toto později zkusíte, nezapomeňte, že každá žádost o přidělení paměti (alokace) musí mít i svůj protiklad – navrácení paměti zpět systému před ukončením programu/proměnné).

3. Pokročilejší programátoři by pro realizaci bitového pole použili rozšířený datový typ struktura, takže by v jedné proměnné byly umístěny všechny informace od daném poli (vlastní pole, počet bitů, počet bytů, chybové stavy …)

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).

Poslední změna 2015-03-11