Nie długo trwało, aby kilka maili między mną a rozmówcą zmieniło temat główny na (nieznacznie) poboczny - zalążek projektu librarian-clojure.
W ten sposób poniosło mnie (dosłownie i w przenośni) na Heroku, gdzie uruchomiłem webową wersję HelloWorld z Clojure'owym Ring.
Pewnie dla niejednego jest to o wiele za wiele, ale czego nie robi się dla zauważalnego rozwoju informatycznego, w którym nie ma miejsca dla już poznanego, a jedynie nieznacznie odświeżonego, a raczej próbuje się czegoś zupełnie nowego, np. zmiana języka obiektowego (Java, Scala) na funkcyjny (Clojure), albo zmiana języka statycznie typowanego (Java, Scala) na dynamiczny (Clojure, JRuby). Człowiek ponownie czuje się niedoświadczony i w ogóle (przesadnie) zagubiony. Podobno tylko tak można się czegoś nowego nauczyć w naszej branży.
Pożyjemy, zobaczymy. A teraz ciii...Clojure się zbliża!
Kiedy projekt trafił w ręce mojego rozmówcy, padło kilka pytań, które pomyślałem, że zadaje więcej osób, więc postanowiłem odpowiedzieć na nie w formie wpisu na blogu (a nóż widelec kogoś skusi i wejdzie w temat - byłoby cudnie - niechby chociaż komentował, jak to beznadziejnie nam idzie!) Marzą mi się regularne sesje, w których z kimś zasiadałbym przy IRC i jakoś współdzieląc ekran programował w parze zdalnie. Podobno się daje i jedynie wystarczy trochę chęci. Znajdzie się ktoś na ochotnika do librarian-clojure? Regularne sesje - stała pora, stała długość sesji i stałe miejsce mogłyby przyciągnąć innych, choćby do pooglądania. Cudo pomysł!
A teraz do pytań.
Jako IDE Eclipse?
"Jedynie" Clojure REPL (powłoka Clojure).
Jeśli jednak potrzebujesz wskazówek, to możesz skorzystać z Eclipse z wtyczką CounterClockWise (CCW) lub IntelliJ IDEA i La Clojure. Możesz spróbować Emacs.
Ja pracuję nad sobą, aby skorzystać z dobrodziejstw Eclipse CCW.
Czy project.clj to manifest?
Zależy co rozumiesz przez manifest? Ten javowy, to nie, ale manifest jako główny plik konfiguracyjny projektu, to jak najbardziej.
Innymi słowy, jest to serce projektu zarządzanego przez leiningen (odpowiednik Mavena w świecie Clojure).
Dlaczego nadałeś rozszerzenie *.md dla pliku README?
Chcę korzystać ze wspacia dla markdown przez GitHub, który rozpoznaje takie pliki jako pisane w tym metajęzyku. Daje to formatowanie tekstu bez większych udziwnień (niż te, których wymaga sam markdown).
Czy ns (namespace) to analogia dla pakietów w Javie?
Prawie. To właściwie javowy odpowiednik FQCN (ang. fully-qualified class name), czyli pakiet + nazwa klasy.
Każdy plik w Clojure to zwykle zestaw funkcji (nic jednak nie stoi na przeszkodzie, abyś potworzył przestrzenie nazw, a w nich funkcje itd.) Zachowując jednak zdrowy rozsądek, rozsądnie jest potraktować pojedynczy plik clj z ns jako klasę, w której na początku znajduje się deklaracja przestrzeni nazewniczej, w której "siedzi" również nazwa pliku (coś ala javowa klasa).
Czy :use to analogia do import w Javie?
Tak.
Czy deftest to słowo kluczowe definiujące funkcję 'testową' analogicznie do anotacji @org.junit.Test?
Tak.
Jakie wykorzystanie gita preferujesz - z poziomu powłoki systemowej, czy IDE, np. Eclipse EGit?
Powłoka. Javowe IDE wspierają gita, więc kiedy się już zdecydujesz, znajdziesz i wsparcie dla gita. Przekonuję się do Eclipse EGit.
26 styczeń 2012
20 styczeń 2012
Clojure finansowo z makrem -> (wplatanie na drugą pozycję)
Pisałem w poprzednim wpisie o moich ponownych poczynaniach wokół Clojure, aby w końcu zrozumieć jego istotę i w ogóle istotę programowania funkcyjnego.
Kontynuując moje "naukowe" aktywności zakończyłem lekturę "The Joy of Clojure: Thinking the Clojure Way", którą podsumowałem recenzją The "Why" of Clojure - mind-bending for enlightenment with idiomatic Clojure code w serwisie Amazon.com (nakłaniam do oddaniu głosu) i zabrałem się za kolejną książkę Clojure – Grundlagen, Concurrent Programming, Java. Tym razem będzie po niemiecku, a przez to zdecydowanie trudniej (dawno to było, kiedy władałem tym językiem w stopniu zadowalającym).
Jakby celem utrudnienia i tak już niełatwego zadania nauki Clojure po niemiecku, dostałem od Manning Clojure in Action, co przyprawiło mnie o niemały ból głowy - brnąć w przypominanie sobie niemieckiego (jedno z postanowień noworocznych), czy odłożyć to i zabrać się za drugą książkę, która pisana była z myślą o tym "Jak to zrobić w Clojure". Na razie Clojure z niemieckim przeważa.
Przeglądając reakcję czytelników po ostatnim wpisie Clojure finansowo uzasadniłem moje wewnętrzne przekonanie, że należy kontynuować temat programowania funkcyjnego z Clojure.
I właśnie w tym momencie zorientowałem się, że w prezentowanej aplikacji najbardziej zabrakło idiomatycznego Clojure, o którym tak wiele pisano w "The Joy of Clojure".
Było tak:
Mówią, że po ilości idiomatyczych konstrukcji poznaje się poziom zaawansowania w danej dziedzinie i nie inaczej jest w programowaniu - czy to w Javie, czy Clojure, czy innym języku, nawet takim jak angielski, niemiecki, itp.
A jak to jest u Ciebie z idiomatycznymi konstrukcjami? Znasz jakieś w Javie? Ciekawym również Scali (pewnie _ jest swego rodzaju idiomem) czy JRuby.
Kontynuując moje "naukowe" aktywności zakończyłem lekturę "The Joy of Clojure: Thinking the Clojure Way", którą podsumowałem recenzją The "Why" of Clojure - mind-bending for enlightenment with idiomatic Clojure code w serwisie Amazon.com (nakłaniam do oddaniu głosu) i zabrałem się za kolejną książkę Clojure – Grundlagen, Concurrent Programming, Java. Tym razem będzie po niemiecku, a przez to zdecydowanie trudniej (dawno to było, kiedy władałem tym językiem w stopniu zadowalającym).
Jakby celem utrudnienia i tak już niełatwego zadania nauki Clojure po niemiecku, dostałem od Manning Clojure in Action, co przyprawiło mnie o niemały ból głowy - brnąć w przypominanie sobie niemieckiego (jedno z postanowień noworocznych), czy odłożyć to i zabrać się za drugą książkę, która pisana była z myślą o tym "Jak to zrobić w Clojure". Na razie Clojure z niemieckim przeważa.
Przeglądając reakcję czytelników po ostatnim wpisie Clojure finansowo uzasadniłem moje wewnętrzne przekonanie, że należy kontynuować temat programowania funkcyjnego z Clojure.
I właśnie w tym momencie zorientowałem się, że w prezentowanej aplikacji najbardziej zabrakło idiomatycznego Clojure, o którym tak wiele pisano w "The Joy of Clojure".
Było tak:
; zakładam 366 dni w roku 2012 i kapitalizację w dni wolne (niesprawdzone)
(defn interest-rate-per-day [interest-rate-per-year]
(/ (* interest-rate-per-year 0.01) 366))
; funkcja pomocnicza do wyliczenia zysku (niewykorzystywana)
(defn interest [present-value interest-rate]
(- (* present-value (inc interest-rate)) present-value))
(defn future-value [present-value interest-rate periods]
(* present-value (Math/pow (inc (interest-rate-per-day interest-rate)) periods)))
(defn max-present-value [limit interest-rate periods]
(/ limit (Math/pow (inc (interest-rate-per-day interest-rate)) periods)))
(max-present-value 10000 8.1 31)Powinno być jednak tak (miejsca oznaczone przez ",,," w pierwszej funkcji służą *jedynie* wskazaniu, gdzie argument zostanie przekazany przez makro -> - usuń je, a zobaczysz zmianę, a raczej jej brak!):; zakładam 366 dni w roku 2012 i kapitalizację w dni wolne (niesprawdzone)
(defn interest-rate-per-day [interest-rate-per-year]
(-> interest-rate-per-year
(* ,,, 0.01)
(/ ,,, 366)))
(defn future-value [present-value interest-rate periods]
(-> interest-rate
interest-rate-per-day
inc
(Math/pow periods)
(* present-value)))
; teraz dopiero zauważyłem, że future-value jest skopiowane w części do max-present-value :(
(defn max-present-value [limit interest-rate periods]
(let [v (-> interest-rate interest-rate-per-day inc (Math/pow periods))]
(/ limit v)))
(max-present-value 10000 8.1 31)Od razu ładniej, nieprawdaż?Mówią, że po ilości idiomatyczych konstrukcji poznaje się poziom zaawansowania w danej dziedzinie i nie inaczej jest w programowaniu - czy to w Javie, czy Clojure, czy innym języku, nawet takim jak angielski, niemiecki, itp.
A jak to jest u Ciebie z idiomatycznymi konstrukcjami? Znasz jakieś w Javie? Ciekawym również Scali (pewnie _ jest swego rodzaju idiomem) czy JRuby.
04 styczeń 2012
Clojure finansowo
Maksym to straszny brojek się robi. Kiedykolwiek przyglądam mu się bacznie, bez względu na jego minkę, widzę w nim gościa, którego będzie nosiło. Aż boimy się z Agatą pomyśleć, co będzie, kiedy zacznie raczkować, a później chodzić. Brrr...Będzie jazda bez trzymanki (jak u Owsiaka na WOŚPie)!
Gość właśnie skończył 3 miesiące i rośnie jak na drożdżach. Zdjęcie z miarką jest z 18 grudnia i teraz jest jeszcze dłuższy! Niech rośnie w siłę, aby tatusiowi na emeryturę zarobić :)
Jeszcze.
Siedzę od lat w Javie, głównie w jej wydaniu korporacyjnym (Java EE), i kiedykolwiek pytany o możliwości Clojure, moim ochom i echom nie ma końca. Szybko się jednak kończy, kiedy pada "A jaką aplikację możnaby w tym napisać, aby widać było zysk w porównaniu, chociażby, z Javą?". I tu mnie pot zalewa, zaczynam czkać i kończy się na mizernym "Nie wiem". Właśnie na tym chciałbym popracować w tym roku. Muszę to wiedzieć, albo pora zarzucić Clojure jako język, któremu poświęcam czas.
Czytam sobie pomalutku "The Joy of Clojure: Thinking the Clojure Way" i poszukuję odpowiedzi na nurtujące mnie odpowiedzi sensowności stosowania języka przy tworzeniu aplikacji korporacyjnych (niechby to były wyłącznie aplikacje webowe). Wiem o istnieniu Compojure, Ring i podobnych rozwiązań, ale jakoś do mnie nie przemawiają, bo...tak naprawdę w ogóle się z nimi nie zmierzyłem na dłużej niż kilka chwil. To uważam za głównego winowajcę moich trudów mentalnych wokół Clojure.
I właśnie w tym roku postanowiłem to zmienić. Albo teraz, albo nigdy.
To górne ograniczenie mnie zaintrygowało. Moje skromne pokłady wiedzy finansowej zostały lekko nadwyrężone, kiedy miałem policzyć, ile należy wpłacić, aby nie przekroczyć 10k w ciągu miesiąca, w którym mam do dyspozycji jeden przelew bezpłatny. Chodziło o znalezienie tej magicznej kwoty, z którą mogłem spokojnie przespać 29 nocy, aby przed 30. przelać różnicę niezbędną do "przeczekania" kolejnego miesiąca (i tak wyłącznie do 28 lutego).
Wystarczyło otworzyć Google Docs i policzyć. Można było również skorzystać z kalkulatorów różnej maści w Sieci, albo LibreOffice, ale mnie zachciało się...Clojure (później dopiero doszło do mnie, że to był przerost formy nad treścią, ale co wiem, to moje).
Chcesz spróbować samodzielnie? Nic trudnego. Przekonaj się sam(a)!
Zainstaluj lein zgodnie z dokumentacją na stronie domowej projektu. Sprowadza się to do pobrania skryptu lein i kilku drobnych systemowych ustawień.
Teraz już tylko kilka chwil i siedzisz w Clojure po pachy.
Czy nazwy funkcji odpowiadają zamierzeniom autora (patrząc oczyma czytelnika)? Czy zrobił(a)byś to inaczej? Daj się namówić na podzielenie się kilkoma usprawnieniami, aby biedną duszyczkę jackową uchować od ogni piekielnych :)
Gość właśnie skończył 3 miesiące i rośnie jak na drożdżach. Zdjęcie z miarką jest z 18 grudnia i teraz jest jeszcze dłuższy! Niech rośnie w siłę, aby tatusiowi na emeryturę zarobić :)
Clojure
Jeszcze w zeszłym roku zabrałem się ponownie za Clojure i w ramach postanowień noworocznych zdecydowałem się rozpoznać możliwość wykorzystania tego języka do tworzenia aplikacji biznesowych. Wiem, że ludzie w tym coś robią i powstają systemy korporacyjne, ale ja jakoś tego nie czuję.Jeszcze.
Siedzę od lat w Javie, głównie w jej wydaniu korporacyjnym (Java EE), i kiedykolwiek pytany o możliwości Clojure, moim ochom i echom nie ma końca. Szybko się jednak kończy, kiedy pada "A jaką aplikację możnaby w tym napisać, aby widać było zysk w porównaniu, chociażby, z Javą?". I tu mnie pot zalewa, zaczynam czkać i kończy się na mizernym "Nie wiem". Właśnie na tym chciałbym popracować w tym roku. Muszę to wiedzieć, albo pora zarzucić Clojure jako język, któremu poświęcam czas.
Czytam sobie pomalutku "The Joy of Clojure: Thinking the Clojure Way" i poszukuję odpowiedzi na nurtujące mnie odpowiedzi sensowności stosowania języka przy tworzeniu aplikacji korporacyjnych (niechby to były wyłącznie aplikacje webowe). Wiem o istnieniu Compojure, Ring i podobnych rozwiązań, ale jakoś do mnie nie przemawiają, bo...tak naprawdę w ogóle się z nimi nie zmierzyłem na dłużej niż kilka chwil. To uważam za głównego winowajcę moich trudów mentalnych wokół Clojure.
I właśnie w tym roku postanowiłem to zmienić. Albo teraz, albo nigdy.
...finansowo
Ostatnimi czasy wzięło mnie na porównywanie ofert różnych banków dotyczących lokat (głównie "antybelkowych") i rachunków oszczędnościowych (z dniowym naliczaniem odsetek). Na bankier.pl trafiłem na ofertę Deutsche Banku z kontem oszczędnościowym z kapitalizacją 8,1% (bez podatku od zysków kapitałowych przy założeniu, że nie przekroczymy 10k PLN).To górne ograniczenie mnie zaintrygowało. Moje skromne pokłady wiedzy finansowej zostały lekko nadwyrężone, kiedy miałem policzyć, ile należy wpłacić, aby nie przekroczyć 10k w ciągu miesiąca, w którym mam do dyspozycji jeden przelew bezpłatny. Chodziło o znalezienie tej magicznej kwoty, z którą mogłem spokojnie przespać 29 nocy, aby przed 30. przelać różnicę niezbędną do "przeczekania" kolejnego miesiąca (i tak wyłącznie do 28 lutego).
Wystarczyło otworzyć Google Docs i policzyć. Można było również skorzystać z kalkulatorów różnej maści w Sieci, albo LibreOffice, ale mnie zachciało się...Clojure (później dopiero doszło do mnie, że to był przerost formy nad treścią, ale co wiem, to moje).
Chcesz spróbować samodzielnie? Nic trudnego. Przekonaj się sam(a)!
Zainstaluj lein zgodnie z dokumentacją na stronie domowej projektu. Sprowadza się to do pobrania skryptu lein i kilku drobnych systemowych ustawień.
Teraz już tylko kilka chwil i siedzisz w Clojure po pachy.
jacek:~/sandbox $ lein new clojure-finansowo Created new project in: /Users/jacek/sandbox/clojure-finansowo Look over project.clj and start coding in clojure_finansowo/core.clj jacek:~/sandbox $ cd clojure-finansowo/ jacek:~/sandbox/clojure-finansowo $ lein repl Copying 1 file to /Users/jacek/sandbox/clojure-finansowo/lib REPL started; server listening on localhost port 25483 user=>I jesteś w REPL - interaktywnej powłoce Clojure. Skorzystaj z poniższego skryptu, aby wyliczyć ILE trzeba włożyć, aby nie przekroczyć magicznego 10k w miesiącu, w którym masz jeden przelew darmowy (wliczając przelew na rachunek spoza banku).
; zakładam 366 dni w roku 2012 i kapitalizację w dni wolne (niesprawdzone)
(defn interest-rate-per-day [interest-rate-per-year]
(/ (* interest-rate-per-year 0.01) 366))
; funkcja pomocnicza do wyliczenia zysku (niewykorzystywana)
(defn interest [present-value interest-rate]
(- (* present-value (inc interest-rate)) present-value))
(defn future-value [present-value interest-rate periods]
(* present-value (Math/pow (inc (interest-rate-per-day interest-rate)) periods)))
(defn max-present-value [limit interest-rate periods]
(/ limit (Math/pow (inc (interest-rate-per-day interest-rate)) periods)))
(max-present-value 10000 8.1 31)Nie jest to cudo programowania w Clojure, ale nie miało takim być. Służyło jedynie odświeżeniu moich znajomości z Clojure i uważam, że ten cel został w pełni zrealizowany. Przede wszystkim, zrealizowałem swój własny cel biznesowy (a właściwie finansowy, ale przecież to to samo).Czy nazwy funkcji odpowiadają zamierzeniom autora (patrząc oczyma czytelnika)? Czy zrobił(a)byś to inaczej? Daj się namówić na podzielenie się kilkoma usprawnieniami, aby biedną duszyczkę jackową uchować od ogni piekielnych :)
03 styczeń 2012
O operatorach przesunięć w Javie...prawie wszystko
Na zakończenie 2011 zasiadłem do rozpoznania wewnętrznej reprezentacji liczb całkowitych w Javie i w ten sposób powstały dwa wpisy:
Dla przypomnienia:
& (AND) zwraca 1, wyłącznie jeśli oba bity są 1.
^ (XOR) zwraca 0, jeśli oba bity są jednocześnie 0 lub 1.
| (OR) zwraca 0, wyłącznie jeśli oba bity są 0.
Kolejność działań: &, ^, |
Jeśli typem lewego argumentu jest int, jedynie 5 najmłodszych bitów jest branych pod uwagę. Dlaczego? Taka jest długość bitowej reprezentacji int, tzn. 5 bitów pozwala na określenie zakresu przesunięcia od 0 do 31 włącznie, a tylko takie ma sens w przypadku 32 bitowej reprezentacji liczby całkowitej. W myśl tej zasady prawy argument jest zawsze pomniejszany przez zastosowanie operatora logicznego AND z maską 0x1F (0b11111), aby nie wyjść poza zakres [0, 31].
Jeśli jednak typem lewego argumentu jest long, wtedy jedynie 6 najmłodszych bitów jest branych pod uwagę. Ponownie, tylko tyle bitów - 2^6 - służy do reprezentacji bitowej dowolnej liczby long. Tym razem stosujemy logiczny AND z maską 0x3F (= 0b111111) i przesunięcie jest wykonane w zakresie 0 do 63 włącznie.
Lewy argument typu long nie wymusza promocji argumentu prawego do long, gdyż i tak int jest wystarczający, aby określić zakres przesunięcia [0-63] (przez zastosowanie maski 0x3F).
Przesunięcie w lewo ze znakiem jest równoważne iloczynowi lewego operandu przez 2 do potęgi s, tj. n * 2^s.
Przykład: 11 << 3 = 11 * 2^3 = 11 * 8 = 88
Dla liczb nieujemnych, przesunięcie w prawo ze znakiem jest równoważne z obliczeniem ilorazu (bez reszty) lewego operandu przez 2 do potęgi s, tj. n / 2^s.
Przykład: 11 >> 3 = 11 / 2^3 = 11 / 8 = 1
Z przesunięciem bez znaku "wypełniaczem" staje się 0, co może zamazać bit znaku i zmienić znak wyniku, który zawsze będzie dodatni.
Próbując wyrazić działanie >>> wzorem stosuje się następującą zasadę - jeśli lewy operand jest dodatni, wtedy wynik jest identyczny z prawym przesunięciem ze znakiem. Jeśli jednak lewy operand jest ujemy, wtedy wynik równa się (n >> s) + (2 << ~s). I właśnie ten wzór mnie zmroził najbardziej. Aż mnie do tej pory ciarki przechodzą :)
Przykład: 11 >>> 3 = 11 >> 3 = 11 / 2^3 = 1
Tylko skąd pomysł na >>>?! Na pewno nie zamierzam zapamiętać wzoru na wynik (chociaż przy przeglądaniu Sieci i spisywaniu wiedzy już zagnieździło się w głowie). Musi być tego jakieś sensowne uzasadnienie.
Dopiero w The Unsigned Right Shift olśniło mnie, kiedy trafiłem na możliwe zastosowanie operatora prawego przesunięcia bez znaku "shifting bits that does not represent a numeric value, e.g. pixel-based values and graphics."
I uzupełniając, w Bit twiddling in Java: The Unsigned Right Shift Operator:
Mimo, że każdy ciąg bitów o długości mniejszej niż 64 (najdłuższy typ w Javie - long) reprezentuje pewną liczbę całkowitą, to jedynie przesunięcia ze znakiem szanują reprezentację ciągu w postaci liczby - zachowują znak, a on ma znaczenie przy liczbach. W przypadku przesunięcia w prawo bez znaku >>> reprezentacja liczbowa nie ma znaczenia, a jedynie ciąg bitów - właśnie przez brak dbałości o znak liczby.
Innymi słowy, główne zastosowanie prawego przesunięcia bez znaku to sterowniki urządzeń, niskopoziomowa obsługa grafiki i formatów graficznych, pakiety komunikacyjne, kryptografia. W mojej karierze z Javą nigdy jednak nie spotkałem się z takimi zadaniami, ani chociażby minimalnego użycia operatorów przesunięcia. Zdają się być zbyt magiczne, aby miały zastosowanie nad chociażby java.lang.Math.pow(double, double). Mówi się również, że maksymalna liczba możliwych pytań z operatorów przesunięć na egzaminie z SCJP nie przekracza...jednego (!)
Zagadka: Jaki będzie wynik dowolnego przesunięcia liczby 0xFFFFFFFF (8 znaków F, tj. 32 jedynki) dla operatorów prawego przesunięcia ze znakiem?
W artykule Bitwise operation znalazłem bardzo intrygujące zachowanie przesunięć.
Zacznijmy od zagadki: Jaki będzie wynik odpowiednich przesunięć - (-12 >> 2) << 2, (-12 << 2) >> 2, (-12 >>> 2) << 2, (-12 << 2) >>> 2?
UWAGA: Przesunięcia typów mniej pojemnych, które będą rozszerzane do int - do 32 bitów, np. 8-bitowy byte rozszerzany jest do 32 bitowego int, więc przesunięcie >>> może nie mieć żadnego wpływu i należy maskować liczbę przed przesunięciem, np. (b & 0xFF) >>> 2.
Przesunięcie w prawo zawsze skutkuje "wypadaniem" liczb poza koniec (jakby wpadały w przepaść i były tracone na zawsze).
W The SCJP Tip Line Bit Shifting by Corey McGlone trafiłem na ciekawą zagadkę, która wynika bezpośrednio z powyższych reguł przesunięcia liczb całkowitych (szczególnie maskowaniem prawego operandu).
Zagadka: Jaki będzie wynik 3 >>> 32?
Na odpowiedź masz jedynie sekundę :)
Pamiętasz maskowanie prawego operandu przed wykonaniem przesunięcia? Dla int będzie to maska 0x1F, czyli 32. Czy teraz łatwiej odpowiedzieć na powyższe pytanie? To jaki będzie wynik?
Wystarczy zastosować mod 32 i masz gotową odpowiedź.
3 >>> 32 = 3 >>> (32 % 32) = 3 >>> 0 = 3
Fajne, co?! Właśnie takie cuda w Javie i w ogóle w językach programowania nakręcają mnie na dalsze ich zgłębianie. Czego i Tobie życzę w Nowym Roku 2012! :)
- Kod uzupełnień do dwóch w Javie (reprezentacja binarna liczb całkowitych)
- O kodzie uzupełnień do dwóch w Javie raz jeszcze
Dla przypomnienia:
& (AND) zwraca 1, wyłącznie jeśli oba bity są 1.
^ (XOR) zwraca 0, jeśli oba bity są jednocześnie 0 lub 1.
| (OR) zwraca 0, wyłącznie jeśli oba bity są 0.
Kolejność działań: &, ^, |
Wstępniak
Java definiuje 3 operatory przesunięcia - w lewo ze znakiem <<, w prawo ze znakiem >> i w prawo bez znaku >>>. Wszystkie działają wyłącznie na typach całkowitych long (64 bity) lub int (32 bity) i typ lewego argumentu wyznacza typ prawego. W przypadku węższych typów - short, byte, char - są one promowane do int i to po obu stronach niezależnie.Jeśli typem lewego argumentu jest int, jedynie 5 najmłodszych bitów jest branych pod uwagę. Dlaczego? Taka jest długość bitowej reprezentacji int, tzn. 5 bitów pozwala na określenie zakresu przesunięcia od 0 do 31 włącznie, a tylko takie ma sens w przypadku 32 bitowej reprezentacji liczby całkowitej. W myśl tej zasady prawy argument jest zawsze pomniejszany przez zastosowanie operatora logicznego AND z maską 0x1F (0b11111), aby nie wyjść poza zakres [0, 31].
Jeśli jednak typem lewego argumentu jest long, wtedy jedynie 6 najmłodszych bitów jest branych pod uwagę. Ponownie, tylko tyle bitów - 2^6 - służy do reprezentacji bitowej dowolnej liczby long. Tym razem stosujemy logiczny AND z maską 0x3F (= 0b111111) i przesunięcie jest wykonane w zakresie 0 do 63 włącznie.
Lewy argument typu long nie wymusza promocji argumentu prawego do long, gdyż i tak int jest wystarczający, aby określić zakres przesunięcia [0-63] (przez zastosowanie maski 0x3F).
35 00000000 00000000 00000000 00100011
31 -> 0x1f 00000000 00000000 00000000 00011111
& -----------------------------------
00000000 00000000 00000000 00000011 -> 3
-29 11111111 11111111 11111111 11100011
31 -> 0x1f 00000000 00000000 00000000 00011111
& -----------------------------------
00000000 00000000 00000000 00000011 -> 3
Interesujący wydał mi się ten drugi przykład, gdzie prawy operand -29 daje ostatecznie przesunięcie 3 bitów (!) Z takim pytaniem na egzaminie znajomości Javy można łatwo polec.Operator lewego przesunięcia ze znakiem <<
Działanie n << s to przesunięcie s bitów w n z uwzględnieniem bitu znaku, czyli zakres działania to 31 bitów dla lewego operandu typu int lub 63 dla long (odpowiednio maskowane jak opisałem wyżej). Nowe bity po prawej, które pojawią się przy przesunięciu, są wypełniane zerami.Przesunięcie w lewo ze znakiem jest równoważne iloczynowi lewego operandu przez 2 do potęgi s, tj. n * 2^s.
Przykład: 11 << 3 = 11 * 2^3 = 11 * 8 = 88
11 (binarnie) 0000 0000 0000 0000 0000 0000 0000 1011 przesunięcie o 3 0000 0000 0000 0000 0000 0000 0101 1000 wynik: 88 (dziesiętnie)Podobnie z liczbami ujemnymi.
Operator prawego przesunięcia ze znakiem >>
Działanie n >> s to przesunięcie s bitów w n z uwzględnieniem bitu znaku, czyli zakres działania to 31 bitów dla lewego operandu typu int lub 63 dla long (odpowiednio maskowane). Przy przesunięciu w prawo ze znakiem "wypełniaczem" miejsc pustych jest najważniejszy bit - bit znaku, tj. 0 dla dodatnich i 1 dla ujemnych.Dla liczb nieujemnych, przesunięcie w prawo ze znakiem jest równoważne z obliczeniem ilorazu (bez reszty) lewego operandu przez 2 do potęgi s, tj. n / 2^s.
Przykład: 11 >> 3 = 11 / 2^3 = 11 / 8 = 1
11 (binarnie) 0000 0000 0000 0000 0000 0000 0000 1011 przesunięcie o 3 0000 0000 0000 0000 0000 0000 0000 0001 wynik: 1 (dziesiętnie)Przykład: -17 >> 3 = -3
-17 (binarnie) 1111 1111 1111 1111 1111 1111 1110 1111 przesunięcie o 3 1111 1111 1111 1111 1111 1111 1111 1101 wynik: -3 (dziesiętnie)
Operator prawego przesunięcia bez znaku >>>
Działanie n >>> s to przesunięcie s bitów w n wliczając bit znaku (bit znaku traci swoją wyjątkowość i jest traktowany jak każdy inny bit).Z przesunięciem bez znaku "wypełniaczem" staje się 0, co może zamazać bit znaku i zmienić znak wyniku, który zawsze będzie dodatni.
Próbując wyrazić działanie >>> wzorem stosuje się następującą zasadę - jeśli lewy operand jest dodatni, wtedy wynik jest identyczny z prawym przesunięciem ze znakiem. Jeśli jednak lewy operand jest ujemy, wtedy wynik równa się (n >> s) + (2 << ~s). I właśnie ten wzór mnie zmroził najbardziej. Aż mnie do tej pory ciarki przechodzą :)
Przykład: 11 >>> 3 = 11 >> 3 = 11 / 2^3 = 1
11 (binarnie) 0000 0000 0000 0000 0000 0000 0000 1011 przesunięcie o 3 0000 0000 0000 0000 0000 0000 0000 0001 wynik: 1 (dziesiętnie)Przykład: -17 >>> 3 = 536870909
-17 (binarnie) 1111 1111 1111 1111 1111 1111 1110 1111 przesunięcie o 3 0001 1111 1111 1111 1111 1111 1111 1101 wynik: 536870909 (dziesiętnie)
Zastosowanie przesunięć
Operatory ze znakiem to odpowiednio mnożenie i dzielenie lewego operanda przez s-tą potęgę dwójki.Tylko skąd pomysł na >>>?! Na pewno nie zamierzam zapamiętać wzoru na wynik (chociaż przy przeglądaniu Sieci i spisywaniu wiedzy już zagnieździło się w głowie). Musi być tego jakieś sensowne uzasadnienie.
Dopiero w The Unsigned Right Shift olśniło mnie, kiedy trafiłem na możliwe zastosowanie operatora prawego przesunięcia bez znaku "shifting bits that does not represent a numeric value, e.g. pixel-based values and graphics."
I uzupełniając, w Bit twiddling in Java: The Unsigned Right Shift Operator:
Mimo, że każdy ciąg bitów o długości mniejszej niż 64 (najdłuższy typ w Javie - long) reprezentuje pewną liczbę całkowitą, to jedynie przesunięcia ze znakiem szanują reprezentację ciągu w postaci liczby - zachowują znak, a on ma znaczenie przy liczbach. W przypadku przesunięcia w prawo bez znaku >>> reprezentacja liczbowa nie ma znaczenia, a jedynie ciąg bitów - właśnie przez brak dbałości o znak liczby.
Innymi słowy, główne zastosowanie prawego przesunięcia bez znaku to sterowniki urządzeń, niskopoziomowa obsługa grafiki i formatów graficznych, pakiety komunikacyjne, kryptografia. W mojej karierze z Javą nigdy jednak nie spotkałem się z takimi zadaniami, ani chociażby minimalnego użycia operatorów przesunięcia. Zdają się być zbyt magiczne, aby miały zastosowanie nad chociażby java.lang.Math.pow(double, double). Mówi się również, że maksymalna liczba możliwych pytań z operatorów przesunięć na egzaminie z SCJP nie przekracza...jednego (!)
Zagadka: Jaki będzie wynik dowolnego przesunięcia liczby 0xFFFFFFFF (8 znaków F, tj. 32 jedynki) dla operatorów prawego przesunięcia ze znakiem?
W artykule Bitwise operation znalazłem bardzo intrygujące zachowanie przesunięć.
Zacznijmy od zagadki: Jaki będzie wynik odpowiednich przesunięć - (-12 >> 2) << 2, (-12 << 2) >> 2, (-12 >>> 2) << 2, (-12 << 2) >>> 2?
UWAGA: Przesunięcia typów mniej pojemnych, które będą rozszerzane do int - do 32 bitów, np. 8-bitowy byte rozszerzany jest do 32 bitowego int, więc przesunięcie >>> może nie mieć żadnego wpływu i należy maskować liczbę przed przesunięciem, np. (b & 0xFF) >>> 2.
Przesunięcie w prawo zawsze skutkuje "wypadaniem" liczb poza koniec (jakby wpadały w przepaść i były tracone na zawsze).
W The SCJP Tip Line Bit Shifting by Corey McGlone trafiłem na ciekawą zagadkę, która wynika bezpośrednio z powyższych reguł przesunięcia liczb całkowitych (szczególnie maskowaniem prawego operandu).
Zagadka: Jaki będzie wynik 3 >>> 32?
Na odpowiedź masz jedynie sekundę :)
Pamiętasz maskowanie prawego operandu przed wykonaniem przesunięcia? Dla int będzie to maska 0x1F, czyli 32. Czy teraz łatwiej odpowiedzieć na powyższe pytanie? To jaki będzie wynik?
Wystarczy zastosować mod 32 i masz gotową odpowiedź.
3 >>> 32 = 3 >>> (32 % 32) = 3 >>> 0 = 3
Fajne, co?! Właśnie takie cuda w Javie i w ogóle w językach programowania nakręcają mnie na dalsze ich zgłębianie. Czego i Tobie życzę w Nowym Roku 2012! :)
31 grudzień 2011
17b 79 63 7a 65 6e 69 61 20 6e 6f 77 6f 72 6f 63 7a 6e 65
Właśnie dobiega końca 2011 rok i nadeszła pora na życzenia noworoczne. Ostatnio siedzę nad reprezentacją liczb całkowitych w Javie, więc nie inaczej mogło być i dzisiaj (w końcu to taka uroczysta pora, która wymaga specjalnego potraktowania :-))
1010011 1111010 1100011 1111010 100011001 101011011 1101100 1101001 1110111 1100101 1100111 1101111 100000 1001110 1101111 1110111 1100101 1100111 1101111 100000 1010010 1101111 1101011 1110101 100000 110010 110000 110001 110010 100000 101111100 1111001 1100011 1111010 1111001 100000 1001010 1100001 1100011 1100101 1101011 100000 1001100 1100001 1110011 1101011 1101111 1110111 1110011 1101011 1101001 100000 1111010 100000 1110010 1101111 1100100 1111010 1101001 1101110 100000101 101110Do odkodowania można skorzystać z poniższej aplikacji.
package pl.japila.java7;
import java.util.Scanner;
import javax.swing.JOptionPane;
public class ZyczeniaNoworoczne {
public static void main(String... args) {
String userInput = JOptionPane.showInputDialog(null,
"Wprowadź dane do odkodowania (zastosuj zasadę Copiego & Paste)");
StringBuilder zyczeniaNoworoczne = new StringBuilder();
Scanner scanner = new Scanner(userInput);
while (scanner.hasNext()) {
zyczeniaNoworoczne.append((char) Integer.parseInt(scanner.next(), 2));
}
JOptionPane.showMessageDialog(null, zyczeniaNoworoczne);
}
}p.s. Do odkodowania tytułu zastosuj podstawę 16 w linii 17.
30 grudzień 2011
O kodzie uzupełnień do dwóch w Javie raz jeszcze
W Kod uzupełnień do dwóch w Javie (reprezentacja binarna liczb całkowitych) zaprezentowałem moją dotychczasową wiedzę na temat reprezentacji binarnej liczb całkowitych w Javie. Uważam to za mój początek w dokładniejszym rozpoznaniu tematu i nie ukrywam, że wciągnął mnie. Przypomnę tylko, że zaczęło się od zmian w Javie 7 z Fork/Join (nowe podejście do współbieżności w Javie z konstrukcjami wyższego poziomu), aby przez operator przesunięcia w prawo bez znaku >>> przejść do kodu uzupełnień do dwóch dla liczb całkowitych w Javie. Właśnie takie przejścia z jednego tematu na drugi w krótkim czasie lubię najbardziej. Nie pozwalają człowiekowi na dłuższy bezruch.
Przez ostatni tydzień dalej zgłębiałem temat i przesiedziałem sporo czasu czytając różnej maści artykuły. O większości pisałem na swoim kanale @jaceklaskowski na twitterze, więc wielu już miało przedsmak tego, o czym teraz będę pisał.
Prawie.
I już przy omawianiu dostępnych typów dostrzec można ich różną reprezentację wewnętrzną - byte, short, int i long są z bitem znaku, w przeciwieństwie do char, któremu dano wszystkie dostępne bity do dyspozycji.
"Two's complement numbers is a way to encode negative numbers into ordinary binary, such that addition still works."
Tylko o jakie dodawanie chodzi?!
Właśnie o zwykłe dodawanie binarne się rozchodzi. Jak mogłem się zorientować przeszukując materiały w Sieci, istnieje wiele systemów reprezentowania liczb całkowitych, ale czy to podwójne zero, czy konieczność rozróżniania znaku dodawanych liczb, sprawiają, że kod uzupełnienia do dwóch wydaje się być najbardziej trafnym. I taki zastosowano w Javie.
W Signed Int: Two's Complement mogłem dalej zgłębiać niuanse kodu uzupełnień do dwóch, który od tej pory będę zapisywał jako 2C (od angielskiego two's complement). Tam dowiedziałem się, że w 2C występuje jedno zero i dodawanie jest spójne dla reprezentacji bitowej z i bez znaku korzystając ze sprzętowej realizacji dodawania bitów (bez względu, czy reprezentują liczbę ze znakiem, czy bez - obie reprezentacje sprowadzane są do reprezentacji bez znaku). Ta cecha 2C jest związana z działaniem sprzętowym dodawania, a tutaj moja wiedza kończy się niezwykle szybko i na tym poprzestanę. I czuję, że więcej nie jest mi potrzebne o maszynowych rozwiązaniach.
Zadanie dla dociekliwych: wykonaj bitowe dodawanie liczb całkowitych, np. 1 i 2.
Najdłuższa liczba całkowita - typu long - ma do dyspozycji 64 bity. Pierwszy bit zarezerwowany jest dla bitu znaku (poza char).
Do uzyskania liczby ujemnej w 2C mamy 3 różne sposoby, z których najczęściej brany jest ten, który polega na odwróceniu wszystkich bitów i dodaniu jedynki, tj. -B = ~B + 1, przy założeniu, że B to dowolna liczba całkowita.
Zadanie dla dociekliwych: znajdź liczbę przeciwną do 1 korzystając z powyższego algorytmu.
I właśnie w tym momencie dociera do mnie jak interesującym jest rozpoznawanie tematu reprezentacji 2C. Dodaj 1 do liczby, której reprezentacja bitowa zawiera wyłącznie 1ki (czyli -1).
Idąc dalej, możnaby zastanowić się, co stanie się przy wyznaczaniu liczby przeciwnej dwukrotnie? Czy zachodzi zasada wyznaczania liczby przeciwnej podwójnie, która powinna wyznaczyć liczbę początkową, czyli -(-x) = x, w 2C?
Krok 1. Reprezentacja liczby całkowitej w postaci 32 bitów (dla int) lub 64 bitów (dla long). Ja pozostanę przy 32 bitach.
int n0 = 1111 1111 1111 1111 1111 1111 1111 1111 // -1
Krok 2. Odwracamy wszystkie bity
int n1 = 0000 0000 0000 0000 0000 0000 0000 0000 // 0
Krok 3. Dodajemy jedynkę
int n2 = 0000 0000 0000 0000 0000 0000 0000 0001 // 1
Zakończyłem pierwsze wyliczenie liczby przeciwnej do zadanej, czyli -1. Czy kontynuując odwracanie wyliczę wyjściową, czyli -1?
Krok 4 Reprezentacja bitowa liczby 1
int n00 = 0000 0000 0000 0000 0000 0000 0000 0001 // 1
Krok 5 Odwrócenie bitów
int n10 = 1111 1111 1111 1111 1111 1111 1111 1110 // nieistotne
Krok 6 Dodajemy jedynkę
int n20 = 1111 1111 1111 1111 1111 1111 1111 1111 // -1
I jak łatwo zauważyć n20 == n0, czyli parzyste wykonanie wyznaczania liczby odwrotnej do zadanej zawsze zwróci liczbę początkową.
Z Why computers represent signed integers using two’s complement tylko upewniłem się, że 2C jest warte poświęconego czasu i jego zrozumienie uważam od tej pory za obowiązkowe (ja już mam za sobą, więc tym łatwiej jest mi rzucać takie stwierdzenia :)).
"The representation of signed integers is the representation used by modern processors. It is called "two's complement" because to negate an integer, you subtract it from 2N. For example, to get the representation of –2 in 3-bit arithmetic, you can compute 8 – 2 = 6, and so –2 is represented in two’s complement as 6 in binary: 110."
W tym zdaniu znajduje się kolejny sposób na wyznaczanie liczb przeciwnych w 2C. Po prostu odejmujemy liczbę dodanią od 2^N, czyli dla 32 bitowych liczb typu int będzie to 1 + 32 zera w binarnej reprezentacji (wyznaczenie, a co ważniejsze, zapamiętanie tej liczby stanowi nie lada wyzwanie umysłowe, więc pozostańmy przy takim opisie).
Z Kod uzupełnień do dwóch w Javie (reprezentacja binarna liczb całkowitych) wiemy, że mnożenie
Przez ostatni tydzień dalej zgłębiałem temat i przesiedziałem sporo czasu czytając różnej maści artykuły. O większości pisałem na swoim kanale @jaceklaskowski na twitterze, więc wielu już miało przedsmak tego, o czym teraz będę pisał.
Prawie.
Liczby całkowite w Javie
Specyfikacja The Java Language Specification, Third Edition w rozdziale 4.2.1 Integral Types and Values wymienia typy całkowite z ich zakresami. W kolejności ich długości wyróżniamy: byte na 8 bitach, short na 16 bitach, int na 32 bitach i najdłuższy long na 64 bitach. Jest jeszcze całkowite char, które reprezentowane jest na 16 bitach, z tą różnicą, w porównaniu do poprzednich, że bez bitu znaku (najstarszy bit, pierwszy od lewej strony, albo ostatni z prawej).I już przy omawianiu dostępnych typów dostrzec można ich różną reprezentację wewnętrzną - byte, short, int i long są z bitem znaku, w przeciwieństwie do char, któremu dano wszystkie dostępne bity do dyspozycji.
Dodawanie i liczba przeciwna w kodzie uzupełnień do dwóch
W artykule na Wikipedii Two's complement trafiłem na zdanie, które wywarło na mnie niesamowite wrażenie i sprawiło, że zrozumiałem sens istnienia tego systemu kodowania. Uważam, że mogłoby stanowić świetne wprowadzenie dla całego artykułu, albo jedyne:"Two's complement numbers is a way to encode negative numbers into ordinary binary, such that addition still works."
Tylko o jakie dodawanie chodzi?!
Właśnie o zwykłe dodawanie binarne się rozchodzi. Jak mogłem się zorientować przeszukując materiały w Sieci, istnieje wiele systemów reprezentowania liczb całkowitych, ale czy to podwójne zero, czy konieczność rozróżniania znaku dodawanych liczb, sprawiają, że kod uzupełnienia do dwóch wydaje się być najbardziej trafnym. I taki zastosowano w Javie.
W Signed Int: Two's Complement mogłem dalej zgłębiać niuanse kodu uzupełnień do dwóch, który od tej pory będę zapisywał jako 2C (od angielskiego two's complement). Tam dowiedziałem się, że w 2C występuje jedno zero i dodawanie jest spójne dla reprezentacji bitowej z i bez znaku korzystając ze sprzętowej realizacji dodawania bitów (bez względu, czy reprezentują liczbę ze znakiem, czy bez - obie reprezentacje sprowadzane są do reprezentacji bez znaku). Ta cecha 2C jest związana z działaniem sprzętowym dodawania, a tutaj moja wiedza kończy się niezwykle szybko i na tym poprzestanę. I czuję, że więcej nie jest mi potrzebne o maszynowych rozwiązaniach.
Zadanie dla dociekliwych: wykonaj bitowe dodawanie liczb całkowitych, np. 1 i 2.
Najdłuższa liczba całkowita - typu long - ma do dyspozycji 64 bity. Pierwszy bit zarezerwowany jest dla bitu znaku (poza char).
Do uzyskania liczby ujemnej w 2C mamy 3 różne sposoby, z których najczęściej brany jest ten, który polega na odwróceniu wszystkich bitów i dodaniu jedynki, tj. -B = ~B + 1, przy założeniu, że B to dowolna liczba całkowita.
Zadanie dla dociekliwych: znajdź liczbę przeciwną do 1 korzystając z powyższego algorytmu.
I właśnie w tym momencie dociera do mnie jak interesującym jest rozpoznawanie tematu reprezentacji 2C. Dodaj 1 do liczby, której reprezentacja bitowa zawiera wyłącznie 1ki (czyli -1).
1111 1111 1111 1111 1111 1111 1111 1111 // -1 + 0000 0000 0000 0000 0000 0000 0000 0001 // 1 ------------------------------------------------------------------- 10000 0000 0000 0000 0000 0000 0000 0000 // 0 (na 33 bitach = przepełnienie!)Obie liczby są typu int. Obie mają do dyspozycji 32 bity z ostatnim bitem (licząc od lewej) zarezerwowanym na znak. Wynik również musi mieścić się w 32 bitach, ale cóż to?! Dodawanie 1 i -1 kończy się przepełnieniem - wynik wymusza 33 bity. W Javie taka sytuacja jest ukrywana przez usunięcie dodatkowego 33 bitu, aby w ten sposób otrzymać liczbę 32-bitową, która składa się wyłącznie z samych 0, a to po prostu 0 w systemie dziesiętnym. Jakież to piękne!
Idąc dalej, możnaby zastanowić się, co stanie się przy wyznaczaniu liczby przeciwnej dwukrotnie? Czy zachodzi zasada wyznaczania liczby przeciwnej podwójnie, która powinna wyznaczyć liczbę początkową, czyli -(-x) = x, w 2C?
Krok 1. Reprezentacja liczby całkowitej w postaci 32 bitów (dla int) lub 64 bitów (dla long). Ja pozostanę przy 32 bitach.
int n0 = 1111 1111 1111 1111 1111 1111 1111 1111 // -1
Krok 2. Odwracamy wszystkie bity
int n1 = 0000 0000 0000 0000 0000 0000 0000 0000 // 0
Krok 3. Dodajemy jedynkę
int n2 = 0000 0000 0000 0000 0000 0000 0000 0001 // 1
Zakończyłem pierwsze wyliczenie liczby przeciwnej do zadanej, czyli -1. Czy kontynuując odwracanie wyliczę wyjściową, czyli -1?
Krok 4 Reprezentacja bitowa liczby 1
int n00 = 0000 0000 0000 0000 0000 0000 0000 0001 // 1
Krok 5 Odwrócenie bitów
int n10 = 1111 1111 1111 1111 1111 1111 1111 1110 // nieistotne
Krok 6 Dodajemy jedynkę
int n20 = 1111 1111 1111 1111 1111 1111 1111 1111 // -1
I jak łatwo zauważyć n20 == n0, czyli parzyste wykonanie wyznaczania liczby odwrotnej do zadanej zawsze zwróci liczbę początkową.
Z Why computers represent signed integers using two’s complement tylko upewniłem się, że 2C jest warte poświęconego czasu i jego zrozumienie uważam od tej pory za obowiązkowe (ja już mam za sobą, więc tym łatwiej jest mi rzucać takie stwierdzenia :)).
"The representation of signed integers is the representation used by modern processors. It is called "two's complement" because to negate an integer, you subtract it from 2N. For example, to get the representation of –2 in 3-bit arithmetic, you can compute 8 – 2 = 6, and so –2 is represented in two’s complement as 6 in binary: 110."
W tym zdaniu znajduje się kolejny sposób na wyznaczanie liczb przeciwnych w 2C. Po prostu odejmujemy liczbę dodanią od 2^N, czyli dla 32 bitowych liczb typu int będzie to 1 + 32 zera w binarnej reprezentacji (wyznaczenie, a co ważniejsze, zapamiętanie tej liczby stanowi nie lada wyzwanie umysłowe, więc pozostańmy przy takim opisie).
Z Kod uzupełnień do dwóch w Javie (reprezentacja binarna liczb całkowitych) wiemy, że mnożenie
package pl.japila.java7;
import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.assertThat;
import org.junit.Test;
public class TwoCDemo {
@Test
public void test() {
long oneAnd32Zeros = (long)1 << 32; // 0x1_FFFF_FFFF - int overflow!
int three = 3; // 0b11
int minusThree = (int)(oneAnd32Zeros - three);
assertThat(minusThree, is(-3));
}
}
Jako podsumowanie, warto zwrócić uwagę na użycie operatora przesunięcia w lewo, aby uzyskać liczbę podwójnie większą od największej w zakresie int. Nie chciałem pisać tej liczby dziesiętnie, a (czego nie wiedziałem wcześniej) jej reprezentacja w notacji bitowej (z 0b), ósemkowej (z wiodącym 0), albo szesnastkowo (z 0x) nie jest możliwa - są one zarezerwowane wyłącznie dla typów int i mniejszych.23 grudzień 2011
Kod uzupełnień do dwóch w Javie (reprezentacja binarna liczb całkowitych)
Wszystko zaczęło się od mojego przedstawienia zmian w Javie 7, w pakiecie java.util.concurrent podczas 84 spotkania Warszawa JUG - Warszawski Eclipse DemoCamp 2011 - Java 7, JavaFX i Eclipse (prezentacja do pobrania jako JacekLaskowski-EclipseDemoCamp2011-ConcurrencyUtilitiesJava7-2011.11.08.pdf).
Wtedy zaczęła się moja przygoda ze szkieletem Fork/Join. Rozwiązywanie problemu przez zrównoleglanie jego mniejszych składowych wymaga właściwego sposobu podziału (zwykle po połowie) i tak do ustalonego, minimalnego poziomu jego złożoności, a właściwie braku, po którym rozwiązanie można obliczyć "siłowo" (element po elemencie, liniowo).
Kwestią, z którym zwykle zmagają się programiści korzystający z Fork/Join (czy dowolnego problemu rozwiązywanego przez algorytmy typu "dziel i zwycieżaj") to, w jaki sposób dzielić, aby samo dzielenie nie było na tyle skomplikowane, że zysk ze zrównoleglenia zostanie przez niego skonsumowany i ostatecznie wyjdziemy na przysłowiowe "zero".
I tu pojawia się przyczynek do tego wpisu - operator przesunięcia bez znaku w prawo >>> (ang. unsigned right shift) w Javie.
Nie jest to niczym odkrywczym w Javie 7, ale przy Fork/Join nabrał większego znaczenia. Mówiąc wprost, ja na niego zwróciłem uwagę właśnie przy Fork/Join. I tak kończy się w zasadzie rola Fork/Join, które nie będzie już przywoływane, bo posłużył wyłącznie jako tło do rozpoznania operatora przesunięcia i jak się później okazało reprezentacji liczb całkowitych w Javie.
Weźmy następujący problem: W jaki sposób wyznaczyć połowę pewnej liczby nieujemnej x?
Liczba dowolna, acz ustalona, x (teraz dopiero dojrzałem, aby dostrzec piękno tych słów) może być liczbą elementów w tablicy, w którym znajdują się elementy do przetworzenia.
Operator przesunięcia w prawo bez znaku >>> jest złożeniem << i >> w zależności od znaku lewego argumentu - dodatni to >>, a ujemny...cóż...tu sprawa się komplikuje i wygląda (n>>s)+(2<<~s) przy założeniu, że rozważamy n>>>s.
Pamiętam, kiedy dostrzegłem (a właściwie pokazano mi palcem), że n << 1 to po prostu n * 2. Innych zastosowań przesunięcia w lewo jeszcze nie odkryłem, ale pewnie są równie zabójcze dla mojego serca :)
Wtedy zacząłem zgłębiać reprezentację liczb całkowitych w Javie, bo w końcu działanie tych operatorów polega na przesunięciach binarnych.
Zadanie wprowadzające: Czy znasz zapis binarny ujemnej liczby całkowitej w Javie? Niech to będzie -1 lub Integer.MIN_VALUE.
Właśnie wtedy zreflektowałem się, jak niewiele wiem na ten temat. Niewiele?! Delikatnie powiedziane. Nic nie wiem! Zabrałem się za lekturę specyfikacji języka Java (tutaj niewiele znalazłem poza ogólnikami), aby skończyć na pojęciach reprezentacjach liczb ze znakiem i bez oraz kod uzupełnień do dwóch (ang. two's complement).
I tak od rozpoznawania Fork/Join przeszedłem do operatora przesunięcia, aby skończyć na reprezentacji liczb całkowitych w Javie.
W ten sposób powstała moja implementacja zamiany binarnego ciągu znaków (bez wiodącego 0b, które doszło w Javie 7) do postaci liczby całkowitej w zapisie dziesiętnym. Klasa nie jest krótka, ale starałem się dobierać nazwy do ich przeznaczenia, więc sądzę, że stosunkowo łatwo będzie zorientować się, co miałem na myśli.
Przede mną analiza kodów źródłowych java.lang.Integer, która dostarcza większości z poniższych metod. Niedługo więcej w temacie, bo nie czuję, abym go wyczerpał (a mam wrażenie, że jedynie zdrapałem wierzchnią warstwę). Oczekuję uwag i wskazówek od życzliwego czytelnika (w czasie świąt niegodnym nie podzielić się miłym słówkiem).
Gdybyśmy już się nie widzieli, życzę najlepszego z okazji nadchodzących Świąt Bożego Narodzenia. Baw się i świętuj, aby wypoczęty wrócić do dalszych prac poznawczych.
Wtedy zaczęła się moja przygoda ze szkieletem Fork/Join. Rozwiązywanie problemu przez zrównoleglanie jego mniejszych składowych wymaga właściwego sposobu podziału (zwykle po połowie) i tak do ustalonego, minimalnego poziomu jego złożoności, a właściwie braku, po którym rozwiązanie można obliczyć "siłowo" (element po elemencie, liniowo).
Kwestią, z którym zwykle zmagają się programiści korzystający z Fork/Join (czy dowolnego problemu rozwiązywanego przez algorytmy typu "dziel i zwycieżaj") to, w jaki sposób dzielić, aby samo dzielenie nie było na tyle skomplikowane, że zysk ze zrównoleglenia zostanie przez niego skonsumowany i ostatecznie wyjdziemy na przysłowiowe "zero".
I tu pojawia się przyczynek do tego wpisu - operator przesunięcia bez znaku w prawo >>> (ang. unsigned right shift) w Javie.
Nie jest to niczym odkrywczym w Javie 7, ale przy Fork/Join nabrał większego znaczenia. Mówiąc wprost, ja na niego zwróciłem uwagę właśnie przy Fork/Join. I tak kończy się w zasadzie rola Fork/Join, które nie będzie już przywoływane, bo posłużył wyłącznie jako tło do rozpoznania operatora przesunięcia i jak się później okazało reprezentacji liczb całkowitych w Javie.
Weźmy następujący problem: W jaki sposób wyznaczyć połowę pewnej liczby nieujemnej x?
Liczba dowolna, acz ustalona, x (teraz dopiero dojrzałem, aby dostrzec piękno tych słów) może być liczbą elementów w tablicy, w którym znajdują się elementy do przetworzenia.
Operator przesunięcia w prawo bez znaku >>> jest złożeniem << i >> w zależności od znaku lewego argumentu - dodatni to >>, a ujemny...cóż...tu sprawa się komplikuje i wygląda (n>>s)+(2<<~s) przy założeniu, że rozważamy n>>>s.
Pamiętam, kiedy dostrzegłem (a właściwie pokazano mi palcem), że n << 1 to po prostu n * 2. Innych zastosowań przesunięcia w lewo jeszcze nie odkryłem, ale pewnie są równie zabójcze dla mojego serca :)
Wtedy zacząłem zgłębiać reprezentację liczb całkowitych w Javie, bo w końcu działanie tych operatorów polega na przesunięciach binarnych.
Zadanie wprowadzające: Czy znasz zapis binarny ujemnej liczby całkowitej w Javie? Niech to będzie -1 lub Integer.MIN_VALUE.
Właśnie wtedy zreflektowałem się, jak niewiele wiem na ten temat. Niewiele?! Delikatnie powiedziane. Nic nie wiem! Zabrałem się za lekturę specyfikacji języka Java (tutaj niewiele znalazłem poza ogólnikami), aby skończyć na pojęciach reprezentacjach liczb ze znakiem i bez oraz kod uzupełnień do dwóch (ang. two's complement).
I tak od rozpoznawania Fork/Join przeszedłem do operatora przesunięcia, aby skończyć na reprezentacji liczb całkowitych w Javie.
W ten sposób powstała moja implementacja zamiany binarnego ciągu znaków (bez wiodącego 0b, które doszło w Javie 7) do postaci liczby całkowitej w zapisie dziesiętnym. Klasa nie jest krótka, ale starałem się dobierać nazwy do ich przeznaczenia, więc sądzę, że stosunkowo łatwo będzie zorientować się, co miałem na myśli.
Przede mną analiza kodów źródłowych java.lang.Integer, która dostarcza większości z poniższych metod. Niedługo więcej w temacie, bo nie czuję, abym go wyczerpał (a mam wrażenie, że jedynie zdrapałem wierzchnią warstwę). Oczekuję uwag i wskazówek od życzliwego czytelnika (w czasie świąt niegodnym nie podzielić się miłym słówkiem).
Gdybyśmy już się nie widzieli, życzę najlepszego z okazji nadchodzących Świąt Bożego Narodzenia. Baw się i świętuj, aby wypoczęty wrócić do dalszych prac poznawczych.
package pl.japila.java7;
public class BinaryToDecimalIntDemo {
static final char ZERO = '0';
static final char ONE = '1';
public static void main(String[] args) {
for (int number = Integer.MIN_VALUE; number <= Integer.MIN_VALUE + 0xFFFF; number++) {
String negativeNumber = Integer.toBinaryString(number);
int intInDecimal = BinaryToDecimalIntDemo.getIntInDecimal(negativeNumber);
assert number == intInDecimal;
}
for (int number = Integer.MAX_VALUE; number >= Integer.MAX_VALUE - 0xFFFF; number--) {
String negativeNumber = Integer.toBinaryString(number);
int intInDecimal = BinaryToDecimalIntDemo.getIntInDecimal(negativeNumber);
assert number == intInDecimal;
}
}
static int getIntInDecimal(String binary) {
int sum = 0;
boolean negative = false;
char[] bits = binary.toCharArray();
if (bits.length == Integer.SIZE) {
if (isNegative(bits)) {
negative = true;
bits = subtractOne(invertBits(removeSignBit(bits)));
}
}
for (int i = bits.length - 1, j = 0; i >= 0; i--, j++) {
sum += calculateValueInBinaryRepAt(j, bits[i]);
}
return negative ? (sum == 0 ? Integer.MIN_VALUE : -sum) : sum;
}
private static char[] subtractOne(final char[] bits) {
char[] newBits = new char[bits.length];
System.arraycopy(bits, 0, newBits, 0, newBits.length);
int i = newBits.length - 1;
if (newBits[i] == ONE) {
newBits[i] = ZERO;
} else {
newBits[i] = ONE;
for (int j = i - 1; j >= 0; j--) {
if (newBits[j] == ZERO) {
newBits[j] = ONE;
} else {
newBits[j] = ZERO;
break;
}
}
}
return newBits;
}
private static char[] invertBits(char[] bits) {
char[] newBits = new char[bits.length];
System.arraycopy(bits, 0, newBits, 0, newBits.length);
for (int i = 0; i < newBits.length; i++) {
newBits[i] = (newBits[i] == ZERO ? ONE : ZERO);
}
return newBits;
}
private static char[] removeSignBit(char[] bits) {
char[] newBits = new char[bits.length - 1];
System.arraycopy(bits, 1, newBits, 0, newBits.length);
return newBits;
}
private static boolean isNegative(char[] bits) {
return bits.length == Integer.SIZE && bits[0] == ONE;
}
private static double calculateValueInBinaryRepAt(int i, char c) {
return Math.pow(2, i) * Character.getNumericValue(c);
}
}
Subskrybuj:
Posty (Atom)
