c math.h pow - Teilen Sie eine Zahl mit 3, ohne die Operatoren *, /, +, -,% zu verwenden




15 Answers

Dies ist eine einfache Funktion, die die gewünschte Operation ausführt. Aber es erfordert den Operator + , so dass Sie nur noch die Werte mit Bit-Operatoren hinzufügen müssen:

// 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; 
}

Als Jim kommentierte, funktioniert das, weil:

  • n = 4 * a + b
  • n / 3 = a + (a + b) / 3
  • So sum += a, n = a + b und iterieren

  • Wenn a == 0 (n < 4) , sum += floor(n / 3); dh 1, if n == 3, else 0

square integer

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

Die Nummer kann signiert oder nicht signiert sein.




log(pow(exp(number),0.33333333333333333333)) /* :-) */



Sie können (plattformabhängig) Inline-Assemblierung verwenden, zB 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;
}



(Hinweis: Siehe Edit 2 unten für eine bessere Version!)

Das ist nicht so schwierig, wie es sich anhört, denn Sie sagten "ohne die [..] + [..] Operatoren zu verwenden ". Siehe unten, wenn Sie verbieten möchten, das Zeichen + zusammen zu verwenden.

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 einfach div_by(100,3) um 100 durch 3 zu teilen.

Bearbeiten : Sie können auch den Operator ++ ersetzen:

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)
}

Edit 2: Etwas schnellere Version ohne Verwendung eines Operators, der die Zeichen + , - , * , / , % .

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 der add Funktion, weil wir den Zeigertyp ohne das Zeichen * nicht bezeichnen können, außer in den Funktionsparameterlisten, wo der Syntaxtyp type[] identisch mit dem type* const .

FWIW, Sie können eine Multiplikationsfunktion leicht mit einem ähnlichen Trick implementieren, um den von 0x55555556 vorgeschlagenen AndreyT Trick zu verwenden:

int mul(int const x, int const y) {
  return sizeof(struct {
    char const ignore[y];
  }[x]);
}



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);
}

Zuerst beachte das

1/3 = 1/4 + 1/16 + 1/64 + ...

Jetzt ist der Rest 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! Wir können jedoch nicht hinzufügen, also müssen wir stattdessen eine Add-Funktion schreiben, die bitweise Operatoren verwendet! 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.

Eine andere Sache zu beachten ist, dass ich zuerst um 30 nach links verschiebe! Dies soll sicherstellen, dass die Fraktionen nicht abgerundet 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 tragen Sie hinzu, dass Sie als Kind gelernt haben!

111
 1011
+0110
-----
10001

Diese Implementierung ist fehlgeschlagen, weil wir nicht alle Terme der Gleichung hinzufügen 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 Reslut von div_by_3(a) = x, dann x <= floor(f(a, i)) < a / 3 . Wenn a = 3k , erhalten wir eine falsche Antwort.




Um eine 32-Bit-Zahl durch 3 zu teilen, kann man sie mit 0x55555556 multiplizieren und dann die oberen 32 Bits des 64-Bit-Ergebnisses nehmen.

Jetzt muss nur noch die Multiplikation mit Bitoperationen und Verschiebungen implementiert werden ...




Es ist wirklich ziemlich 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;

(Ich habe natürlich einige der Programme aus Gründen der Kürze weggelassen.) Wenn der Programmierer es satt hat, alles zu tippen, bin ich mir sicher, dass er oder sie ein separates Programm schreiben könnte, um es für ihn zu generieren. Ich kenne zufällig einen bestimmten Operator, der seine Arbeit immens vereinfachen würde.




Dies ist der klassische Divisionalgorithmus in Base 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);
}



Nicht überprüft, ob diese Antwort bereits veröffentlicht wurde. Wenn das Programm auf Floating-Nummern erweitert werden muss, können die Zahlen mit 10 * Anzahl 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;
}



int div3(int x)
{
  int reminder = abs(x);
  int result = 0;
  while(reminder >= 3)
  {
     result++;

     reminder--;
     reminder--;
     reminder--;
  }
  return result;
}



BC Math in PHP :

<?php
    $a = 12345;
    $b = bcdiv($a, 3);   
?>

MySQL (es ist ein Interview von Oracle)

> SELECT 12345 DIV 3;

Pascal :

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

x86-64 Assembler:

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



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

#!/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));
}
''')



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;
    }



Lösung mit fma , 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);
}

Sehen Sie meine andere Antwort .




zuerst:

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

dann finde 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;    // 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 + , aber jemand implementiert bereits add by bitwise op




Related