Po půl roce sucha (konečně) přináším další zajímavou programovací úlohu. Tentokrát se jedná o úlohu pro programátory v C++ a na své si přijdou především milovníci bitových manipulací :). A nebojte, nebude to žádná úloha stylu "vytvořte makro pro vzájemné prohození polovin předaného intu".
Máte následující neúplné definice dvou šablon:
#include <string> #include <cassert> using namespace std; template<typename T> T binaryStringToNumber(const string &binStr) { assert(binStr.size() == sizeof(T)); // ? } template<typename T> string numberToBinaryString(const T &num) { // ? }
Doplňte těla šablon tak, aby:
Způsob uložení bajtů v paměti (little/big endian) je dán architekturou. Upozorňuji, že dané řetězce musí obsahovat přesnou binární podobu daných čísel bajt po bajtu a naopak, tj. musí platit sizeof(T) == str.size()
, kde str
je převedený řetězec. Výsledný řetězec tedy nebude textově obsahovat pouze znaky '0' a '1'! Viz příklady v sekci testování.
T
bude vždy bezznaménkový integrální typ (unsigned char
, unsigned short int
, unsigned int
a unsigned long int
).static_cast
apod.).Abych vám ulehčil práci, tak zde přikládám ukázku, jak lze dané šablony otestovat. Ukázka není přenositelná a jsou v ní určité předpoklady (na velikost datových typů + architektura používá schéma little endian pro uložení bajtů čísel v paměti), takže si ji budete muset upravit podle své plaformy. Samotné definice šablon ale musí být přenositelné!
#include <climits> int main() { assert(CHAR_BIT == 8 && sizeof(short int) == 2 && sizeof(int) == 4 && sizeof(long int) == 8); // 1B assert(binaryStringToNumber<unsigned char>(string("\x00", 1)) == 0x00); assert(binaryStringToNumber<unsigned char>(string("\xB8", 1)) == 0xB8); assert(binaryStringToNumber<unsigned char>(string("\xFF", 1)) == 0xFF); assert(numberToBinaryString<unsigned char>(0x00) == string("\x00", 1)); assert(numberToBinaryString<unsigned char>(0xC4) == string("\xC4", 1)); assert(numberToBinaryString<unsigned char>(0xFF) == string("\xFF", 1)); // 2B assert(binaryStringToNumber<unsigned short int>(string("\x00\x00", 2)) == 0x00); assert(binaryStringToNumber<unsigned short int>(string("\x28\x51", 2)) == 0x5128); assert(binaryStringToNumber<unsigned short int>(string("\xFF\xFF", 2)) == 0xFFFF); assert(numberToBinaryString<unsigned short int>(0x00) == string("\x00\x00", 2)); assert(numberToBinaryString<unsigned short int>(0x2C4B) == string("\x4B\x2C", 2)); assert(numberToBinaryString<unsigned short int>(0xFFFF) == string("\xFF\xFF", 2)); // 4B assert(binaryStringToNumber<unsigned int>(string("\x28\x7D\xA1\xE8", 4)) == 0xE8A17D28); assert(numberToBinaryString<unsigned int>(0x6ABB4C32) == string("\x32\x4C\xBB\x6A", 4)); // 8B assert(binaryStringToNumber<unsigned long int>(string("\x28\x7D\xA1\xE8\xAA\x32\xC4\x99", 8)) == 0x99C432AAE8A17D28UL); assert(numberToBinaryString<unsigned long int>(0x3C2103895BF39D0F) == string("\x0F\x9D\xF3\x5B\x89\x03\x21\x3C", 8)); return 0; }
Uvedu celkem dvě řešení - první používá bitové manipulace, druhé na to jde "hrubou silou".
#include <limits> template<typename T> T binaryStringToNumber(const string &binStr) { assert(binStr.size() == sizeof(T)); T num = 0; num |= binStr[sizeof(T) - 1]; for (size_t i = 2; i <= sizeof(T); ++i) { num <<= CHAR_BIT; num |= static_cast<unsigned char>(binStr[sizeof(T) - i]); } return num; } template<typename T> string numberToBinaryString(const T &num) { string binStr(sizeof(T), '\0'); for (size_t i = 0; i < sizeof(T); ++i) { size_t shiftSize = i * CHAR_BIT; T byteMask = numeric_limits<unsigned char>::max(); binStr[i] = (num & (byteMask << shiftSize)) >> shiftSize; } return binStr; }
Transformace z řetězce na číslo probíhá postupným prováděním bitového součtu (OR) bajtů ze zdrojového řetězce a bajtů z čísla. Po každém provedení bitového součtu dojde k posunutí bitů doleva, aby se vytvořilo místo pro následující bitový součin. Takto dojde k přesné kopii bajt po bajtu. Všimněte si především korektního použití konstanty CHAR_BIT
, ve které je uloženo počet bitů v jednom bajtu (potenciálně přenositelnější než použití konstanty 8).
Transformace z čísla na řetězec probíhá tak, že se provede bitový posun bajtu obsahující samé jedničky o příslušný počet bajtů doleva, pak se provede logický součin (AND) s daným číslem (pro vymaskování dané části čísla) a k následnému posunu zpět. Jelikož používáme bezznaménkové typy, tak nás nemusí trápit to, zda operátor bitového posunu doprava zachovává znaménko nebo ne. Opět si povšimněte využití konstanty CHAR_BIT
a šablony numeric_limits
pro získání maximální možné hodnoty, která se vleze do jednoho bajtu.
template<typename T> T binaryStringToNumber(const string &binStr) { assert(binStr.size() == sizeof(T)); T num = 0; memcpy(&num, binStr.data(), sizeof(T)); return num; } template<typename T> string numberToBinaryString(const T &num) { char tmpBinStr[sizeof(T)] = {}; memcpy(tmpBinStr, &num, sizeof(T)); return string(tmpBinStr, sizeof(T)); }
Druhé řešení využívá (s)prostou kopii bajt po bajtu mezi řetězcem a číslem. Možná vás napadlo, že by šlo využít unie (uložit jednu složku a číst z jiné) nebo reinterpret_cast
, ale ani jedna z těchto konstrukcí není přenositelná. Použitím memcpy()
mě nenapadá žádný důvod, proč by tato implementace neměla být přenositelná.
Komentáře
Zveřejněno moje řešení #6
Zveřejnil jsem moje řešení šestého úkolu. Komentáře jsou, jako vždy, vítány.
Přidat komentář