Friday, December 9, 2016

Թվի երկուական ներկայացման ևս մի մեթոդի մասին

Մի անգամ արդեն ես առիթ եմ ունեցել գրելու ամբողջ թիվը տասական ներկայացումից երկուական ներկայացման ձևափոխելու մասին։ ՀայIT.orgԹվի ձևափոխումը տասականից երկուական տեսքի հոդվածում գրել եմ ձևափոխության ռեկուրսիվ եղանակի մասին, որտեղ օգտագործել եմ ծրագրավորման լեզվում տողերի կոնկատենացիայի հնարավորությունը։

Հիմա ուզում եմ խոսել այն մասին, թե ինչպես կառուցել թվի երկուական ներկայացումը, երբ լեզվում տողերի կցման հնարավորություն չկա, և արդյունքը պետք է գրել սիմվոլների բուֆերի մեջ։ Ընդունված մեթոդն այն է, որ տրված տասական թիվը, քանի դեռ այն զրո չի դարձել, հաջորդաբար բաժանվում է `2`֊ի, և բաժանումից ստացված մնացորդները գրառվում են հակառակ կարգով։ Այստեղ խնդիրն այն է, որ կամ պետք է հենց սկզբից մնացորդները բուֆերի մեջ գրառել հակառակ հաջորդականությամբ՝ նախապես իմանալով երկուական տեսքի զբաղեցրած նիշերի քանակը, կամ մնացորդները գրառել դրանց ստացվելու ուղիղ հաջորդականությամբ և վերջում վերադասավորել հակառակ կարգով։ Թվի երկուական տեսքի զբաղեցրած նիշերի քանակը կարելի է ստանալ լոգարիթմի օգնությամբ․ \(length=\lceil\log_2{n}\rceil\)
// տարբերակ I
void bin_a( int num, char* res )
{
  size_t length = log(num)/log(2);
  while( num ) {
    res[length--] = "01"[num & 0x01];
    num >>= 1;
  }
}

// տարբերակ II
void bin_b( int num, char* res )
{
  char* p = res;
  while( num ) {
    *p++ = "01"[num & 0x01];
    num >>= 1;
  }

  while( p > res ) {
    char t = *(--p);
    *p = *res;
    *res = t;
    ++res;
  }
}
Թե զբաղեցնելիք նիշերի քանակը, և թե մնացորդները հակառակ գրելուց հետո դրանք շրջելը ես համարում եմ ավելորդ աշխատանք։ Ստորև ցուցադրում եմ մի եղանակ, որում թվի տասական տեսքից երկուական տեսքի կառուցումը կատարվում է առանց վերը նշված «ավելորդ» (կամ ոչ ցանկալի) գործողությունների։

Եվ այսպես, int bin( int num, char* res ) ֆունկցիան արգումենտում ստանում է ձևափոխվելիք թիվը և արդյունքը գրառելու տեղը (նիշերի բուֆեր), իսկ վերադարձնում է երկուական ներկայացման նիշերի քանակը։ Սա ինտերֆեյսը։ Իսկ իրականացումը ռեկուրսիվ է․ բազա) եթե num֊ը փոքր է 2֊ից, ապա բուֆերի սկզբում գրել '0' կամ '1' համապատասխան նիշը, քայլ) եթե num֊ը մեծ է կամ հավասար երկուսի, ապա bin() ֆունկցիան ռեկուրսիվ կանչել num / 2 քանորդով ու ստանալ len թիվը, որը բուֆերում այդ քանորդի զբաղեցրած նիշերի քանակն է, ապա բուֆերի len + 1 դիրքում գրել num % 2 մնացորդին համապատասխան '0' կամ '1' նիշը։ Ռեկուրսիայի բազային ճյուղում որպես արդյունք ֆունկցիան պետք է վերադարձնի 1, քայլի ճյուղում՝ len + 1։

Ահա իրականացումը C լեզվով․
int bin( int num, char* res )
{
  if( num < 2 ) {
    *res = "01"[num];
    return 1;
  }

  int len = bin(num >> 1, res);
  *(res + len) = "01"[num & 0x01];
  return 1 + len;
}
Նկարագրված երեք ֆունկցիաների արդյունքները համեմատելու համար օգտագործում եմ test_bin() ֆունկցիան․
bool test_bin( int num )
{
  char res_a[32] = { 0 };
  bin_a(num, res_a);

  char res_b[32] = { 0 };
  bin_b(num, res_b);

  char res[32] = { 0 };
  bin(num, res);

  bool pass = 0 == strcmp(res, res_a);
  pass = pass && (0 == strcmp(res, res_b));
  
  if( !pass )
    printf("| num = %d\tres = %s\tres_a = %s\tres_b = %s\n",
           num, res, res_a, res_b);
  else
    printf("| num = %d\tres= %s\n", num, res);

  return pass;
}

1 comment: