Binarno mnozenje i deljenje???

[ Ramirez @ 19.08.2003. 11:28 ] @

Lepo objasniste BITOVE u C/C++ ali meni nije jasno kako se mnoze i dele binarni brojevi???

[ filmil @ 19.08.2003. 12:06 ] @

Binarni brojevi se množe i dele isto kao i bilo koji drugi. Ono što ljude „sprečava“ da to shvate jeste nesvakidašnji zapis binarnih brojeva. Ako se upitaš koje su bitne odlike algoritama za množenje i deljenje „na papiru“ i iste te algoritme primeniš na binarne brojeve, videćeš da je i ponašanje sasvim isto.

E sada, činjenica da su cifre binarnog broja samo nule i jedinice unose dodatnu strukturu u operacije koje se koriste za pravljenje struktura za brzo množenje brojeva (počev od rednih množača odn. delitelja, preko rednoparalelnih, paralelnih, asimetričnih itd.) ali ne znam da li je to ono te zanima.

Možda bi pomoglo da pitanje postaviš malo konkretnije.Na primer rekao si da ti nije jasno kako se binarni brojevi množe i dele. Dobro, ali gde tačno? Da li te zanima samo princip, ili te zanimaju algoritmi, ili te zanimaju strukture u digitalnoj logici koje množe brojeve (FPU)? Množenje binarnih brojeva u C++-u teško da može da prođe kao pitanje, jer jer te jezik implementacije ni u čemu ne vezuje, kao da si recimo rekao: kako se na engleskom pravi tablica množenja.

f

[ Ramirez @ 19.08.2003. 12:46 ] @

Radim funkcije za rachunske operacije sa velikim brojevima predstavljenim u obliku statichkih nizova (50 elemenata ili vishe). Svako polje niza nosi jednu cifru.

Sabiranje i oduzimanje ovakva dva broja je lako i zavrsheno... mnozenje sam pocheo i mislim da nije preterano teshko ali deljenje je matematichki nemoguce realizovati (bar ja tako mislim) na nivou odvojenih cifara....

Pa je ideja bila da se mnozenje i deljenje urade preko binarnih brojeva... Rekoshe mi da je to shiftovanje u levo i desno (ali sam ja malo skeptichan). Probao sam da mnozim binarne brojeve ali mi nije jasan princip...???

[ random @ 19.08.2003. 15:00 ] @

Možda bi želeo da pogledaš neku od dobro razvijenih biblioteka za takve stvari, kao što je GNU MP.

http://www.swox.com/gmp/

[ sallle @ 28.08.2003. 18:07 ] @

Shiftovanje za i mesta je kad mnozis sa 2^i. ako posmatras n-tu cifru bin broja, onda ce u dec sistemu imati vrednost 2^n, e ako mnozis sa 2 npr, svaku cifra postaje 2^(n+1), tj shiftovala se za jedno mesto.

malo sam konfuzno rekao konfuzno...

[ sallle @ 28.08.2003. 18:10 ] @

e da, e ako imas neki ruzan broj sa kojim treba da pomnozis, onda koristis pravilo komutativnosti a*(11dec)=a*2^3+a*2^1+a*2^0, znaci uzmes
binarno a, i posebno ga shiftujes za 3, za 2, i za nula, i saberes ta tri broja.

a sto se delenja tice posto sam zaboravio kako se predstavljaju decimalni projevi u bin sistemu to ti ne znam reci (cini mi se cak da tu ima i nekoliko standarda, mozda i zavisi od sistema...).

[ jandrla @ 28.08.2003. 21:09 ] @

Citat:

Ramirez:
Naravno da je matematicki moguce realizovati deljenje binarnih brojeva na bitovskom nivou i algoritam koji to realizuje je jako poznat ne mogu se tacno setiti imena posto sam to radio pre dve i po godine ali ti preporucujem knjigu "Osnovi racunarskih sistema" od Nenada Mitica gde ti je algoritam savrseno dobro objasnjen i lako primenljiv.

Radim funkcije za rachunske operacije sa velikim brojevima predstavljenim u obliku statichkih nizova (50 elemenata ili vishe). Svako polje niza nosi jednu cifru.

Sabiranje i oduzimanje ovakva dva broja je lako i zavrsheno... mnozenje sam pocheo i mislim da nije preterano teshko ali deljenje je matematichki nemoguce realizovati (bar ja tako mislim) na nivou odvojenih cifara....

Pa je ideja bila da se mnozenje i deljenje urade preko binarnih brojeva... Rekoshe mi da je to shiftovanje u levo i desno (ali sam ja malo skeptichan). Probao sam da mnozim binarne brojeve ali mi nije jasan princip...???

[ zglgrgd @ 23.10.2009. 01:25 ] @

Ajde pojasni to shiftovanje sallle ?

Konkretno me zanima Šta znači pomnožiti neki broj u binarnom brojnom sisteamu brojem 2k? Ako je to to-shiftovanje.
I odg mi na ovo boldovano.

[ EArthquake @ 23.10.2009. 06:57 ] @

shiftovanje ulevo za n mesta == mnozenje sa 2^n
znaci ako imamo broj 1010b (10 dekadno) i siftujemo ga jednom ulevo dobijemo 10100b (20 dekadno)

ako ga siftujes 2 puta , to je kao mnozenje sa 2^2 tj 4 (operatori << i >> predstavljaju shiftovanje ulevo i udesno , respektivno)
1010 << 2 = 101000b (sto je 40 dekadno)
sa 3 bi bilo 2^3 = 8 , dakle isto sto i mnozenje s 8 i tako dalje

shiftovanje udesno je ekvivalentno samo sto se radi o deljenju
1010 >> 1 = 101b (sto je 5 dekadno)

da ne dodje do zabune , jos jednom da istaknem da se radi o mnozenju i deljenju
SAMO stepenima dvojke , tj mnozenju/deljenju sa 2 , 4 , 8 ,16 , 32 ,64 , 128 , 256 , 512 , 1024 , 2048 , 4096 ... (malo sam se zaneo ... :) )

[ Nedeljko @ 14.11.2009. 17:18 ] @

Ne znam da li će ti ovaj program pomoći. Od ugrađenih aritmetičkih operacija oslanja se samo na sabiranje.

Code:
#include <iostream>
#include <cstdlib>

using namespace std;

typedef unsigned long long int Integer;

Integer quotient(Integer num, Integer den) {
    if (num < den)
        return 0;

    Integer result = 0;
    int pow = 0;

    while (true) {
        int newDen = den << 1;

        if (newDen > num)
            break;

        den = newDen;
        ++pow;
    }

    pow = 1 << pow;

    while (num > 0) {
        if (num >= den) {
            num -= den;
            result |= pow;
        }

        pow >>= 1;
        den >>= 1;
    }

    return result;
}

Integer product(Integer a, Integer b) {
    if (b == 0)
        return 0;

    Integer result = 0;
    int pow = 0;

    while ((1<<pow) <= b)
        ++pow;

    for (--pow; pow>=0; --pow)
        if ((1<<pow) & b)
            result += a << pow;

    return result;
}

int main(int argc, char *argv[])
{
    cout << quotient(15,3) << endl;
    cout << product(15,3) << endl;

    return EXIT_SUCCESS;
}