Zamiana liczby dziesiętnej na binarną

Dla rozgrzewki postanowiłem napisać prosty program zamieniający liczbę dziesiętną bez znaku na liczbę binarną.

Algorytm jest dosyć prosty:
1. Jeżeli liczba jest parzysta, wypisz zero. Jeżeli nieparzysta – jedynkę.
2. Podziel liczbę przez dwa i odrzuć część ułamkową z dzielenia.
3. Jeżeli wynik dzielenia jest równy zero, zamiana zakończona.
4. Jeżeli wynik dzielenia nie jest zerem i liczba jest nieparzysta, to wstaw jedynkę przed liczbą binarną już otrzymaną. Jeżeli iloraz jest parzysty, to poprzedź liczbę binarną zerem.
5. Idź do kroku 2. i powtórz.

Ponieżej kod:

#include 
#include 

char* program_name;

void print_usage(int ret_code) {
  printf("%s \n\n", program_name);
  printf("Converts a decimal number to binary and prints it out.\n");
  exit(ret_code);
}

int main(int argc, char** argv) {
  char str_num[32] = {0};
  unsigned int tmp_number = 0;
  unsigned int prev_number;
  int num_pos = 31;
  int i;
  int lp = 1;

  program_name = argv[0];

  if(argc <= 1) {
    printf("Provide a number to convert!\n\n");
    print_usage(-1);
  }

  tmp_number = atoi(argv[1]);
  prev_number = tmp_number;

  printf("The decimal number to convert to binary: %u\n", tmp_number);

  if(tmp_number % 2 == 0) {
    str_num[num_pos] = '0';
    printf("%d. %u. Is even: ", lp, tmp_number);
    for(i = num_pos; i < 32; ++i) {
      printf("%c", str_num[i]);
    }
    printf(" : %d\n", 32 - num_pos);
    --num_pos;
    lp++;
  } else {
    str_num[num_pos] = '1';
    printf("%d. %u. Is odd: ", lp, tmp_number);
    for(i = num_pos; i  1) {
    tmp_number /= 2;

    if(tmp_number % 2 == 0) {
      str_num[num_pos] = '0';
      printf("%d. %u / 2 = %d. Is even: ", lp, prev_number, tmp_number);
      for(i = num_pos; i < 32; ++i) {
        printf("%c", str_num[i]);
      }
      printf(" : %d\n", 32 - num_pos);
      lp++;
    } else {
      str_num[num_pos] = '1';
      printf("%d. %u / 2 = %d. Is odd: ", lp, prev_number, tmp_number);
      for(i = num_pos; i < 32; ++i) {
        printf("%c", str_num[i]);
      }
      printf(" : %d\n", 32 - num_pos);
      lp++;
    }

    prev_number = tmp_number;
    --num_pos;
  }

  return 0;
}

Wynik wykonania programu dla maksymalnej wartości liczby całkowitej, na maszynie 32-bitowej:

$ time ./dec2bin 4294967295
The decimal number to convert to binary: 4294967295
1. 4294967295. Is odd: 1 : 1
2. 4294967295 / 2 = 2147483647. Is odd: 11 : 2
3. 2147483647 / 2 = 1073741823. Is odd: 111 : 3
4. 1073741823 / 2 = 536870911. Is odd: 1111 : 4
5. 536870911 / 2 = 268435455. Is odd: 11111 : 5
6. 268435455 / 2 = 134217727. Is odd: 111111 : 6
7. 134217727 / 2 = 67108863. Is odd: 1111111 : 7
8. 67108863 / 2 = 33554431. Is odd: 11111111 : 8
9. 33554431 / 2 = 16777215. Is odd: 111111111 : 9
10. 16777215 / 2 = 8388607. Is odd: 1111111111 : 10
11. 8388607 / 2 = 4194303. Is odd: 11111111111 : 11
12. 4194303 / 2 = 2097151. Is odd: 111111111111 : 12
13. 2097151 / 2 = 1048575. Is odd: 1111111111111 : 13
14. 1048575 / 2 = 524287. Is odd: 11111111111111 : 14
15. 524287 / 2 = 262143. Is odd: 111111111111111 : 15
16. 262143 / 2 = 131071. Is odd: 1111111111111111 : 16
17. 131071 / 2 = 65535. Is odd: 11111111111111111 : 17
18. 65535 / 2 = 32767. Is odd: 111111111111111111 : 18
19. 32767 / 2 = 16383. Is odd: 1111111111111111111 : 19
20. 16383 / 2 = 8191. Is odd: 11111111111111111111 : 20
21. 8191 / 2 = 4095. Is odd: 111111111111111111111 : 21
22. 4095 / 2 = 2047. Is odd: 1111111111111111111111 : 22
23. 2047 / 2 = 1023. Is odd: 11111111111111111111111 : 23
24. 1023 / 2 = 511. Is odd: 111111111111111111111111 : 24
25. 511 / 2 = 255. Is odd: 1111111111111111111111111 : 25
26. 255 / 2 = 127. Is odd: 11111111111111111111111111 : 26
27. 127 / 2 = 63. Is odd: 111111111111111111111111111 : 27
28. 63 / 2 = 31. Is odd: 1111111111111111111111111111 : 28
29. 31 / 2 = 15. Is odd: 11111111111111111111111111111 : 29
30. 15 / 2 = 7. Is odd: 111111111111111111111111111111 : 30
31. 7 / 2 = 3. Is odd: 1111111111111111111111111111111 : 31
32. 3 / 2 = 1. Is odd: 11111111111111111111111111111111 : 32

real	0m0.002s
user	0m0.000s
sys	0m0.000s

Program wypisuje kolejne kroki działania, liczba na końcu każdego wiersza to liczba bitów. Na końcu jest wypisany czas działania programu, a nie samej zamiany. Zamiana pewnie trwa dużo krócej, wypisywanie na ekran zajmuje czas.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s