STL - 16 bitset 활용

[STL-16] bitset 활용

|

STL을 배우자

2009.01.07 12:16

라온(raon_pgm)

카페매니저

http://cafe.naver.com/cppstl/670

오랜만이죠.. ^^

 

이번에는 bitset 을 다뤄보고자 합니다.

우선 이름에서도 알 수 있듯이 bitset은 bool type을 담고 있는 container입니다.

그런데 generic container와는 다른 특수한 container 입니다.

 

bitset에 대한 상세한 내용은 아래 링크를 참고하시기 바라며,

오늘은 간단한 활용과 주의 해야 할 부분에 대해서 다뤄보고자 합니다.

 

http://idb.snu.ac.kr/~sjjung/stl/bit_2576.htm

http://www.dinkumware.com/manuals/?manual=compleat&page=bitset.html

http://www.cppreference.com/wiki/stl/bitset/start

 

간단하게 선언하고 출력을 하는 예입니다.

 

1 #include <iostream>  2 #include <limits>  3 #include <bitset>  4 #include <string>  5   6 using namespace std;  7   8 int main()  9 { 10     bitset< numeric_limits< unsigned int >::digits > bset(0x01020304); 11  12     cout << bset << endl; 13     cout << hex << showbase << bset.to_ulong() << endl; 14     cout << bset.to_string<char,char_traits<char>,allocator<char> >().substr(0,8) << endl; 15  16     return EXIT_SUCCESS; 17 }

---------- run  ----------
00000001000000100000001100000100
0x1020304
00000001

출력 완료 (0초 경과)

 

Line 10에서 bitset을 선언하는데 사이즈를 unsigned int의 digits 개수인 32로 됩니다.

bitset은 생성자가 explicit로 되어 있기 때문에 operator=은 지원하지 않습니다.

Line 13은 출력은 unsigned long 형식으로 하는데 bitset size가 unsigned long type의

size보다 크면 exception 처리 됩니다.

Line 14에서 string 형으로 처리하는데 to_string()을 사용할 때 string에 대한 type을 모두 지정해야 합니다.

주의 할 점이 하나 있는데, string의 경우 operator[] 의 접근 방식과 bitset의 operator[] 가 다릅니다.

개념적으로 string str = "1000" 이라고 할 때 1은  str[0] 이지만, bitset<4> bit("1000") 에서는 1은 bit[3] 입니다.

말그대로 배열과 같은 순서가 아니라 bit order 라고 할 수 있습니다.

 

bool type은 check box나 다중 flag로 많이 쓰는데, 아래 예는 enum으로 선언해서 flag로 사용할 경우 입니다.

1 #include <bitset>  2   3 using namespace std;  4   5 int main()  6 {  7     enum enumFlagSet { eA = 0, eB, eC, eD, eE, eFlagSize };  8   9     bitset< eFlagSize > bset; 10  11     ... 12  13     return EXIT_SUCCESS; 14 }

 

enumeration 형태로 bitset size를 따로 관리할 필요없이 마지막 eFlagSize로 만들어 줍니다.

bset[eA] 형태로 하면,, 그 다음은 감이 잡히죠..

 

마지막으로 예전에, 전공 했다는 넘이 floating point type 구조도 몰라 이해 시켜 주려고 만들었던 코드입니다.

floating point type 값을 bit으로 만들고 각 section 별로 나눠 다시 계산하는 형태입니다.

1 /*-----------------------------------------------------------------------------------------   2  * finename    : dpa.cpp   3  * eng'r name  : Jeong-il Ahn(raon_pgm@naver.com)   4  * date        : 1998 . 2. 2.   5  * title       : precision analysis   6  * purpose     : The precision of floating point format analysis   7  * description : - wikipedia.org -   8                  In computing, double precision is a computer numbering format that   9                  occupies two storage locations in computer memory at address and  10                  address+1.  11                  A double precision number, sometimes simply called a double, may be  12                  defined to be an integer, fixed point, or floating point.  13   14                  Modern computers with 32-bit stores (single precision) provide  15                  64-bit double precision.  16                  Double precision floating point is an IEEE 754 standard for  17                  encoding floating point numbers that uses 8 bytes.  18  * reference   : http://en.wikipedia.org/wiki/Double_precision  19  * environment : system   : intel cpu 32bit windows XP  20                  compiler : g++ -3.4.5 (mingw32) || gnu g++  21  * compute formula   22    formula is to compute double precision : -1^sign * 2^(exponent-exponent bias) * 1.mantissa  23   24     @ single precision  25   26     sign  27     |exponent (8 bits)  28     ||      |fraction (23 bits)  29     ||      ||                     |  30     *########&&&&&&&&&&&&&&&&&&&&&&&  31     |       |                      |  32     31      23                     0  33   34   35     @ double precision  36   37     sign  38     |exponent (11 bits)  39     ||         |fraction (52 bits)  40     ||         ||                                                  |  41     *###########&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&  42     |          |                                                   |  43     63         52                                                  0  44   45  *----------------------------------------------------------------------------------------*/  46   47 #include <iostream>  48 #include <iomanip>  49 #include <ios>  50 #include <stdexcept>  51 #include <string>  52 #include <bitset>  53 #include <cmath>  54   55 using namespace std;  56   57 //! global variables  58 // size of double type = 8byte  59 const size_t sizeVar = sizeof(double);  60 // bit memory size  61 const size_t sizeBitset = sizeVar * 8;  62 const size_t sizeExponent = 11;  63 const size_t sizeMantissa = 52;  64 // exponent bias = 1023  65 const unsigned long ulExponentBias = 1023;  66   67 // get mantissa from bitset<sizeBitset>  68 double fnMantissa( const bitset<sizeBitset> &b );  69 // get exponent from bitset<sizeBitset>  70 double fnExponent( const bitset<sizeBitset> &b );  71   72 void usage()  73 {  74     cout << " usage : dpa NUM" << endl;  75     cout << "\n        NUM = floating point number" << endl;  76     exit(EXIT_FAILURE);  77 }  78   79 int main( int argc, char **argv )  80 {  81     if( argc != 2 ){  82         usage();  83     }  84   85     try {  86         //argument is double type  87         double dblNumber = atof(argv[1]);  88   89         double dblSign;         // sign     : 1bit  90         double dblExponent;     // exponent : 2^(exponent-exponent bias)  91         double dblSignificand;  // mantissa : 1.mantissa   92         double dblResult;       // double precision : -1^sign * 2^(exponent-exponent bias) * 1.mantissa  93   94         dblSign = dblExponent = dblSignificand = dblResult = 0.;  95   96         bitset< sizeBitset > bit;  //bitset container  97   98         // floating point type의 경우 if문으로 == , != 를 비교하는 것은 오류가 생길 수 있지만,  99         // Input argument 값에 대한 다른 연산이 없으며, 100         // 입력 값이 잘못되었을 경우 atof는 0. 을 return 하므로 확인하고 처리한다. 101         if ( dblNumber != 0. ) { 102             //double type을 각 1byte씩 잘라 char type으로 casting하고 bitset에 입력 103             for( int i = sizeVar-1 ; i >= 0 ; --i ){ 104                 bit |= bitset<sizeBitset>( ( reinterpret_cast< unsigned char* >(&dblNumber) )[i] ); 105                 if( i != 0 ){ 106                     bit <<= 8; 107                 } 108             } 109  110             dblSign         = bit[sizeBitset-1] ? -1. : 1.; 111             dblExponent     = fnExponent( bit ); 112             dblSignificand  = 1.+fnMantissa( bit ); 113             dblResult       = dblSign * dblExponent * dblSignificand; 114         } 115  116         // bitset을 구분별로 출력하기 위해 string에 대입 117         string strBitSet = bit.to_string<char,char_traits<char>,allocator<char> >(); 118  119         // print to standard output 120         // stream precision set 121         streamsize prec = cout.precision(); 122         cout << endl 123              // single precision 의 경우 신뢰할 수 있는 수준은 소수점 이하 9자리 정도이고, 124              // double precision 의 경우는 소수점 이하 15자리 정도이다. 125              // 오차를 확인하고자 할 경우 precision set을 변경하면 된다. 126              << setprecision(15) 127              << "Input value : " << dec << dblNumber << endl << endl 128              // bits : 10000 이라면 string의 경우 1의 position은 [0] 이지만 129              // bitset의 경우 1의 position은 bit order기준으로 [4] 가 된다. 130              // access operator 사용이 반대로 되므로 주의가 필요하다. 131              << "Double precision bit data " << endl 132              << "sign        : " << strBitSet[0] << endl 133              << "exponent    : " << strBitSet.substr(1,sizeExponent) << endl 134              << "significand : " << strBitSet.substr(sizeExponent+1) << endl << endl 135              << "Compute bit data" << endl 136              << "double precision : -1^sign * 2^(exponent-exponent bias) * 1.mantissa" << endl 137              << "compute double   : "   << dblSign << " * " << dblExponent << " * " << dblSignificand << endl 138              << "                 = "   << dblResult << endl 139              << setprecision(prec); 140     } 141     catch ( const exception& error ) { 142         cerr << error.what() << endl; 143         exit ( EXIT_FAILURE ); 144     } 145     catch (...) { 146         cerr << "Unknown error caught, Process has been halted." << endl; 147         exit ( EXIT_FAILURE ); 148     } 149  150     return ( EXIT_SUCCESS ); 151 } 152  153 double fnExponent( const bitset<sizeBitset> &b ) 154 { 155     string str = b.to_string< char,char_traits<char>,allocator<char> >(); 156     long lValue = bitset<sizeExponent>(str.substr(1,sizeExponent)).to_ulong() - ulExponentBias; 157  158     return ( 159               lValue < 0 160             ? 1. / pow( 2, static_cast<double>( abs(lValue) ) )   161             : pow( 2, static_cast<double>( lValue ) ) 162            ); 163 } 164  165 double fnMantissa( const bitset<sizeBitset> &b ) 166 { 167     double dblMantissa = 0; 168     __int64 n64 = 2; 169     for( int sz = sizeMantissa-1 ; sz >= 0 ; --sz ){ 170         dblMantissa += ( b[sz] * ( 1. / n64 ) ); 171         n64 <<= 1; 172     } 173  174     return dblMantissa; 175 }

---------- run  ----------

Input value : -1.05

Double precision bit data 
sign        : 1
exponent    : 01111111111
significand : 0000110011001100110011001100110011001100110011001101

Compute bit data
double precision : -1^sign * 2^(exponent-exponent bias) * 1.mantissa
compute double   : -1 * 1 * 1.05
                 = -1.05

출력 완료 (0초 경과)

 

주석 내용 읽어 보시면 프로그램 내용은 금방 이해가 되리라 보구요, bitset을 사용하는 형태를 참고하시기 바랍니다.

 

굳이 기본형에 bit operator를 사용하여 처리하거나 bit field나 vector<bool> 을 사용하지 않고

bitset을 사용해서 얻는 이점이 무엇일까라는 의문이 생기는 분도 있으리라 생각합니다. 답은 없습니다만,

기본형은 자료형에 따른 사이즈 제한이 있고, bit field는 선언이나 접근이 용이하지 않으며,

vector<bool>의 경우 얘기가 깁니다만, 템플릿 특화된 형태로 standard container가 아닙니다.

자세한 얘기는 effective stl에 scott 아저씨가 잘 얘기해 주고 있습니다.

proxy pattern 으로 구현된 vector<bool>은 이런 저런 문제가 있다는 것만 기억해 두시기 바랍니다.

그러니 vector<bool>을 사용할 것이라면 bitset을 사용하세요.