Programowanie i algorytmy

Dziesiętna na binarną

Zad. 1. Napisz funkcję, która wyświetli postać binarną podanej liczby całkowitej zapisanej w systemie dziesiętnym.

Wejście

Liczba całkowita typu int.

Wyjście

Ciąg cyfr binarnych reprezentującą podaną liczbę całkowitą na wejściu.

 

Rozwiązanie.

Sposób tradycyjny

Dla przykładu zamieńmy liczbę 20 na liczbę binarną.

W jednym kroku algorytmu wykonujemy dwie czynności:

  • wyznaczamy resztę z dzielenia przez 2 konwertowanej liczby
  • konwertowaną liczbę dzielimy przez 2 (dzielenie całkowite)

Daną czynność wykonujemy tak długo, jak długo liczba dziesiętna jest większa od 0.

Przykład zamiany liczby 20 jest przedstawiony poniżej:

Następnym krokiem jest spisanie reszt (z dołu do góry), czyli

20 = (10100)2.

Do rozwiązania problemu posłużymy się tablicą, a następnie wyświetlimy jej zawartość w odwrotnej kolejności. Załóżmy, że typ int składa się z 4 bajtów, czyli maksymalnie możemy uzyskać 31 bitów (jeden bit przeznaczony jest na znak liczby).

#include <cstdlib>
#include <iostream>
using namespace std;
 
void dec_to_bin(int liczba)
{
  int i=0,tab[31];
 
  while(liczba) //dopóki liczba będzie różna od zera
  {
    tab[i++]=liczba%2;
    liczba/=2;
  }
 
  for(int j=i-1;j>=0;j--)
    cout<<tab[j];
}
 
int main()
{
  int liczba;
 
  cout<<"Podaj liczbę: ";
  cin>>liczba;
 
  cout<<liczba<<" po zamianie na postać binarną: ";
  dec_to_bin(liczba);
  cout<<endl;
 
  system("pause");
  return 0;
}

 

Sposób drugi - z wykorzystaniem operatorów bitowych

Aby otrzymać ostatni bit dane liczby wystarczy wykonać działanie:

{tex}liczba\ \&\ 1{/tex}

Jeśli ostatni bit ma wartość 1, wynik działania 1 & 1 = 1, gdy ostatnim bitem jest 0, wynik działania 0 & 1 = 0, a więc poprawnie wyłuskujemy ostatni bit danej liczby.

Koncepcja wyznaczenia bitów danej liczby jest następująca:

dla przykładu posłużmy się liczbą 20.

20 = (10100)2

Przesuwamy bity liczby 20 o 4 miejsca w prawo i wykonujemy działanie & 1:

bit = (liczba >> 4) & 1

Aby otrzymać bit następny, przesuwamy liczbę o 3 bity i działamy & 1:

bit = (liczba >> 4) & 1

Czynność tą powtarzamy do momentu uzyskania wszystkich bitów (i=0).

 

#include <cstdlib>
#include <iostream>
using namespace std;
 
void dec_to_bin(int liczba)
{
  int i=31;
  bool ok=false;
  while(i--)
  {
    //warunek, który pozwoli ominąć początkowe zera
    if(liczba>>i&1&!ok) 
      ok=true;
 
    if(ok)
      cout<<((liczba>>i)&1);
 
  }
}
 
int main()
{
  int liczba;
  cout<<"Podaj liczbę: ";
  cin>>liczba;
 
  cout<<liczba<<" po zamianie na postać binarną: ";
  dec_to_bin(liczba);
  cout<<endl;
 
  system("pause");
  return 0;
}