Teilen Sie eine Zahl durch 3, ohne * , / , + , - , % Operatoren zu verwenden

Question

Wie würden Sie eine Zahl durch 3 teilen, ohne die *, /, +, -, % Operatoren zu verwenden?

Die Zahl kann positiv oder negativ sein.

Answer 1

Mit BC Math in PHP:

---

MySQL (es handelt sich um ein Interview von Oracle)

> SELECT 12345 DIV 3;

---

Pascal:

a:= 12345;
b:= a div 3;

---

x86-64 Assemblersprache:

mov  r8, 3
xor  rdx, rdx   
mov  rax, 12345
idiv r8

Answer 2

Mit dem Hacker's Delight Magic-Nummernrechner

int durchDreiTeilen(int num)
{
  return (fma(num, 1431655766, 0) >> 32);
}

Wo fma eine Standardbibliotheksfunktion ist, die im Header math.hdefiniert ist.

Answer 3

Zuerst:

x/3 = (x/4) / (1-1/4)

Dann figuren Sie heraus, wie man x/(1 - y) löst:

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;    // benötigt mehr Genauigkeit
    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; // da (1-(1/2)^32) sehr nahe bei 1 ist,
                     // addieren wir 1 statt teilen durch (1-(1/2)^32)
}

Auch wenn es + benutzt, aber jemand hat bereits add mit bitweisen Operationen implementiert.

Answer 4

Das folgende Skript generiert ein C-Programm, das das Problem ohne die Operatoren * / + - % löst:

#!/usr/bin/env python3

print('''#include 
#include 
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; // unmöglich
}
int main()
{
    const int32_t number = 8;
    printf("%d / 3 = %d\n", number, div_by_3(number));
}
''')

Answer 5

Ich denke, die richtige Antwort ist:

Warum sollte ich nicht einen einfachen Operator verwenden, um eine grundlegende Operation durchzuführen?