Zahl ohne *, /, +, - und % durch 3 dividieren

[nufan]

Mal wieder eine kleine Denkaufgabe

Wie kann man einen Integer durch 3 dividieren, ohne die Operatoren *, /, +, - oder % zu verwenden?
Vorweg: Das ist keine Fangfrage. Das Problem ist wirklich programmiertechnisch zu lösen und wurde angeblich bei einem Oracle-Jobinterview gestellt.

Lösung:
http://stackoverflow.com/questions/1169 ... -operators

[Xin]

Also nur Bit-Operatoren?

[nufan]

Also nur Bit-Operatoren?

Das wäre eine Möglichkeit, es gibt aber noch andere.

[cloidnerux]

Das wäre eine Möglichkeit, es gibt aber noch andere.

Man kann es auch nähern.
Sei a der Quotient und x der Ergebnis, so ist a / 2 * 2/3= x, das Ergebnis der Division durch 2 liegt also etwas über dem zu erwarteten Ergebnis.
a / 4 * 4/3 = x, die Division der zahl durch 4 liegt also etwas unter dem Ergebnis.
Addiert man nun das Ergebnis der Division durch 4 und der Division durch 2(Division per Shift) und shiftet dieses wieder um 2(Mittelwert), erhält man das voraussichtliche Ergebnis der Division durch 3(Bei Zahlen bis 1k >2% Fehler). Eine Addition lässt sich Bitweise nach dem Volladdierer bauen, indem man sich durch die Bits iteriert, der ++ Operator ist ja nicht verboten.
Verbessern lässt sich das Ergebnis durch bessere Aufteilung der Division von 4 und 2, man nur beachten das die gesamtsumme 2^n entspricht.

[Xin]

Ich habe durch Fragen meiner Möglichkeiten an dani93 und dem einen oder anderen Tipp, worauf er hinauswill, eine ziemlich kranke Lösung gefunden:

Man lege eine Datei der Größe X an und lese anschließend X Blöcke der Größe 3 Bytes ein. Das passt nicht, denn das wären ja 3*x Bytes. Also ist nach X/3 Blöcken Schluss und das gibt fread zurück.
Das Ziel ist also wirklich, kranke Lösungen zu finden, um die Operatoren nicht selbst zu verwenden.

Vielleicht kann dani93 ja mal die eine oder andere Lösung vorstellen, sofern niemand mehr einen Versuch starten möchte.

[fat-lobyte]

Also ich hätt da mittlerweile doch noch eine Idee. Hat zwar nichts mehr mit optimierung zu tun, aber funktionieren tuts.

[fat-lobyte]

Was hindert einen eigentlich daran, die Integerdivision mit Bitoperatoren nachzubauen? Ich nehme an, das ist nicht der Sinn der Aufgabe?

[nufan]

Also ich hätt da mittlerweile doch noch eine Idee. Hat zwar nichts mehr mit optimierung zu tun, aber funktionieren tuts.

Dann nur her damit

Was hindert einen eigentlich daran, die Integerdivision mit Bitoperatoren nachzubauen? Ich nehme an, das ist nicht der Sinn der Aufgabe?

Kannst du natürlich auch machen ^^ Die Angabe ist etwas schwammig formuliert, aber das bedeutet auch, dass du kein ++, --, +=, -= usw. verwenden darfst. Das kannst du dir aber natürlich auch selber bauen ^^
Es geht nicht darum eine optimierte oder besonders elegante Lösung zu finden. Es geht darum auf etwas an sich selbstverständliches zu verzichten und trotzdem ans Ziel zu kommen. Die von Xin beschriebene Lösung ist alles andere als optimal oder elegant, aber sie führt zum Ziel und erfüllt die Kriterien.

[Xin]

Was hindert einen eigentlich daran, die Integerdivision mit Bitoperatoren nachzubauen? Ich nehme an, das ist nicht der Sinn der Aufgabe?

Kannst du natürlich auch machen ^^ Die Angabe ist etwas schwammig formuliert, aber das bedeutet auch, dass du kein ++, --, +=, -= usw. verwenden darfst. Das kannst du dir aber natürlich auch selber bauen ^^

Das Schwammige war auch der Grund, weswegen ich Dich quasi so lange fragte, was erlaubt war, bis klar war, dass ich die Std-Lib habe und andere Dinge notfalls von Hand nachbauen kann.
War ++/-- nicht nun auch nicht erlaubt?


Fragen aus Jobinterviews, die ich hatte waren "Wieviele Menschen spielen jetzt in Neuseeland Golf?", "Warum sind Gullideckel rund?" oder "Was wiegt eine Jumbojet beim Start?"

[fat-lobyte]

Code: Alles auswählen

#include <cmath>

inline int my_round(long double d)
{ return (d + 0.5L); }

int divide_by_3(int x)
{
    return my_round(
            tan(static_cast<long double>(atan2(
                        static_cast<long double>(x),3.0L))
           ));
                
}