Jak liczby całkowite są wewnętrznie reprezentowane na poziomie bitów w Javie?

84

Próbuję zrozumieć, w jaki sposób Java przechowuje wewnętrznie liczby całkowite. Wiem, że wszystkie prymitywne liczby całkowite java są podpisane (z wyjątkiem krótkich?). Oznacza to jeden bit mniej dostępny w bajcie dla liczby.

Moje pytanie brzmi: czy wszystkie liczby całkowite (dodatnie i ujemne) są przechowywane jako uzupełnienie do dwóch, czy są tylko liczbami ujemnymi w uzupełnieniu do dwóch?

Widzę, że specyfikacja mówi x bit two's complement number. Ale często się mylę.

Na przykład:

  int x = 15; // Stored as binary as is?  00000000 00000000 00000000 00001111?
  int y = -22; // Stored as two complemented value? 11111111 11111111 11111111 11101010

Edytować

Żeby było jasne, x = 15

   In binary as is: `00000000 00000000 00000000 00001111'
  Two's complement: `11111111 11111111 11111111 11110001`

Więc jeśli twoja odpowiedź to allliczby są przechowywane jako uzupełnienia do dwóch, to:

  int x = 15; // 11111111 11111111 11111111 11110001
  int y = -22 // 11111111 11111111 11111111 11101010

Zamieszanie tutaj znowu jest takie, że znak mówi, że obie są liczbami ujemnymi. Czy może to źle odczytałem / źle zrozumiałem?

Edytuj Nie jestem pewien, czy moje pytanie jest niejasne. Zmuszony do wyodrębnienia pytania:

Moje pytanie dokładnie: czy liczby dodatnie są przechowywane w, binary as ispodczas gdy liczby ujemne są przechowywane jako two's complement?

Niektórzy powiedzieli, że wszystkie są przechowywane w uzupełnieniu do dwóch, a jedna odpowiedź mówi, że tylko liczby ujemne są przechowywane jako uzupełnienia do dwóch.

Kevin Rave
źródło

Odpowiedzi:

104

Zacznijmy od podsumowania prymitywnych typów danych Java:

bajt : typ danych Byte to 8-bitowa liczba całkowita uzupełniająca do dwóch ze znakiem .

Krótki : Krótki typ danych to 16-bitowa liczba całkowita uzupełniająca do dwóch ze znakiem .

int: Int to 32-bitowa liczba całkowita z dopełnieniem do dwóch ze znakiem .

long: typ danych Long to 64-bitowa liczba całkowita z dopełnieniem do dwóch ze znakiem .

float: typ danych Float to 32-bitowy zmiennoprzecinkowy IEEE 754 o pojedynczej precyzji .

double : double typ danych to 64-bitowy zmiennoprzecinkowy podwójnej precyzji IEEE 754 .

boolean: boolean typ danych reprezentuje jeden bit informacji .

char: char typ danych to pojedynczy 16-bitowy znak Unicode .

Źródło

Uzupełnienie dwóch

„Dobrym przykładem jest wiki, że związek z dopełnieniem do dwóch jest realizowany poprzez odnotowanie, że 256 = 255 + 1, a (255 - x) jest uzupełnieniem x

0000 0111 = 7 dopełnienia do dwóch to 1111 1001 = -7

działa to tak, że MSB (najbardziej znaczący bit) otrzymuje wartość ujemną, więc w powyższym przypadku

-7 = 1001 = -8 + 0+ 0+ 1

Dodatnie liczby całkowite są zwykle przechowywane jako proste liczby binarne (1 to 1, 10 to 2, 11 to 3 itd.).

Ujemne liczby całkowite są przechowywane jako uzupełnienie do dwóch wartości bezwzględnych. Uzupełnienie do dwóch liczby dodatniej jest w przypadku użycia tego zapisu jako liczby ujemnej.

Źródło

Ponieważ otrzymałem kilka punktów za tę odpowiedź, postanowiłem dodać do niej więcej informacji.

Bardziej szczegółowa odpowiedź:

Między innymi istnieją cztery główne podejścia do przedstawiania liczb dodatnich i ujemnych w systemie dwójkowym, a mianowicie:

  1. Podpisana wielkość
  2. Dopełnienie
  3. Dopełnienie do dwóch
  4. Stronniczość

1. Podpisana wielkość

Używa najbardziej znaczącego bitu do reprezentowania znaku, pozostałe bity są używane do reprezentowania wartości bezwzględnej. Gdzie 0 oznacza liczbę dodatnią, a 1 oznacza liczbę ujemną , na przykład:

1011 = -3
0011 = +3

Ta reprezentacja jest prostsza. Jednak nie można dodawać liczb binarnych w taki sam sposób, jak dodaje się liczby dziesiętne, co utrudnia implementację na poziomie sprzętu. Co więcej, to podejście wykorzystuje dwa wzorce binarne do reprezentowania 0, -0 (1000) i +0 (0000) .

2. Uzupełnienie

W tej reprezentacji odwracamy wszystkie bity danej liczby, aby znaleźć jej komplementarność. Na przykład:

010 = 2, so -2 = 101 (inverting all bits).

Problem z tą reprezentacją polega na tym, że nadal istnieją dwa wzorce bitowe reprezentujące 0, ujemne 0 (1000) i dodatnie 0 (0000)

3. Dopełnienie do dwóch

Aby znaleźć minus liczby, w tej reprezentacji odwracamy wszystkie bity, a następnie dodajemy jeden bit. Dodanie jednego bitu rozwiązuje problem posiadania dwóch wzorców bitowych reprezentujących 0. W tej reprezentacji mamy tylko jeden wzorzec dla 0 (0000) .

Na przykład, chcemy znaleźć binarną ujemną reprezentację 4 (dziesiętnie) za pomocą 4 bitów. Najpierw zamieniamy 4 na binarne:

4 = 0100

następnie odwracamy wszystkie bity

0100 -> 1011

na koniec dodajemy trochę

1011 + 1 = 1100.

Więc 1100 jest równoważne -4 dziesiętnie, jeśli używamy binarnej reprezentacji dopełnienia Two z 4 bitami.

Szybszym sposobem znalezienia komplementarnego jest ustalenie pierwszego bitu o wartości 1 i odwrócenie pozostałych bitów. W powyższym przykładzie byłoby to coś takiego:

0100 -> 1100
^^ 
||-(fixing this value)
|--(inverting this one)

Reprezentacja dopełnienia do dwóch, oprócz posiadania tylko jednej reprezentacji dla 0, dodaje również dwie wartości binarne w taki sam sposób, jak w liczbach dziesiętnych, parzystych z różnymi znakami. Niemniej jednak konieczne jest sprawdzenie przypadków przepełnienia.

4. Odchylenie

Ta reprezentacja jest używana do reprezentowania wykładnika w normie IEEE 754 dla zmiennoprzecinkowych. Ma tę zaletę, że wartość binarna ze wszystkimi bitami do zera reprezentuje najmniejszą wartość. A wartość binarna ze wszystkimi bitami do 1 reprezentuje największą wartość. Jak sama nazwa wskazuje, wartość jest kodowana (dodatnio lub ujemnie) binarnie z n bitami z odchyleniem (zwykle 2 ^ (n-1) lub 2 ^ (n-1) -1).

Więc jeśli używamy 8 bitów, wartość 1 w systemie dziesiętnym jest reprezentowana binarnie z odchyleniem 2 ^ (n-1), przez wartość:

+1 + bias = +1 + 2^(8-1) = 1 + 128 = 129
converting to binary
1000 0001
dreamcrash
źródło
61

Liczby całkowite Java mają 32 bity i są zawsze podpisane. Oznacza to, że najbardziej znaczący bit (MSB) działa jako bit znaku. Liczba całkowita reprezentowana przez an intto nic innego jak ważona suma bitów. Wagi są przypisane w następujący sposób:

Bit#    Weight
31      -2^31
30       2^30
29       2^29
...      ...
2        2^2
1        2^1
0        2^0

Zauważ, że waga MSB jest ujemna (w rzeczywistości największa możliwa wartość ujemna), więc gdy ten bit jest włączony, całkowita liczba (suma ważona) staje się ujemna.

Zasymulujmy to liczbami 4-bitowymi:

Binary    Weighted sum            Integer value
0000       0 + 0 + 0 + 0           0
0001       0 + 0 + 0 + 2^0         1
0010       0 + 0 + 2^1 + 0         2
0011       0 + 0 + 2^1 + 2^0       3
0100       0 + 2^2 + 0 + 0         4
0101       0 + 2^2 + 0 + 2^0       5
0110       0 + 2^2 + 2^1 + 0       6
0111       0 + 2^2 + 2^1 + 2^0     7 -> the most positive value
1000      -2^3 + 0 + 0 + 0        -8 -> the most negative value
1001      -2^3 + 0 + 0 + 2^0      -7
1010      -2^3 + 0 + 2^1 + 0      -6
1011      -2^3 + 0 + 2^1 + 2^0    -5
1100      -2^3 + 2^2 + 0 + 0      -4
1101      -2^3 + 2^2 + 0 + 2^0    -3
1110      -2^3 + 2^2 + 2^1 + 0    -2
1111      -2^3 + 2^2 + 2^1 + 2^0  -1

Tak więc dopełnienie do dwóch nie jest wyłącznym schematem reprezentacji ujemnych liczb całkowitych, możemy raczej powiedzieć, że binarna reprezentacja liczb całkowitych jest zawsze taka sama, po prostu negujemy wagę najbardziej znaczącego bitu. I ten bit określa znak liczby całkowitej.

W języku C znajduje się słowo kluczowe unsigned(niedostępne w java), którego można użyć do zadeklarowania unsigned int x;. W liczbach całkowitych bez znaku waga MSB jest dodatnia ( 2^31), a nie ujemna. W takim przypadku zakres an unsigned intto 0to 2^32 - 1, a an intma zakres -2^31to 2^31 - 1.

Z innego punktu widzenia, jeśli weźmiesz pod uwagę uzupełnienie do dwóch xjako ~x + 1(NIE x plus jeden), oto wyjaśnienie:

Dla any x, ~xjest po prostu odwrotnością bitową do x, więc gdziekolwiek xma 1-bit, ~xbędzie 0tam -bit (i odwrotnie). Tak więc, jeśli dodasz je do siebie, nie będzie żadnego przeniesienia w dodawaniu, a suma będzie po prostu liczbą całkowitą, której każdy bit jest 1.

Dla 32-bitowych liczb całkowitych:

x + ~x = 1111 1111 1111 1111 1111 1111 1111 1111
x + ~x + 1 =   1111 1111 1111 1111 1111 1111 1111 1111 + 1
           = 1 0000 0000 0000 0000 0000 0000 0000 0000

Najbardziej lewy 1-bit zostanie po prostu odrzucony, ponieważ nie mieści się w 32-bitowych (przepełnienie liczby całkowitej). Więc,

x + ~x + 1 = 0
-x = ~x + 1

Widzisz więc, że negację xmożna przedstawić za pomocą ~x + 1, co nazywamy dopełnieniem do dwóch x.

0605002
źródło
Moje pytanie dokładnie: czy + ve liczb są przechowywane w, binary as ispodczas gdy -ve liczby są przechowywane w two's complement?
Kevin Rave
No tak. liczba ujemna jest reprezentowana przez komputer jako uzupełnienie do dwóch wartości dodatniej.
0605002
4
Świetna odpowiedź i wyjaśnienie Bonny @ 0605002, +1 :)
KM Rakibul Islam
@ 0605002: Czy mógłbyś podać odniesienie do tej odpowiedzi? Chociaż znałem koncepcje, ale nigdy tak naprawdę nie myślałem o nich w ten sposób. Najprostsza, wciąż dokładna odpowiedź.
Abhishek Singh
Cztery lata na uniwersytecie i nigdy nie rozumiałem uzupełnienia do dwóch. Ta odpowiedź nauczyła mnie więcej. To takie smutne, że na całym świecie naucza się tak prostych rzeczy w tak tajemniczy sposób.
Prashant Pandey,
10

Uruchomiłem następujący program, aby to wiedzieć

public class Negative {
    public static void main(String[] args) {
        int i =10;
        int j = -10;

        System.out.println(Integer.toBinaryString(i));
        System.out.println(Integer.toBinaryString(j));
    }
}

Wyjście jest

1010
11111111111111111111111111110110

Z wyników wynika, że ​​posługiwał się dopełnieniem do dwóch.

Dungeon Hunter
źródło
1
Uzupełnienie dwóch po 10 jest 11111111 11111111 11111111 11110110. Twoje wypisuje się, podczas gdy binarny dla 10 to 1010. Czyli tylko -ve liczby są przechowywane jako uzupełnienia do dwóch?
Kevin Rave
sprawdź artykuł na wiki en.wikipedia.org/wiki/ ... numer uzupełnienia 2, który podałeś dla 15 jest zły
Dungeon Hunter
jeśli bit msb zaczyna się od 1, będzie to liczba ujemna
Dungeon Hunter
tak, dopełnieniem 10 do dwóch jest 11111111 11111111 11111111 11110110, czyli -10
Dungeon Hunter
+ ve numery zostaną zapisane jako binarne, pozostawiając znak w uzupełnieniu 2
Dungeon Hunter,
5

Oracle udostępnia dokumentację dotyczącą typów danych Java, która może okazać się interesująca. Konkretnie:

int: typ danych int to 32-bitowa liczba całkowita dopełniająca do dwóch ze znakiem. Jego wartość minimalna wynosi -2 147 483 648, a maksymalna 2 147 483 647 (włącznie).

Przy okazji, short jest również przechowywane jako uzupełnienie do dwóch.

matsev
źródło
4

Liczby dodatnie są przechowywane / wczytywane bez zmian.

e.g) For +ve number 10; byte representation will be like 0-000 0010 
                                               (0 - MSB will represent that it is +ve).
So while retrieving based on MSB; it says it is +ve, 
so the value will be taken as it is. 

Ale liczby ujemne będą przechowywane po uzupełnieniu do 2 (innym niż bit MSB), a bit MSB zostanie ustawiony na 1.

np. podczas przechowywania -10 wtedy

  0-000 0010  -> (1's complement) -> 0-111 1101 
              -> (2's complement) 0-111 1101 + 1 -> 0-111 1110
  Now MSB will be set to one, since it is negative no -> 1-111 1110

podczas pobierania okazało się, że MSB jest ustawione na 1. Więc jest to minus nie. Uzupełnienie 2 zostanie wykonane inaczej niż MSB.

  1-111 1110  --> 1-000 0001 + 1 --> 1-000 0010
  Since MSB representing this is negative 10 --> hence  -10 will be retrived.

Odlew

Należy również pamiętać, że podczas rzutowania int / short do bajtu, tylko ostatni bajt będzie brany pod uwagę wraz z ostatnim bajtem MSB,

Weźmy przykład „-130” w skrócie, może być przechowywany jak poniżej

(MSB)1-(2's complement of)130(1000 0010) --> 1-111 1111 0111 1110

Teraz rzutowanie bajtów zajęło ostatni bajt, czyli 0111 1110. (0-MSB) Ponieważ MSB mówi, że jest to wartość + ve, zostanie przyjęty taki, jaki jest. To jest 126. (+ ve).

Weź inny przykład „130” w skrócie, może być przechowywany jak poniżej

  0-000 000 1000 0010     (MSB = 0)

Teraz rzutowanie bajtów zajęło ostatni bajt, czyli 1000 0010. (1 = MSB) Ponieważ MSB mówi, że jest to wartość -ve, zostanie wykonane uzupełnienie 2 i zostanie zwrócona liczba ujemna. Więc w tym przypadku -126 zostanie zwrócone.

 1-000 0010  -> (1's complement) -> 1-111 1101 
             -> (2's complement) 1-111 1101 + 1 -> 1-111 1110 -> (-)111 1110
               = -126

Różnica między (int) (char) (byte) -1 AND (int) (short) (byte) -1

(byte)-1       -> 0-000 0001 (2's Comp) -> 0-111 1111 (add sign) -> 1-111 1111
(char)(byte)-1 -> 1-111 1111 1111 1111  (sign bit is carry forwarded on left) 

podobnie

(short)(byte)-1-> 1-111 1111 1111 1111  (sign bit is carry forwarded on left) 

Ale

(int)(char)(byte)-1 -> 0-0000000 00000000 11111111 11111111  = 65535
since char is unsigned; MSB won't be carry forwarded. 

I

(int)(Short)(byte)-1 -> 1-1111111 11111111 11111111 11111111 = -1
since short is signed; MSB is be carry forwarded. 

Bibliografia

Dlaczego uzupełnienie do dwóch jest używane do reprezentowania liczb ujemnych?

Co to jest „Uzupełnienie 2”?

Kanagavelu Sugumar
źródło
3

Najbardziej znaczący bit (32.) wskazuje, że liczba jest dodatnia lub ujemna. Jeśli wynosi 0, oznacza to, że liczba jest dodatnia i jest przechowywana w rzeczywistej reprezentacji binarnej. ale jeśli jest 1, oznacza to, że liczba jest ujemna i jest przechowywana w reprezentacji dopełnienia do dwóch. Kiedy więc przypisujemy wagę -2 ^ 32 do 32-go bitu, jednocześnie przywracając wartość całkowitą z jego reprezentacji binarnej, otrzymujemy rzeczywistą odpowiedź.

Sazzadur Rahaman
źródło
1
Witamy w StackOverflow! : D
0605002
3

Zgodnie z tym dokumentem wszystkie liczby całkowite są podpisywane i przechowywane w formacie dopełnienia do dwóch dla języka Java. Nie jestem pewien co do jego niezawodności.

Joel
źródło
„W formacie uzupełnienia do dwóch wartość dodatnia jest reprezentowana jako prosta liczba binarna”. napisane w tym samym dokumencie… więc technicznie jest poprawne. :)
Shashi
2

liczby dodatnie są przechowywane bezpośrednio jako binarne. Komplement 2 jest wymagany dla liczb ujemnych.

na przykład:

15: 00000000 00000000 00000000 00001111-15
: 11111111 11111111 11111111 11110001

tutaj jest różnica w bitach ze znakiem.

Siva Padhy
źródło
2

Dziękuję, dreamcrash za odpowiedź https://stackoverflow.com/a/13422442/1065835 ; na stronie wiki podają przykład, który pomógł mi zrozumieć, jak znaleźć binarną reprezentację ujemnego odpowiednika liczby dodatniej.

Na przykład, używając 1 bajtu (= 2 półbajty = 8 bitów), liczba dziesiętna 5 jest reprezentowana przez

0000 01012 Najbardziej znaczący bit ma wartość 0, więc wzorzec reprezentuje wartość nieujemną. Aby przekonwertować na −5 w notacji z uzupełnieniem do dwóch, bity są odwracane; 0 staje się 1, a 1 staje się 0:

1111 1010 W tym miejscu liczebnik jest uzupełnieniem jedności wartości dziesiętnej −5. Aby uzyskać uzupełnienie do dwóch, do wyniku dodaje się 1, co daje:

1111 1011 Wynikiem jest liczba binarna ze znakiem, reprezentująca wartość dziesiętną −5 w postaci uzupełnienia do dwóch. Najbardziej znaczący bit to 1, więc reprezentowana wartość jest ujemna.

Maksim Dmitriev
źródło
1

Dla dodatniej liczby całkowitej 2 'wartość uzupełnienia jest taka sama, jak bit 0 MSB (like +14 2'complement is 01110) .

Dla tylko ujemnych liczb całkowitych obliczamy wartość uzupełnienia 2 ' (-14= 10001+1 = 10010) .

Tak więc ostateczna odpowiedź brzmi: obie wartości (+ve and -ve)są przechowywane tylko w postaci uzupełnienia 2 '.

Mangesh Gawali
źródło