Wyszukanie przerwy binarnej w liczbie n

W artykule zajmiemy się przykładowym zadaniem związanym z analizą wartości binarnej liczby „n”. Jest to przykładowe zadanie z jednego z kursów online, a do napisania tego artykułu skłonił mnie ciekawy wpis na blogu adamczuk.net.pl.

Autor tego bloga na jednym ze swoich wpisów podaje następujący opis zadania:

„Zadanie wymaga napisania funkcji, która dla dodatniej liczby N zwróci długość jej najdłuższej przerwy binarnej, czyli ciągu zer pomiędzy jedynkami. Funkcja powinna zwracać 0, jeśli N nie posiada binarnej przerwy. Przykładowo, dla liczby N = 9, zapisanej binarnie 1001 przerwa wynosi 2. Liczba 20 zapisana binarnie to 10100, a jej przerwa 1. Zakładamy także, że N jest liczbą całkowitą z zakresu [1..2147483647].”

Autor zaprezentował na swoim blogu rozwiązanie tego problemu metodą tradycyjną, m.in. z wykorzystaniem pętli for. Ja chciałbym przeanalizować nieco inne podejście, które ciekawie łączy w sobie kilka elementów jak operacje tablicowe, użycie obiektu Math, wyrażenia regularne oraz sposób zapisu funkcji z wykorzystaniem składki ECMA Script 6.

Na początku przedstawię moją propozycję rozwiązania powyższego problemu, a następnie omówimy sobie krok po kroku poszczególne elementy tej funkcji:

const zeros = (n) => Math.max(...(((n).toString(2).match(/0+(?=1)/g)||[”]).map(v => v.length)))

Zacznijmy od konwersji liczby n na postać binarną

Bardzo często słyszę opinie, że wszystkie liczby z JavaScript są obiektami, a ich metoda toString() umożliwia konwersję do różnych systemów liczbowych, np. toString(2) do zamiany liczby dziesiętnej n na liczbę w systemie dwójkowym.

Nie do końca jednak zgadzam się z takimi stwierdzeniami. Po pierwsze w JavaScript nie wszystko jest obiektem – są również tzw. typy proste, do których należy m.in. typ numeryczny. Spójrzmy na poniższy kod:

var a = 5,
    b = Number(5);

typeof a; //'number'
typeof b; //'number'

a.toString(2); //'101'
b.toString(2); //'101'

Teoretycznie mogłoby się, że zarówno a jak i b to pełnoprawne obiekty, zawierające metodę toString odziedziczoną prototypowo po obiekcie Object. W praktyce jednak wygląda to nieco inaczej. Zmienna a jest zmienną o wartości typu prostego i dopiero w momencie wywołania na niej metody toString(2) zostaje ona chwilowo przekonwertowana na obiekt, po czym ponownie „wraca” do zmiennej typu prostego. W przypadku zmiennej b od początku jest ona obiektem, przez co przez cały czas swojego istnienia zabiera nieco więcej zasobów. W zastosowaniach praktycznych nie ma to znaczenia i zarówno a jak i b można traktować jak zmienne typu numerycznego, na których można wywoływać metody obiektu Number i odziedziczone prototypowo. Warto jednak wiedzieć o pewnych niuansach specyficznych dla języka JavaScript związanych z dynamicznym tworzeniem obiektów z typów prostych.

No dobrze, ale powróćmy zatem do metody toString(). pobiera ona jeden parametr, który określa podstawę systemu liczbowego w jakim ma zostać zaprezentowana liczba. Czasami znajduję informacje (nawet w książkach), że wywołanie (5).toString() powoduje konwersję liczby do typu string.

Jest to duże uproszczenie tego do czego na prawdę służy metoda toString. Otóż w pewnym uproszczeniu wykonuje ona dwa zadania. Najpierw pobiera zmienną typu liczbowego n i podstawę nowego systemu liczbowego, a następnie konwertuje tę liczbę do zadanego systemu. Na koniec uzyskany wynik zwraca w postaci ciągu znakowego.

Metoda toString() nie może zwracać nam przekonwertowanej liczby w inny sposób niż jako typ string, gdyż prowadziłoby to do wielu błędów w interpretacji uzyskanych wyników. Spójrzmy na przykład na liczbę 999 i jej konwersję do systemu szesnastkowego:

var n = 999;
n.toString(16); //'3e7'
n = n.toString(16); //'3e7';

n = 3e7; //Zauważ brak apostrofów!
n; //30000000 ups...

Zmiennej n przypisaliśmy jej reprezentację znakową odpowidającą zapisowi szesnastkowego, czyli „3e7”. Jeśli jednak zmiennej n przypiszemy tę samą wartość (3e7) bez cudzysłowu to stworzymy zmienną typu numerycznego, ale uwaga… wykorzystując w tym celu zapis w notacji naukowej, gdzie 3e7 oznacza 3 x 10^7 co w konsekwencji daje liczbę „nieco” odmienną od 999. Pamiętajmy zatem, że metoda toString() nie tyle konwertuje liczbę do innego systemu lecz zwraca znakową reprezentację tej liczby w określonym systemie numerycznym.

To teraz zajmijmy się omówieniem problemu

No dobrze, wiemy już zatem jak uzyskać reprezentację liczby n w systemie binarnym. Spróbujmy zatem powrócić do początku artykułu gdzie omówiłem założenia do zadania i przeanalizujmy poniższy fragment kodu:

(5).toString(2); '101'
(1025).toString(2); '10000000001'
(3997).toString(2); '111110011101'

Interesuje nas najdłuższa przerwa binarna, czyli największa ilość powtarzających się zer ograniczonych z obu stron jedynką. Dla liczby 5 jest to „1”, dla 1025 będzie to „9”, a dla liczby 3997 wynikiem będzie „2”.

Drugi etap – wyrażenie regularne

Mamy już znakową reprezentację binarnego zapisu liczby n, więc kolejnym krokiem będzie wyszczególnienie z tego ciągu zer, które ograniczone są z obu stron jedynkami. Użyjemy do tego prostego wyrażenia regularnego i metody match():

(n.toString(2).match(/0+(?=1)/g)) || []

W wyrażeniu regularnym poszukujemy cyfry zero co najmniej jeden raz (o czym mówi kwantyfikator „+”), po której występuje pojedyncza cyfra jeden. Ciąg przeszukujemy globalnie (flaga „g”). Bez tej flagi w przypadku liczby 3997 przeszukiwanie skończyłoby się na znalezieniu dwóch pierwszych zer. My potrzebujemy znaleźć RegExp wszystkie zera spełniające warunki brzegowe, a dopiero później będziemy analizować ich ilość.

Dla liczby 3997 podane wyrażenie zwróci tablicę [’00’, ‚0’]. Niektórzy mogą w tym momencie zapytać dlaczego nie rozpoczynamy przeszukania od jedynki? Otóż z dwóch powodów. Po pierwsze gdy wyrażenie dopiero zaczyna analizować ciąg to i tak zawsze napotka na cyfrę jeden. Wynika to z tego, że w JavaScript n.toString(2) zwróci ciąg pomijający wszystkie początkowe zera, a więc możliwie najkrótszą reprezentację binarną liczby. Mamy więc pewność, że zawsze zaczniemy od jedynki. Pierwsze wyszukanie w liczbie 3997 kończy się na jedynce umiejscowionej tuż za drugim zerem (licząc od lewej strony ciągu). Jedynka ta nie jest jednak zwracana jako wynik dopasowania, więc w kolejnym kroku wyszukiwanie rozpocznie się właśnie od niej, więc ponownie mamy pewność, że na początku będzie wartość „1”.

Należy jeszcze pamiętać o pewnym niuansie. Otóż metoda match zwraca tablicę dopasowań lub null, jeśli nie znajdzie żadnego dopasowania do podanego wzorca RegExp. Jeśli w dalszych krokach planujemy stosować metody tablicowe (ja u nas) to należy się zabezpieczyć i dla wartości null zastosować jako alternatywę pustą tablicę [”]. Jest to możliwe, gdyż w JavaScript null zostanie niejawnie przekonwertowane na false i zostanie zwrócona wartość z prawej strony operatora alternatywy „||”. Należy zastosować w tym wypadku tablicę z jednym elementem ” (czyli pusty ciąg znakowy), dla którego w dalszej części kodu uzyskamy długość tego elementu równą zero.

Metoda tablicowa map()

Kolejny krok to przetworzenie naszej tablicy zawierającej dopasowane zera na elementy reprezentujące długości tych dopasowań, czyli de facto ilość znalezionych zer, zawartych między jedynkami.

w tym celu posłużymy się metodą Array.prototype.map. Pobiera ona jeden lub dwa parametry i zwraca tablicę przetworzoną przez funkcję zwrotną calback. W naszym wypadku zadaniem funkcji zwrotnej jest pobranie wartości elementu tablicy (v) i zwrócenie w jego miejsce długości tego elementu (v.length).

Zastosowaliśmy tutaj zapis w formie Arrow Function z ECMA Script 6:

((n).toString(2).match(/0+(?=1)/g)||[”]).map(v => v.length)

Sposób działania Arrow Function omówimy w oddzielnym artykule, więc na razie (w pewnym uproszczeniu) przyjmij, że pobiera ona po prostu jako parametr wartość v i zwraca v.length.

Do tego typu iterowania po tablicach istnieje jeszcze druga metoda o nazwie forEach. Pobiera ona takie same dwa parametry (drugi opcjonalny). Istnieje jednak między nimi istotna różnica: tylko metoda map zwraca przetworzoną tablicę, którą możemy wykorzystać w dalszych krokach.

I na koniec metoda Math.max()

Dotarliśmy już prawie do końca zmagań. Aby zwrócić największą liczbę wystąpień kolejnych zer możemy zastosować tradycyjną pętlę for lub metodę obiektu Math o nazwie max().

Jest jednak pewien szkopuł. Metoda max() oczekuje podania parametrów jako wartości numeryczne lub takie, które można niejawnie przekonwertować do typu number. Poprawne jest zatem wywołanie Math.max(1,2,3) i Math(‚1’, ‚2’, ‚3’), choć osobiście zalecam unikanie drugiego zapisu z przekazywaniem wartości typu string chyba, że mamy stuprocentową pewność, że zostaną one w oczekiwany przez nas sposób przekonwertowane do typu liczbowego.

Błędnym zapisem będzie jednak Math.max([1,2,3]) czyli przekazanie jako parametru wartości tablicowej.

Problem ten można rozwiązać na dwa sposoby. Metoda „tradycyjna” stosowana przed wprowadzeniem standardu ECMA Script 6 polegała na użyciu metody apply (dziedziczonej po Function.prototype) w następujący sposób:

Math.max.apply([1,2,3,4]); //4

Jest to rozwiązanie poprawne, ale ES6 udostępnia nam krótszą formę, stosującą tzw. operator rozproszenia:

Math.max(...[1,2,3,4]); //4

Operatort „…” powoduje w tym wypadku rozdzielenie kolejnych wartości tablicy [1,2,3,4] na pojedyncze wartości typu number (1,2,3,4) i przekazanie ich jako parametrów do funkcji Math.max(). Co ciekawe operator „…” może działać także w drugą stronę, czyli pojedyncze wartości „opakowywać” w tablicę, ale to omówimy kiedy indziej.

Uzyskaliśmy więc gotową funkcję realizującą zadany problem z wykorzystaniem kilku obiektów globalnych, wyrażeń regularnych i nowych zapisów ECMA Script 6. Jeśli nie masz dużego doświadczenia ze standardem ES6 to polecam Ci jako „zadanie domowe” rozpracowanie mojej funkcji i przerobienie jej na zapis „standardowy” z function … (w razie problemów proszę o wpisy w komentarzach to wstawię rozwiązanie tego „zadania”).