Teilen Sie eine Zahl durch 3, ohne die Operatoren *, /, +, -, % zu verwenden
https://stackoverflow.com//questions/11694546
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Wie würden Sie eine Zahl durch 3 dividieren, ohne sie zu verwenden? *, /, +, -, %, Betreiber?
Die Nummer kann signiert oder nicht signiert sein.
Lösung
Das ist ein einfache Funktion welches den gewünschten Vorgang ausführt.Aber es erfordert die + Operator, Sie müssen also nur noch die Werte mit Bit-Operatoren addieren:
// replaces the + operator
int add(int x, int y)
{
while (x) {
int t = (x & y) << 1;
y ^= x;
x = t;
}
return y;
}
int divideby3(int num)
{
int sum = 0;
while (num > 3) {
sum = add(num >> 2, sum);
num = add(num >> 2, num & 3);
}
if (num == 3)
sum = add(sum, 1);
return sum;
}
Wie Jim kommentierte, funktioniert dies, weil:
n = 4 * a + bn / 3 = a + (a + b) / 3Also
sum += a,n = a + b, und iterierenWann
a == 0 (n < 4),sum += floor(n / 3);d.h.1,if n == 3, else 0
Andere Tipps
Idiotische Zustände erfordern eine idiotische Lösung:
#include <stdio.h>
#include <stdlib.h>
int main()
{
FILE * fp=fopen("temp.dat","w+b");
int number=12346;
int divisor=3;
char * buf = calloc(number,1);
fwrite(buf,number,1,fp);
rewind(fp);
int result=fread(buf,divisor,number,fp);
printf("%d / %d = %d", number, divisor, result);
free(buf);
fclose(fp);
return 0;
}
Wenn auch der Dezimalteil benötigt wird, einfach angeben result als double und addiere dazu das Ergebnis von fmod(number,divisor).
Erklärung, wie es funktioniert
- Der
fwriteschreibtnumberBytes (im Beispiel oben ist die Zahl 123456). rewindSetzt den Dateizeiger auf den Anfang der Datei zurück.freadliest maximalnumber"Aufzeichnungen", die sinddivisorin der Länge aus der Datei und gibt die Anzahl der gelesenen Elemente zurück.
Wenn Sie 30 Bytes schreiben und die Datei dann in Einheiten von 3 zurücklesen, erhalten Sie 10 „Einheiten“.30 / 3 = 10
log(pow(exp(number),0.33333333333333333333)) /* :-) */
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
int num = 1234567;
int den = 3;
div_t r = div(num,den); // div() is a standard C function.
printf("%d\n", r.quot);
return 0;
}
Sie können (plattformabhängig) Inline-Assembly verwenden, z. B. für x86: (funktioniert auch für negative Zahlen)
#include <stdio.h>
int main() {
int dividend = -42, divisor = 5, quotient, remainder;
__asm__ ( "cdq; idivl %%ebx;"
: "=a" (quotient), "=d" (remainder)
: "a" (dividend), "b" (divisor)
: );
printf("%i / %i = %i, remainder: %i\n", dividend, divisor, quotient, remainder);
return 0;
}
Verwenden itoa zum Konvertieren in eine Basis-3-Zeichenfolge.Lass das letzte fallen trit und zurück zur Basis 10 konvertieren.
// Note: itoa is non-standard but actual implementations
// don't seem to handle negative when base != 10.
int div3(int i) {
char str[42];
sprintf(str, "%d", INT_MIN); // Put minus sign at str[0]
if (i>0) // Remove sign if positive
str[0] = ' ';
itoa(abs(i), &str[1], 3); // Put ternary absolute value starting at str[1]
str[strlen(&str[1])] = '\0'; // Drop last digit
return strtol(str, NULL, 3); // Read back result
}
(Notiz:siehe Edit 2 unten für eine bessere Version!)
Das ist nicht so schwierig, wie es sich anhört, denn Sie sagten: „Ohne die [..] zu verwenden“ + [..] Betreiber".Siehe unten, wenn Sie die Verwendung verbieten möchten + Charakter alle zusammen.
unsigned div_by(unsigned const x, unsigned const by) {
unsigned floor = 0;
for (unsigned cmp = 0, r = 0; cmp <= x;) {
for (unsigned i = 0; i < by; i++)
cmp++; // that's not the + operator!
floor = r;
r++; // neither is this.
}
return floor;
}
dann sag es einfach div_by(100,3) zu teilen 100 von 3.
Bearbeiten:Sie können fortfahren und das ersetzen ++ Betreiber auch:
unsigned inc(unsigned x) {
for (unsigned mask = 1; mask; mask <<= 1) {
if (mask & x)
x &= ~mask;
else
return x & mask;
}
return 0; // overflow (note that both x and mask are 0 here)
}
Bearbeiten 2:Etwas schnellere Version ohne Verwendung eines Operators, der das enthält +,-,*,/,% Figuren.
unsigned add(char const zero[], unsigned const x, unsigned const y) {
// this exploits that &foo[bar] == foo+bar if foo is of type char*
return (int)(uintptr_t)(&((&zero[x])[y]));
}
unsigned div_by(unsigned const x, unsigned const by) {
unsigned floor = 0;
for (unsigned cmp = 0, r = 0; cmp <= x;) {
cmp = add(0,cmp,by);
floor = r;
r = add(0,r,1);
}
return floor;
}
Wir verwenden das erste Argument des add Funktion, da wir den Typ der Zeiger nicht angeben können, ohne die zu verwenden * Zeichen, außer in Funktionsparameterlisten, wo die Syntax type[] ist identisch mit type* const.
FWIW, Sie können eine Multiplikationsfunktion mit einem ähnlichen Trick leicht implementieren, um die zu verwenden 0x55555556 Trick vorgeschlagen von AndreyT:
int mul(int const x, int const y) {
return sizeof(struct {
char const ignore[y];
}[x]);
}
Auf der ist das problemlos möglich Computer einrichten.
Um eine ganze Zahl durch 3 zu dividieren, um 1 Stelle nach rechts verschieben.
Ich bin mir allerdings nicht sicher, ob es überhaupt möglich ist, einen konformen C-Compiler auf einer solchen Plattform zu implementieren.Möglicherweise müssen wir die Regeln etwas erweitern, indem wir beispielsweise „mindestens 8 Bits“ als „in der Lage, mindestens ganze Zahlen von -128 bis +127 zu speichern“ interpretieren.
Da es von Oracle stammt, wie wäre es mit einer Nachschlagetabelle mit vorberechneten Antworten?:-D
Hier ist meine Lösung:
public static int div_by_3(long a) {
a <<= 30;
for(int i = 2; i <= 32 ; i <<= 1) {
a = add(a, a >> i);
}
return (int) (a >> 32);
}
public static long add(long a, long b) {
long carry = (a & b) << 1;
long sum = (a ^ b);
return carry == 0 ? sum : add(carry, sum);
}
Beachten Sie zunächst Folgendes
1/3 = 1/4 + 1/16 + 1/64 + ...
Der Rest ist einfach!
a/3 = a * 1/3
a/3 = a * (1/4 + 1/16 + 1/64 + ...)
a/3 = a/4 + a/16 + 1/64 + ...
a/3 = a >> 2 + a >> 4 + a >> 6 + ...
Jetzt müssen wir nur noch diese bitverschobenen Werte von a addieren!Hoppla!Da wir jedoch nicht addieren können, müssen wir stattdessen eine Additionsfunktion mit bitweisen Operatoren schreiben!Wenn Sie mit bitweisen Operatoren vertraut sind, sollte meine Lösung ziemlich einfach aussehen ...Aber nur für den Fall, dass Sie es nicht sind, werde ich am Ende ein Beispiel durchgehen.
Zu beachten ist auch, dass ich zuerst um 30 nach links verschiebe!Dadurch soll sichergestellt werden, dass die Brüche nicht gerundet werden.
11 + 6
1011 + 0110
sum = 1011 ^ 0110 = 1101
carry = (1011 & 0110) << 1 = 0010 << 1 = 0100
Now you recurse!
1101 + 0100
sum = 1101 ^ 0100 = 1001
carry = (1101 & 0100) << 1 = 0100 << 1 = 1000
Again!
1001 + 1000
sum = 1001 ^ 1000 = 0001
carry = (1001 & 1000) << 1 = 1000 << 1 = 10000
One last time!
0001 + 10000
sum = 0001 ^ 10000 = 10001 = 17
carry = (0001 & 10000) << 1 = 0
Done!
Es ist einfach das Additionstragen, das Sie als Kind gelernt haben!
111
1011
+0110
-----
10001
Diese Implementierung fehlgeschlagen weil wir nicht alle Terme der Gleichung addieren können:
a / 3 = a/4 + a/4^2 + a/4^3 + ... + a/4^i + ... = f(a, i) + a * 1/3 * 1/4^i
f(a, i) = a/4 + a/4^2 + ... + a/4^i
Angenommen, das Ergebnis von div_by_3(a) = x also x <= floor(f(a, i)) < a / 3.Wann a = 3k, wir bekommen eine falsche Antwort.
Um eine 32-Bit-Zahl durch 3 zu dividieren, kann man sie mit multiplizieren 0x55555556 und nehmen Sie dann die oberen 32 Bits des 64-Bit-Ergebnisses.
Jetzt müssen Sie nur noch die Multiplikation mithilfe von Bitoperationen und Verschiebungen implementieren ...
Noch eine andere Lösung.Dies sollte alle Ints (einschließlich negativer Ints) verarbeiten, mit Ausnahme des Mindestwerts eines Ints, der als fest codierte Ausnahme behandelt werden müsste.Dies führt grundsätzlich eine Division durch Subtraktion durch, jedoch nur unter Verwendung von Bitoperatoren (Verschiebungen, XOR und & und Komplement).Für eine höhere Geschwindigkeit wird 3 * subtrahiert (verringernde Potenzen von 2).In c# führt es etwa 444 dieser DivideBy3-Aufrufe pro Millisekunde aus (2,2 Sekunden für 1.000.000 Teilungen), also nicht schrecklich langsam, aber bei weitem nicht so schnell wie ein einfaches x/3.Im Vergleich dazu ist Coodeys nette Lösung etwa fünfmal schneller als diese.
public static int DivideBy3(int a) {
bool negative = a < 0;
if (negative) a = Negate(a);
int result;
int sub = 3 << 29;
int threes = 1 << 29;
result = 0;
while (threes > 0) {
if (a >= sub) {
a = Add(a, Negate(sub));
result = Add(result, threes);
}
sub >>= 1;
threes >>= 1;
}
if (negative) result = Negate(result);
return result;
}
public static int Negate(int a) {
return Add(~a, 1);
}
public static int Add(int a, int b) {
int x = 0;
x = a ^ b;
while ((a & b) != 0) {
b = (a & b) << 1;
a = x;
x = a ^ b;
}
return x;
}
Das ist C#, weil ich das zur Hand hatte, aber die Unterschiede zu C dürften gering sein.
Es ist wirklich ganz einfach.
if (number == 0) return 0;
if (number == 1) return 0;
if (number == 2) return 0;
if (number == 3) return 1;
if (number == 4) return 1;
if (number == 5) return 1;
if (number == 6) return 2;
(Der Kürze halber habe ich natürlich einen Teil des Programms weggelassen.) Wenn der Programmierer es satt hat, alles abzutippen, könnte er oder sie sicher ein separates Programm schreiben, um es für ihn zu generieren.Mir ist zufällig ein bestimmter Betreiber bekannt, /, das würde seine Arbeit ungemein vereinfachen.
Die Verwendung von Zählern ist eine grundlegende Lösung:
int DivBy3(int num) {
int result = 0;
int counter = 0;
while (1) {
if (num == counter) //Modulus 0
return result;
counter = abs(~counter); //++counter
if (num == counter) //Modulus 1
return result;
counter = abs(~counter); //++counter
if (num == counter) //Modulus 2
return result;
counter = abs(~counter); //++counter
result = abs(~result); //++result
}
}
Es ist auch einfach, eine Modulfunktion auszuführen, siehe Kommentare.
Dies ist der klassische Divisionsalgorithmus zur Basis 2:
#include <stdio.h>
#include <stdint.h>
int main()
{
uint32_t mod3[6] = { 0,1,2,0,1,2 };
uint32_t x = 1234567; // number to divide, and remainder at the end
uint32_t y = 0; // result
int bit = 31; // current bit
printf("X=%u X/3=%u\n",x,x/3); // the '/3' is for testing
while (bit>0)
{
printf("BIT=%d X=%u Y=%u\n",bit,x,y);
// decrement bit
int h = 1; while (1) { bit ^= h; if ( bit&h ) h <<= 1; else break; }
uint32_t r = x>>bit; // current remainder in 0..5
x ^= r<<bit; // remove R bits from X
if (r >= 3) y |= 1<<bit; // new output bit
x |= mod3[r]<<bit; // new remainder inserted in X
}
printf("Y=%u\n",y);
}
Schreiben Sie das Programm in Pascal und verwenden Sie das DIV Operator.
Da die Frage markiert ist C, können Sie wahrscheinlich eine Funktion in Pascal schreiben und sie von Ihrem C-Programm aus aufrufen;Die Methode hierfür ist systemspezifisch.
Aber hier ist ein Beispiel, das auf meinem Ubuntu-System mit Free Pascal funktioniert fp-compiler Paket installiert.(Ich mache das aus purer fehlgeleiteter Sturheit;Ich behaupte nicht, dass dies nützlich ist.)
divide_by_3.pas :
unit Divide_By_3;
interface
function div_by_3(n: integer): integer; cdecl; export;
implementation
function div_by_3(n: integer): integer; cdecl;
begin
div_by_3 := n div 3;
end;
end.
main.c :
#include <stdio.h>
#include <stdlib.h>
extern int div_by_3(int n);
int main(void) {
int n;
fputs("Enter a number: ", stdout);
fflush(stdout);
scanf("%d", &n);
printf("%d / 3 = %d\n", n, div_by_3(n));
return 0;
}
Bauen:
fpc divide_by_3.pas && gcc divide_by_3.o main.c -o main
Beispielausführung:
$ ./main
Enter a number: 100
100 / 3 = 33
int div3(int x)
{
int reminder = abs(x);
int result = 0;
while(reminder >= 3)
{
result++;
reminder--;
reminder--;
reminder--;
}
return result;
}
Es wurde nicht überprüft, ob diese Antwort bereits veröffentlicht ist.Wenn das Programm auf Gleitkommazahlen erweitert werden muss, können die Zahlen mit 10*der erforderlichen Genauigkeit multipliziert werden und dann kann der folgende Code erneut angewendet werden.
#include <stdio.h>
int main()
{
int aNumber = 500;
int gResult = 0;
int aLoop = 0;
int i = 0;
for(i = 0; i < aNumber; i++)
{
if(aLoop == 3)
{
gResult++;
aLoop = 0;
}
aLoop++;
}
printf("Reulst of %d / 3 = %d", aNumber, gResult);
return 0;
}
Dies sollte für jeden Teiler funktionieren, nicht nur für drei.Derzeit nur für Unsigned, aber die Erweiterung auf Signed sollte nicht so schwierig sein.
#include <stdio.h>
unsigned sub(unsigned two, unsigned one);
unsigned bitdiv(unsigned top, unsigned bot);
unsigned sub(unsigned two, unsigned one)
{
unsigned bor;
bor = one;
do {
one = ~two & bor;
two ^= bor;
bor = one<<1;
} while (one);
return two;
}
unsigned bitdiv(unsigned top, unsigned bot)
{
unsigned result, shift;
if (!bot || top < bot) return 0;
for(shift=1;top >= (bot<<=1); shift++) {;}
bot >>= 1;
for (result=0; shift--; bot >>= 1 ) {
result <<=1;
if (top >= bot) {
top = sub(top,bot);
result |= 1;
}
}
return result;
}
int main(void)
{
unsigned arg,val;
for (arg=2; arg < 40; arg++) {
val = bitdiv(arg,3);
printf("Arg=%u Val=%u\n", arg, val);
}
return 0;
}
Wäre es Betrug, das zu verwenden? / Betreiber „hinter den Kulissen“ durch Verwendung eval und String-Verkettung?
Dies ist beispielsweise in Javascript möglich
function div3 (n) {
var div = String.fromCharCode(47);
return eval([n, div, 3].join(""));
}
Benutzen BC Mathematik In PHP:
<?php
$a = 12345;
$b = bcdiv($a, 3);
?>
MySQL (es ist ein Interview von Oracle)
> SELECT 12345 DIV 3;
a:= 12345;
b:= a div 3;
x86-64-Assemblersprache:
mov r8, 3
xor rdx, rdx
mov rax, 12345
idiv r8
Das Erste, was ich mir ausgedacht habe.
irb(main):101:0> div3 = -> n { s = '%0' + n.to_s + 's'; (s % '').gsub(' ', ' ').size }
=> #<Proc:0x0000000205ae90@(irb):101 (lambda)>
irb(main):102:0> div3[12]
=> 4
irb(main):103:0> div3[666]
=> 222
BEARBEITEN: Tut mir leid, ich habe den Tag nicht bemerkt C.Aber Sie können die Idee der Zeichenfolgenformatierung verwenden, denke ich ...
Das folgende Skript generiert ein C-Programm, das das Problem ohne Verwendung der Operatoren löst * / + - %:
#!/usr/bin/env python3
print('''#include <stdint.h>
#include <stdio.h>
const int32_t div_by_3(const int32_t input)
{
''')
for i in range(-2**31, 2**31):
print(' if(input == %d) return %d;' % (i, i / 3))
print(r'''
return 42; // impossible
}
int main()
{
const int32_t number = 8;
printf("%d / 3 = %d\n", number, div_by_3(number));
}
''')
Benutzen Hacker's Delight Magic Zahlenrechner
int divideByThree(int num)
{
return (fma(num, 1431655766, 0) >> 32);
}
Wo fma ist eine Standardbibliotheksfunktion, die in definiert ist math.h Header.
Wie wäre es mit diesem Ansatz (c#)?
private int dividedBy3(int n) {
List<Object> a = new Object[n].ToList();
List<Object> b = new List<object>();
while (a.Count > 2) {
a.RemoveRange(0, 3);
b.Add(new Object());
}
return b.Count;
}
Ich denke, die richtige Antwort ist:
Warum sollte ich nicht einen Basisoperator verwenden, um eine Basisoperation auszuführen?
Lösung mit fma()-Bibliotheksfunktion, funktioniert für jede positive Zahl:
#include <stdio.h>
#include <math.h>
int main()
{
int number = 8;//Any +ve no.
int temp = 3, result = 0;
while(temp <= number){
temp = fma(temp, 1, 3); //fma(a, b, c) is a library function and returns (a*b) + c.
result = fma(result, 1, 1);
}
printf("\n\n%d divided by 3 = %d\n", number, result);
}
Verwenden cblas, als Teil des Accelerate-Frameworks von OS X enthalten.
[02:31:59] [william@relativity ~]$ cat div3.c
#import <stdio.h>
#import <Accelerate/Accelerate.h>
int main() {
float multiplicand = 123456.0;
float multiplier = 0.333333;
printf("%f * %f == ", multiplicand, multiplier);
cblas_sscal(1, multiplier, &multiplicand, 1);
printf("%f\n", multiplicand);
}
[02:32:07] [william@relativity ~]$ clang div3.c -framework Accelerate -o div3 && ./div3
123456.000000 * 0.333333 == 41151.957031
Erste:
x/3 = (x/4) / (1-1/4)
Finden Sie dann heraus, wie Sie x/(1 - y) lösen können:
x/(1-1/y)
= x * (1+y) / (1-y^2)
= x * (1+y) * (1+y^2) / (1-y^4)
= ...
= x * (1+y) * (1+y^2) * (1+y^4) * ... * (1+y^(2^i)) / (1-y^(2^(i+i))
= x * (1+y) * (1+y^2) * (1+y^4) * ... * (1+y^(2^i))
mit y = 1/4:
int div3(int x) {
x <<= 6; // need more precise
x += x>>2; // x = x * (1+(1/2)^2)
x += x>>4; // x = x * (1+(1/2)^4)
x += x>>8; // x = x * (1+(1/2)^8)
x += x>>16; // x = x * (1+(1/2)^16)
return (x+1)>>8; // as (1-(1/2)^32) very near 1,
// we plus 1 instead of div (1-(1/2)^32)
}
Obwohl es verwendet +, aber jemand implementiert bereits add by bitwise op.
Okay, ich denke, wir sind uns alle einig, dass dies kein reales Problem ist.Also nur zum Spaß, hier ist, wie man es mit Ada und Multithreading macht:
with Ada.Text_IO;
procedure Divide_By_3 is
protected type Divisor_Type is
entry Poke;
entry Finish;
private
entry Release;
entry Stop_Emptying;
Emptying : Boolean := False;
end Divisor_Type;
protected type Collector_Type is
entry Poke;
entry Finish;
private
Emptying : Boolean := False;
end Collector_Type;
task type Input is
end Input;
task type Output is
end Output;
protected body Divisor_Type is
entry Poke when not Emptying and Stop_Emptying'Count = 0 is
begin
requeue Release;
end Poke;
entry Release when Release'Count >= 3 or Emptying is
New_Output : access Output;
begin
if not Emptying then
New_Output := new Output;
Emptying := True;
requeue Stop_Emptying;
end if;
end Release;
entry Stop_Emptying when Release'Count = 0 is
begin
Emptying := False;
end Stop_Emptying;
entry Finish when Poke'Count = 0 and Release'Count < 3 is
begin
Emptying := True;
requeue Stop_Emptying;
end Finish;
end Divisor_Type;
protected body Collector_Type is
entry Poke when Emptying is
begin
null;
end Poke;
entry Finish when True is
begin
Ada.Text_IO.Put_Line (Poke'Count'Img);
Emptying := True;
end Finish;
end Collector_Type;
Collector : Collector_Type;
Divisor : Divisor_Type;
task body Input is
begin
Divisor.Poke;
end Input;
task body Output is
begin
Collector.Poke;
end Output;
Cur_Input : access Input;
-- Input value:
Number : Integer := 18;
begin
for I in 1 .. Number loop
Cur_Input := new Input;
end loop;
Divisor.Finish;
Collector.Finish;
end Divide_By_3;
