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

Hinweise auf besondere Websites, Vorstellung eigener Websites, Internet-Smalltalk
nufan
Wiki-Moderator
Beiträge: 2557
Registriert: Sa Jul 05, 2008 3:21 pm

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

Beitrag von nufan » Mo Jul 30, 2012 3:38 pm

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

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

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

Beitrag von Xin » Mo Jul 30, 2012 4:58 pm

Also nur Bit-Operatoren?
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

nufan
Wiki-Moderator
Beiträge: 2557
Registriert: Sa Jul 05, 2008 3:21 pm

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

Beitrag von nufan » Mo Jul 30, 2012 6:03 pm

Xin hat geschrieben:Also nur Bit-Operatoren?
Das wäre eine Möglichkeit, es gibt aber noch andere.

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

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

Beitrag von cloidnerux » Mo Jul 30, 2012 10:07 pm

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.
Redundanz macht wiederholen unnötig.
quod erat expectandum

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

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

Beitrag von Xin » Fr Aug 03, 2012 12:04 am

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.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Benutzeravatar
fat-lobyte
Beiträge: 1398
Registriert: Sa Jul 05, 2008 12:23 pm
Wohnort: ::1
Kontaktdaten:

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

Beitrag von fat-lobyte » Fr Aug 03, 2012 1:49 am

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

Benutzeravatar
fat-lobyte
Beiträge: 1398
Registriert: Sa Jul 05, 2008 12:23 pm
Wohnort: ::1
Kontaktdaten:

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

Beitrag von fat-lobyte » Fr Aug 03, 2012 2:33 am

Was hindert einen eigentlich daran, die Integerdivision mit Bitoperatoren nachzubauen? Ich nehme an, das ist nicht der Sinn der Aufgabe?
Haters gonna hate, potatoes gonna potate.

nufan
Wiki-Moderator
Beiträge: 2557
Registriert: Sa Jul 05, 2008 3:21 pm

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

Beitrag von nufan » Fr Aug 03, 2012 2:40 am

fat-lobyte hat geschrieben: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 :)
fat-lobyte hat geschrieben: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.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

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

Beitrag von Xin » Fr Aug 03, 2012 8:44 am

dani93 hat geschrieben:
fat-lobyte hat geschrieben: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?"
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Benutzeravatar
fat-lobyte
Beiträge: 1398
Registriert: Sa Jul 05, 2008 12:23 pm
Wohnort: ::1
Kontaktdaten:

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

Beitrag von fat-lobyte » Mi Aug 08, 2012 11:58 am

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))
           ));
                
}
Du hast keine ausreichende Berechtigung, um die Dateianhänge dieses Beitrags anzusehen.
Haters gonna hate, potatoes gonna potate.

Antworten