Algorytm konwersji liczby z systemu binarnego na szesnastkowy

Przeanalizujmy zadanie polegające na konwersji liczb z systemu dwójkowego na szesnastkowy i zaimplementujmy realizujący je algorytm w języku Java.

Przykład 1

Naszym zadaniem jest przekonwertowanie liczby binarnej 10010101 na system szesnastkowy.

${10010101}_{\mathrm{(2)}}={\left(\right)}_{\mathrm{(16)}}$

Gdybyśmy mieli do dyspozycji kartkę i długopis, najpierw przeprowadzilibyśmy konwersję z systemu binarnego na dziesiętny, a następnie na notację szesnastkową. Wyglądałoby to następująco:

${10010101}_{\mathrm{(2)}}=1\cdot 2^7+1\cdot 2^4+1\cdot 2^2+1\cdot 2^0=$

$=128+16+4+1={149}_{\mathrm{(10)}}$

Aby przekonwertować liczbę z systemu dwójkowego do systemu dziesiętnego, obliczamy sumę iloczynów wszystkich cyfr danej liczby i odpowiadających im wag (czyli w przypadku systemu binarnego kolejnych potęg liczby 2). Możemy w tym celu zastosować również  schemat HorneraPZ4e2fNo0schemat Hornera.

Oto wynik końcowy pierwszej konwersji:

${10010101}_{\mathrm{(2)}}={149}_{\mathrm{(10)}}$

Otrzymany wynik konwertujemy następnie do systemu docelowego, czyli szesnastkowego.

R1Ql17oFZDo7s

Ilustracja przedstawia konwersje liczb dziesiętnych na hexadecymalne. Po lewej stronie prostej znajduje się liczba dziesiętna 149, po prawej reszta z dzielenia przez 16 czyli 5.
Poniżej 149 znajduje się liczba ile razy 16 zmieściło się w liczbie 149 czyli 9. Reszta z 9 przez 16 do 9.

Przeanalizujmy listę kroków algorytmu (liczbaDec oznacza liczbę, którą chcemy zamienić na system szesnastkowy):

1. Weź liczbaDec i podziel ją całkowicie przez podstawę systemu docelowego, czyli 16. W pokazanym wyżej przykładzie bierzemy liczbę 149 i dzielimy ją całkowicie przez 16.

2. Zapisz wynik reszty z dzielenia całkowitego z kroku 1. Reszta z dzielenia całkowitego 149 przez 16 to 5.

3. Zapisz wynik dzielenia całkowitego z kroku 1. do zmiennej liczbaDec. Wynik dzielenia całkowitego 149 przez 16 to 9.

4. Powtarzaj kroki 1‑3, aż do osiągnięcia przez liczbaDec wartości 0. Kolejne dzielenie całkowite, które zostanie wykonane, to 9 przez 16, reszta z tego dzielenia to 9, a wynik dzielenia całkowitego to 0, co kończy powtarzanie dzielenia.

5. Wynikiem jest liczba szesnastkowa, składająca się z reszt z dzielenia zapisanych od końca. W naszym przykładzie jest to liczba 95.

Oto wynik zadania:

${10010101}_{\mathrm{(2)}}={149}_{\mathrm{(10)}}={95}_{\mathrm{(16)}}$

Realizacja algorytmu w języku Java

Przejdźmy do implementacji przedstawionego algorytmu w języku Java. Program będzie wykonywał następujące operacje:

• pobranie liczby binarnej z klawiatury,

• przekształcenie liczby binarnej na dziesiętną – do tego celu użyjemy wbudowanej funkcji parseInt(),

• przekształcenie liczby dziesiętnej na szesnastkową za pomocą funkcji dec2Hex(), którą napiszemy,

• wypisanie wyniku.

Zacznijmy od głównej funkcji programu:

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String liczbaBin = sc.next();
		if (liczbaBin.length() < 32) {
			int liczbaDec = Integer.parseInt(liczbaBin, 2);
			System.out.println(dec2Hex(liczbaDec));
		} else {
			System.out.println("Podaj liczbę binarną, która zawiera mniej niż 32 bity.");
		}
    }

Konwertowaną liczbę binarną pobieramy z klawiatury i zapisujemy w zmiennej liczbaBin. Zanim użyjemy funkcji parseInt() sprawdzamy, czy podana liczba bitów jest mniejsza od 32, ponieważ wspomniana funkcja ma pewne ograniczenia.

Funkcja ta przyjmuje dwa argumenty: liczbę w postaci ciągu znaków oraz podstawę systemu, w którym zapisana jest liczba. Podana liczba musi zawierać tylko cyfry sytemu podanego jako podstawa. Ponieważ zakres wartości typu Integer to <-2Indeks górny 31³¹, 2Indeks górny 31³¹ - 1>, największa liczba binarna, która zostanie poprawnie zamieniona, może składać się z co najwyżej 31 bitów o wartości 1.

W programie używamy więc instrukcji warunkowej, która sprawdza podaną liczbę bitów. Jeżeli jest ich mniej niż 32, liczbę binarną zamieniamy na dziesiętną przy użyciu funkcji parseInt, następnie wywołujemy funkcję Dec2Hex() oraz wypisujemy zwrócony rezultat konwersji. W przeciwnym wypadku wypisujemy stosowny komunikat i kończymy program.

Następny krok to utworzenie funkcji dec2Hex(), która przekształci podaną liczbę dziesiętną na szesnastkową.

public static String dec2Hex(int liczbaDec) {
    if(liczbaDec == 0) {
		return "0";
	}
    String liczbaHex = "";
	int reszta = 0;
    
	while (liczbaDec > 0) {
		if (liczbaDec % 16 <= 9) {
			reszta = liczbaDec % 16;
			liczbaHex = reszta + liczbaHex;
		} else {
			reszta = liczbaDec % 16 - 10 + 'A';
			liczbaHex = (char)reszta + liczbaHex;
		}

		liczbaDec = liczbaDec / 16;
	}

	return liczbaHex;
}

Funkcja zwraca ciąg znaków typu string. Konwersji dokonujemy poprzez dopisywanie („doklejanie”) do zmiennej liczbaHex kolejnych reszt z dzielenia przez 16.

Opis działania funkcji

W linii 2 sprawdzamy, czy konwertowana liczba jest równa 0, jeżeli tak, możemy od razu zwrócić 0 i zakończyć działanie funkcji (linia 3).

W przeciwnym wypadku deklarujemy zmienne:

• String liczbaHex = ""  – w której zapisany jest wynik końcowy konwersji (linia 5),

• int reszta = 0 – która przechowuje reszty z dzielenia przez 16 (linia 6).

Kolejny krok to wywołanie w linii 8. pętli while, która wykonuje instrukcje dopóty, dopóki liczba_dec jest większa od 0.

W linii 9. sprawdzamy, czy reszta z dzielenia przez 16 zawiera się w przedziale <0, 9>. Jeżeli warunek jest spełniony, w linii 10. zapisujemy wynik operacji liczba_dec % 16 do zmiennej reszta, po czym w linii 11. dopisujemy („doklejamy”) go do liczbaHex.

W przeciwnym wypadku w linii 13 do zmiennej reszta wpisujemy wynik operacji liczba_dec % 16 - 10 + A. Odejmując 10 i dodając A, spowodujemy, że w zmiennej reszta będą mogły się znajdować jedynie kody ASCII znaków od A do F.

Następnie w linii 14. wykonujemy rzutowanie zmiennej reszta, która jest liczbą całkowitą, na typ char. W wyniku tej operacji liczba zapisana w zmiennej reszta zmienia się w odpowiadający jej znak z tablicy ASCII. Następnie zmienną reszta doklejamy do liczbaHex.

Zgodnie z algorytmem w 17 linii funkcji wykonujemy dzielenie całkowite zmiennej liczbaDec przez podstawę systemu.

liczbaDec = liczbaDec / 16;

Na końcu w linii 20. zwracamy wynik – jest on zapisany w zmiennej liczbaHex.

Poniżej kod całego programu zawierający omówioną funkcję:

import java.util.Scanner;

public class binary2hexadecimal {

	public static String dec2Hex(int liczbaDec) {
		if (liczbaDec == 0) {
			return "0";
		}
		String liczbaHex = "";
		int reszta = 0;

		while (liczbaDec > 0) {
			if (liczbaDec % 16 <= 9) {
				reszta = liczbaDec % 16;
				liczbaHex = reszta + liczbaHex;
			} else {
				reszta = liczbaDec % 16 - 10 + 'A';
				liczbaHex = (char) reszta + liczbaHex;
			}

			liczbaDec = liczbaDec / 16;
		}

		return liczbaHex;
	}


	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String liczbaBin = sc.next();
		if (liczbaBin.length() < 32) {
			int liczbaDec = Integer.parseInt(liczbaBin, 2);
			System.out.println(dec2Hex(liczbaDec));
		} else {
			System.out.println("Podaj liczbę binarną, która zawiera mniej niż 32 bity.");
		}
	}
}

W przedstawionym programie wykorzystaliśmy gotową wbudowaną funkcję parseInt(), która może posłużyć do zamiany liczby binarnej zawierającej nie więcej niż 31 bitów na liczbę dziesiętną. W filmie zamieszczonym w sekcji „Prezentacja multimedialna” zaprezentowane jest rozwiązanie oparte na schemacie Hornera pozbawione omówionych ograniczeń funkcji parseInt().

Słownik