Szybka konwersja dużych liczb dziesiętnych na binarne

Tomasz

2004-08-28 21:59:34
2004-08-28 21:59:34
9 komentarzy
4703 odsłony

Chciałbym przedstawić wam pewien sposób na spore przyspieszenie zamiany liczb dzisiętnych na binarne. Jest to metoda mojego (chyba;)) pomysłu, który wpadł mi do głowy podczas ręcznego ćwiczenia tych konwersji; z tego względu nadaje się on raczej tylko dla ludzi (nie ma sensu go implementować). Ok przechodze do rzeczy: sposób ten korzysta z pewnej własności logicznej operacji NOT. Załóżmy że mamy liczbę binarną

00100110b (38)

Po zamianie wszystkich bitów na przeciwne (NOT), otrzymujemy

11011001b (217)

Jak łatwo zauważyć, 217+38=255. Czyli suma dowolnej liczby naturalnej i jej odwrotności w jakimś stałym polu bitowym (ktorego maksymalna wartosc to 2^n-1, czyli np. 255, 511, gdzie n to ilosc pozycji w liczbie binarnej) zawsze będzie równa maksymalnej wartości; ten banalny wniosek można w fajny sposób wykorzystać podczas zamiany binarnej dużych liczb. Spróbujmy zamienić liczbę np. 998 na wartość binarną. Szukamy w tym celu liczby większej od 998, będącą potęgą 2; jest to oczywiście 1024. Potem odejmujemy 1 od tej liczby, czyli zostaje 1023. Teraz odejmujemy: 1023-998=25. Zamieniamy teraz wynik na binaria,

25=11001b.

Dopełniamy tą liczbę zerami, tak aby miała 10 pozycji:

0000011001b.

Następnie wynik ten traktujemy operacją NOT (negujemy wszystkie bity).

1111100110b. Dziesiętnie: 998.

Przypominam, że można to łatwo wykorzystać podczas zamiany ręcznej, nie ma co tego implementować na komputerze (wyłuskiwanie bitów metodą maskowania jest szybsze).

Dexarz
• 2008-08-23 15:29

ja znalazłem inny sposób :) .Wystarczy że naszą potęgę z 2 podzielimy na 2 i odejmujemy 1 ,W tym przypadku mamy liczbę 511 ( 1024/2-1) ,potem wystarczy jeszcze od tego odjąć wartość bezwzględna z liczby 511 - 998 i dodajemy do wszystkiego 1 .Wynik będzie taki sam jak 1023-998 ,ale działa dokładniej ...Napisze jeszcze raz :)

i=(2^10)/2-1 (511)
i-|(i-998)|+1=25=(2^10)-1-998 !!

O Mam rozwiązanie dla Xitami ...Ja twój problem rozwiązałem tak :

Najpierw obliczyłem odwrotna liczbę od 520 jak ty czyli wyszło mi 503 ,potem te liczbę znów dałem na odwrotność ,ale liczba 503 mieści sie z mniejszej potędze 2 ,wiec nie muszę odejmować od 1023 a od 511 ,co daje 8 ..Bitowo to tak wygląda :

1000001000b (520) Odwracamy bity i mamy :
0111110111b (503) teraz kasujemy zbędne zera na początku i mamy 111110111b
Znów odwracamy i mamy 000001000b (8) ,a teraz wystarczy dodać do tego 1 na początku (bo 520 jest większe od liczby w którym mieści się 503) i co mamy ?? 520 !!

Można też inaczej ..W twoim przypadku liczbą odwrotną od 503 jest 8 ,więc żeby sprawdzić poprawność można zrobić tak że dodajmy do potęgi 2 ,8 i mamy 520 :) tzn 503 mieści sie w 511 (512) więc 512 + 8 = 520 ,proste nie ?? Więc jak widzicie że macie liczbę nadal dużą ,to odw520 = 503 ,a odwr503 = 8 ,a więc 8 (1000b) + 512 (111111111b) = 520 (1|000001000b) ...

A więc jeszcze raz ...Mamy liczbę 520 ,której odwrotność (not) stanowi 503 ,ta liczba mieści się w mniejszej potędze 2 i potrzebuje tylko 9 bitów (na liczby do 511 włącznie , 10 bitów na 1023 ,a więc wykładnik stanowi jednocześnie liczbę jedynek ,aby mieć liczbę ,w której nasza liczba sie mieści ) , a więc jeśli odwrotnością 503 jest 8 ,to bitowo jest to 1000b ,tylko teraz jest problem ..otóż mamy tu tylko 4 miejsca ,a nie 9 ,wiec dopisujemy na początku reszte brakujących zer !! czyli 5( 9 w 512 ,4 mamy ,wiec jeszcze 5) i mamy liczbę 000001000b (8) ,dodajmy do tego na początku tyle jedynek ile 10 (liczby do 1023 włącznie) - 9 (liczby do 511 włącznie) =1 czyli teraz mamy 1000001000 czyli nasze 520 !!

Jasne ??

Format
• 2006-09-21 22:52

Przy liczbach małych, powiedzmy poniżej 10 000 nie ma problemu - metoda ułatwia sprawe, niestety przy większych problemem staje się znalezienie samej potęgi liczby 2. Na szczęście nikt nie zadaje prac pisemnych z takimi liczbami :)

Xitami
• 2006-06-19 19:07

;-) inny przykład:
Mam N=520, szukam 2^{x>N, otrzymuję 2}x==1024. (1024-1) ? 520 == 503. No to mi pomogłeś ;-)
Sposób ten wynika z własności kodu U2 (czyli uzupełnienia do dwu). Definicja: ?X == NOT(X) + 1.
Więc należało by dodać, że sposób jest szybki ale tylko wtedy gdy N jest tylko trochę mniejsze niż jakaś potęga dwójki.

A teraz uwaga do komentarza poniżej.

Czy warto zamiast x:=y div 8 pisać x:=y shr 3?
Ogólniej Y div (2^m) zamieniać na Y shr m
Dla liczb bez znaku jest to bez znaczenia.
Jeżeli wartość dzielnika jest stałą, znaną w czasie kompilacji, oraz jest całkowitą potęgą dwójki - kompilator (współczesny) dzielenie zastąpi przesuwaniem bitów. A źródło nie straci na czytelności.
To samo dotyczy operatora ?mod? (?%? w języku C), jeżeli po ?mod? występuje całkowita potęga dwójki, kompilator zastąpi to iloczynem logicznym, zamiast ?% m? otrzymamy ?AND (m-1).

Dla liczb ze znakiem, napiszemy ?Y div 8? i drżymy, że mnóstwo czasu stracimy z powodu najdłużej wykonywanej operacji, operacji dzielenia.
Wcale nie trzeba się bać. Kompilator wygeneruje kod, który przed ?shiftem? sprawdzi czy Y jest ujemne, jeżeli tak jest ?shiftnie? nie wartość Y, a wartość Y+1.
Reszta z dzielenia liczby ze znakiem obliczana jest poprzez dzielenie.

Wniosek: pisz div i mod, ale gdzie się da używaj liczb bez znaku!!!

ADuch
• 2005-09-07 16:45

MrStroop ta procka jest nieoptymalna =P
Mozna było zamiast "DIV 8" uzyc "shr 3" i zamiast "mod 8" dac "and 7"

MrStroop
• 2004-10-27 17:10

ha!! - obczjacie ta procedure. To procedura zamienia 0 lub 1 na dowolnym miejscu w dowolnej liczbie(wartosci) i wlasnie korzysta z wspanialej operacji NOT. Jak ktos to zakuma to jest niezly:

procedure Toxicate(Lodata:PByte;const MisterPoz:cardinal;const flag:TF);
const
alone:byte=1;
var
t_d:cardinal;
curr_flag:byte;
begin
t_d:=((MisterPoz-1) div 8);
if t_d>0 then inc(Lodata,t_d);
curr_flag:=LoData^ shr ((MisterPoz-1)mod 8)and 1;
if curr_flag xor flag =0 then LoData^{:=not((not (alone shl ((MisterPoz-1)mod 8))) xor LoData});
{procedura zamienia zera z jedynkami na dowolnym miejscu w wartosci liczbowej
gdy za flage podaje sie 0 to zamieni miejsca wskazane przez
MisterPoz jesli to miejsce jest zerem na 1
i tak samo gdy za flage podaje sie 1 to jesli na pozycji
MisterPoz jest 1 to zostanie ona zamieniona na 0
aha - i wartosc liczbowa do zmiany przekazuje sie w pierwszym parametrze LoData - ale to chyba wiecie}
end;
-ciekawa, nieprawdaz - wykorzystuje powyrzszy pomysl ale zostala juz napisana jakies 4 lata wczesniej//strasznie pokrecona - ale w tym tkwi piekno