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 <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;

	return 0;
}

Sposób drugi - z wykorzystaniem operatorów bitowych

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

$$liczba\ \&\ 1$$

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 <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;

	return 0;
}