[JAVA] Recursief omzetten decimaal naar binair

[Oyster]

Momenteel ben ik bezig met een programma dat recursief een conversie maakt van decimaal naar binair. Ik raak er alleen echt niet uit. Waarschijnlijk zie ik iets ontzettend voor de hand liggends over het hoofd, maar dat zal blijken.

Een decimaal getal is naar binair om te zetten door het integer getal continue door 2 te delen. De rest geeft het binair bit weer. Als voorbeeld nemen we het getal. 127.

code:

127/2 = 63, rest = 1
63/2 = 31, rest = 1
31/2 = 15, rest = 1
15/2 = 7, rest = 1
7/2 = 3, rest = 1
3/2 = 1, rest = 1
1/2 = 0, rest = 1

Van onder naar boven wordt het getal 127 door het binaire getal 1111111 gerepresentateerd.

Nu heb ik de volgende recursieve methode ontworpen, dat het binaire getal uit moet spugen. Daarbij moeten de rest waardes aan elkaar geplakt worden. Met deze rest waardes mag dus niet gerekend worden!

code:

int decToBin(int i){
  if (i==0)
    return 1; (Moet eraan geplakt worden)
  else 
    (Hier wordt de aan elkaar geplakte binaire waarde gemaakt)
    return decToBin(i/2)
}

Het probleem is dat ik de afzonderlijke berekende rest waardes aan elkaar moet plakken.Integers bieden geen mogelijkheid om er karakters aan toe te voegen. Aan een string kunnen karakters toegevoegd worden. Helaas kan ik geen strings returnen aangezien de methode integers verwacht. Met strings kan namelijk ook niet gerekend worden. Mijn techniek stinkt dus, maar ik ben er wel van overtuigd dat ik op de goede weg zit. Iemand die mij een duwtje in de goede richting kan geven? Ik ben echt de draad kwijt.

[TheBlasphemer]

Moet je dec->bin doen gewoon, of heb je specifieke opdracht/reden dit recursief te doen?

Anders kun je dit proberen:

code:

string output="";
int value=127;
while (value>0) {
  output=((value & 1 != 0)?"1":"0") + output;
  value/=2;
}

Dit is beetje pseudocode, het "& 1" kun je ook "% 2" van maken, en de /=2 kun je ook bitshiften, moet je denkik value=value<<1 of value=value>>1 doen.
Ik denk dat "& 1" met bitshifting de snelste implementatie zou zijn in C++, Java weet ik niet zeker wat sneller is aangezien ik niet weet of deze berekening rechtstreeks naar processor gaat of anders.

[Oyster]

Bedankt voor je hulp. Java beschikt idd over methodes om dit makkelijk op te lossen. Helaas moet het recursief.

[TheBlasphemer]

code:

string decToBin(int value) {
  string output="";
  if (value>0) output=decToBin(value/2);
  return output+((value%2)?"1":"0");
}

is dat wat ? (zo even uit de losse hand, zou theoretisch moeten werken...)

[Woy]

Het probleem met je eigen recursieve functie is dat je of 1 returnt of de waarde Van decToBin. De laatste call ( als i == 0 ) geeft altijd 1 terug dus jouw functie zal uiteindelijk altijd 1 returnen. Je zut idd iets moeten doen met een string oid. Het is namenlijk nogal onzinnig om een representatie in een int te gaan stoppen. Onderliggend is een int namenlijk gewoon al binair.

[Daos]

Xander2000 schreef op woensdag 11 januari 2006 @ 00:39:
Als voorbeeld nemen we het getal. 127.

code:

127/2 = 63, rest = 1
63/2 = 31, rest = 1
31/2 = 15, rest = 1
15/2 = 7, rest = 1
7/2 = 3, rest = 1
3/2 = 1, rest = 1
1/2 = 0, rest = 1

Van onder naar boven wordt het getal 127 door het binaire getal 1111111 gerepresentateerd.

Het klopt wel allemaal, maar je kan beter een voorbeeldje nemen waar wat enen en nullen door elkaar staan. Bv 1 + 2 + 16 + 64 = 83

code:

83/2 = 41, rest = 1
41/2 = 20, rest = 1
20/2 = 10, rest = 0
10/2 = 5, rest = 0
5/2 = 2, rest = 1
2/2 = 1, rest = 0
1/2 = 0, rest = 1

Van onder naar boven wordt het getal 83 door het binaire getal 1010011 gerepresentateerd.

code:

int decToBin(int i){
  if (i==0)
    return 1; (Moet eraan geplakt worden)
  else 
    (Hier wordt de aan elkaar geplakte binaire waarde gemaakt)
    return decToBin(i/2)
}

Je had al wat meer kunnen doen:

Java:

int decToBin(int i) {
  if (i == 1)
    return 1;
  else {
    int q = i / 2;      // of iets anders wat hetzelfde doet.
    int r = i - 2 * q;  // of iets anders wat hetzelfde doet.

    int b = decToBin(q);
    
    return (Hier wordt r achter b geplakt)
  }
}

Dat plakken van r achter b is met strings te doen door b + r.
Met integers is het iets lastiger. Neem bijvoorbeeld b = 12 en r = 3. Als je die 3 achter de 12 wilt krijgen, dan doe je 12 * 10 + 3 oftewel b * 10 + r.

[ Voor 8% gewijzigd door Daos op 11-01-2006 12:49 . Reden: Hoop fouten en typo's. Volgende keer maar weer eerst bekijken voordat ik versturen doe ]

[Verwijderd]

Wordt binair niet van rechts naar links gelezen?
Voor 83 zou de output 1100101 moeten worden in plaats van 1010011.

Dan zou de rest dus voor de 'decToBin(q)' geplakt moeten worden in plaats van er achter.

Volgens mij maak je het jezelf onnodig moeilijk door met int's te werken, als je een binaire waarde opslaat in een int valt er namelijk toch niet mee te rekenen (101 - 010 = 91).

[ Voor 4% gewijzigd door Verwijderd op 11-01-2006 15:27 . Reden: onzin ]

[Varienaja]

Verwijderd schreef op woensdag 11 januari 2006 @ 12:52:
Wordt binair niet van rechts naar links gelezen?

Binair lees je gewoon van links naar rechts, net als alle andere getallen.

In computers worden integers soms wel wazig opgeslagen: het little-endian vs big-endian. Maar dat maakt voor deze functie geen bezwaar.

[seamus21]

Kijk eens naar mijn onderstaande functie. Dit was toevallig in dit blok een practicumopgave.

Java:

public String getBinary(int n)
{
    if (n < 0)
    {
        return "?";
    } else {
        if (n == 0)
        {
            return "0";
        } else if (n == 1) {
            return "1";
        } else {
            String s = getBinary(n / 2) + getBinary(n % 2);

            return s;
        }
    }
}

[ Voor 45% gewijzigd door seamus21 op 11-01-2006 13:12 ]

[Gerco]

Helaas kan ik geen strings returnen aangezien de methode integers verwacht.

Hoe bedoel je? Als je een integer returnt uit die dec2bin() method, heb je dus gewoon weer een getal en geen string binaire tekens...

dec2bin(127) zal dan 1111111 opleveren, wat heel iets anders betekent dan "1111111" of 0b1111111 (Java ondersteunt volgens mij geen binaire constanten, maar ik zeg 0b om het duidelijk te maken).

[Verwijderd]

@Varienaja:
hmm, dat had ik niet helemaal duidelijk gezegd, wat ik vooral bedoelde was dat binaire getallen meestal in de volgorde '2^2 | 2^1 | 2^0' genoteerd worden.

[Gerco]

Verwijderd schreef op woensdag 11 januari 2006 @ 13:21:
@Varienaja:
hmm, dat had ik niet helemaal duidelijk gezegd, wat ik vooral bedoelde was dat binaire getallen meestal in de volgorde '2^2 | 2^1 | 2^0' genoteerd worden.

Decimale getallen worden toch ook zo genoteerd?

321 = 3*10² + 2*10¹ + 1*10⁰

[ Voor 6% gewijzigd door Gerco op 11-01-2006 15:43 ]

[Verwijderd]

Aargh, volgende keer nadenken voor ik post.
Je/jullie hebben helemaal gelijk.

[Oyster]

seamus21 schreef op woensdag 11 januari 2006 @ 13:09:
Kijk eens naar mijn onderstaande functie. Dit was toevallig in dit blok een practicumopgave.

Super! Dit werkt helemaal uitstekend. Mijn veronderstelling dat je geen string methode kan gebruiken omdat je een integer terug moet koppelen is dus helemaal fout. Hier ben ik dus op mn plaat gegaan. Ik had dat even meer moeten bestuderen natuurlijk. Bedankt! :W

[Verwijderd]

seamus21 schreef op woensdag 11 januari 2006 @ 13:09:
Kijk eens naar mijn onderstaande functie. Dit was toevallig in dit blok een practicumopgave.

Een case-statement lijkt me hier uitstekend toe te passen en maakt het geheel ook leesbaarder.

[Woy]

Verwijderd schreef op woensdag 11 januari 2006 @ 23:49:
[...]

Een case-statement lijkt me hier uitstekend toe te passen en maakt het geheel ook leesbaarder.

IDD of laat ieder geval alle else statements weg. Omdat je een return doet heb je die else helemaal niet meer nodig. Je programma flow kan daar dan toch niet meer komen.

Java:

public String getBinary(int n)
{
    if (n < 0){
        return "?";
    } 
    if (n == 0){
        return "0";
    }
    if (n == 1){
        return "1";
    }
    return getBinary(n / 2) + getBinary(n % 2);
}

Doet exact hetzelfde.

[Daos]

Verwijderd schreef op woensdag 11 januari 2006 @ 12:52:
Volgens mij maak je het jezelf onnodig moeilijk door met int's te werken, als je een binaire waarde opslaat in een int valt er namelijk toch niet mee te rekenen (101 - 010 = 91).

Kan je met Strings dan wel rekenen?

Xander2000 schreef op woensdag 11 januari 2006 @ 23:23:
Super! Dit werkt helemaal uitstekend. Mijn veronderstelling dat je geen string methode kan gebruiken omdat je een integer terug moet koppelen is dus helemaal fout. Hier ben ik dus op mn plaat gegaan. Ik had dat even meer moeten bestuderen natuurlijk. Bedankt! :W

Je kan het ook doen met integers:

Java:

public static int getBinary(int n) {
  if (n < 0)
    return -1;
  else if (n < 2)
    return n;
  else
    return getBinary(n >> 1) * 10 | n & 1;
}

Het ging bij jou al eerder verkeerd. Snap je nu hoe recursie werkt of had je alleen interesse in een kant-en-klare oplossing?

Verwijderd schreef op woensdag 11 januari 2006 @ 23:49:
Een case-statement lijkt me hier uitstekend toe te passen en maakt het geheel ook leesbaarder.

Hoe wil je (n < 0) in switch/case zetten? Als je de opmaak een beetje mooi maakt en de code iets versimpelt, dan is het al redelijk leesbaar:

Java:

public static String getBinary(int n) {
  if (n < 0)
    return "?";
  else if (n == 0)
    return "0";
  else if (n == 1)
    return "1";
  else
    return getBinary(n / 2) + getBinary(n % 2);
}

[ Voor 11% gewijzigd door Daos op 12-01-2006 10:22 ]

[Cuball]

volgens mij kan je het ook doen adhv bit operations...en dit in een integer ploefen. Je moet dan wel opletten met voorloopnullen en tekenbits, maar het is te doen

[farlane]

Wat is het voordeel van recursie hier?

[Woy]

farlane schreef op donderdag 12 januari 2006 @ 10:53:
Wat is het voordeel van recursie hier?

Waarschijnlijk dat de leraar het goed keurt

Daos schreef op donderdag 12 januari 2006 @ 09:38:
[...]
Je kan het ook doen met integers:

Java:

public static int getBinary(int n) {
  if (n < 0)
    return -1;
  else if (n < 2)
    return n;
  else
    return getBinary(n >> 1) * 10 | n & 1;
}

Wat voor nut heeft het om dat in een integer te stoppen?? Het heeft toch geen enkel nut om een visuele representatie van een integer in een integer te stoppen. Je krijgt dan tenslotte een andere waarde.

Hoe wil je (n < 0) in switch/case zetten? Als je de opmaak een beetje mooi maakt en de code iets versimpelt, dan is het al redelijk leesbaar:

Java:

public static String getBinary(int n) {
  if (n < 0)
    return "?";
  else if (n == 0)
    return "0";
  else if (n == 1)
    return "1";
  else
    return getBinary(n / 2) + getBinary(n % 2);
}

Als je toch overal de return statement inzet dan heb je die elses helemaal niet nodig. Als je perse met else wilt werken kan je dan beter pas aan het eind van je method returnen.

Java:

public static String getBinary(int n) {
  string returnValue;
  if (n < 0)
    returnValue= "?";
  else if (n == 0)
    returnValue = "0";
  else if (n == 1)
    returnValue = "1";
  else
    returnValue = getBinary(n / 2) + getBinary(n % 2);
  return returnValue;
}

Maar zelf zou ik gewoon de else overal weg laten.

[ Voor 79% gewijzigd door Woy op 12-01-2006 11:59 ]

[Daos]

rwb schreef op donderdag 12 januari 2006 @ 11:55:
Wat voor nut heeft het om dat in een integer te stoppen?? Het heeft toch geen enkel nut om een visuele representatie van een integer in een integer te stoppen. Je krijgt dan tenslotte een andere waarde.

Dat heeft inderdaad niet veel nut (er past ook niet zoveel in), maar de topicstarter wilde dat in eerste instantie. Hij beweert nu dat het hem niet lukte omdat hij niet met Strings werkte. Met het voorbeeld laat ik zien dat dat niet waar is. Hij begrijpt gewoon niet hoe recursie werkt.

[Oyster]

Daos schreef op donderdag 12 januari 2006 @ 13:01:
[...]

Dat heeft inderdaad niet veel nut (er past ook niet zoveel in), maar de topicstarter wilde dat in eerste instantie. Hij beweert nu dat het hem niet lukte omdat hij niet met Strings werkte. Met het voorbeeld laat ik zien dat dat niet waar is. Hij begrijpt gewoon niet hoe recursie werkt.

Ik snap prima hoe recursie werkt.

En idd de leraar wilde het zo.

[seamus21]

Ow oh. Ik zie dat de code hier verder besproken is. Mijn codevoorbeeld was een practicum opdracht en was precies goed zoals het er stond. Tuurlijk kan het anders. Maar ik had het gepost om een voorbeeld te laten zien.

[Paul]

Daos schreef op donderdag 12 januari 2006 @ 09:38:
[...]

Kan je met Strings dan wel rekenen?

Ja, maar dan krijg je HELE lange lappen code. Optellen valt nog wel mee, aftrekken wordt al wat meer maar vermenigvuldigen en delen worden echt (relatief) gigantisch

Heb ik ook een keer als schoolopdracht gehad waarna ik het nog een keer overdeed in Bash omdat ik nog nooit van 'bc' gehoord had

[MTWZZ]

Misschien relevant, ik heb het SHA256 algoritme gebouwd in PHP waar ik dus ook het probleem had met omzetting naar binair.
Ik heb er een klasse voor geschreven dus mayb heb je er iets aan.
http://dev.barad-dur.nl/sha256/

[Woy]

MTWZZ schreef op vrijdag 13 januari 2006 @ 09:11:
Misschien relevant, ik heb het SHA256 algoritme gebouwd in PHP waar ik dus ook het probleem had met omzetting naar binair.
Ik heb er een klasse voor geschreven dus mayb heb je er iets aan.
http://dev.barad-dur.nl/sha256/

Hoezo moet je voor SHA256 omzetten naar binair?? Als je gewoon een Int hebt ( of BigInt in jouw geval ) dan is dat al binair, of hexidecimaal of decimaal. Dat zijn allemaal gewoon representaties van een int. Als je bedoeld dat je bit operaties wilt doen kun je daar gewoon de juiste binaire operators voor gebruiken.

[MTWZZ]

True maar PHP kent alleen signed integers en als je gaat bitshiften op die krengen dan kom je nog voor leuke problemen te staan
En BigInt in PHP zit in een extensie die niet bij alle hosters aanstaat ook al zit het standaard in de PHP source.
Overigens is het hoe en wat van het SHA256 algoritme zoals ik hem heb niet zo boeiend maar puur het omzetten van integers naar strings etc.

[Paul]

MTWZZ schreef op vrijdag 13 januari 2006 @ 09:11:
Misschien relevant, ik heb het SHA256 algoritme gebouwd in PHP

offtopic:
Input: Hallo hoe is het? en je krijgt een mooie notice: Notice: Undefined offset: 8 in /var/www/dev.barad-dur.nl/sha256/BigInt.inc.php on line 254

[MTWZZ]

Paul Nieuwkamp schreef op vrijdag 13 januari 2006 @ 10:35:
[...]

offtopic:
Input: Hallo hoe is het? en je krijgt een mooie notice: Notice: Undefined offset: 8 in /var/www/dev.barad-dur.nl/sha256/BigInt.inc.php on line 254

offtopic:
Lullig van dat ding
Ach de berekening klopt wel dus dat boeit niet zo (het is de ToString)