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

Ziemlich amüsiert, dass niemand mit einer allgemeinen Abteilung geantwortet hat:

/* Finden Sie für die gegebene Ganzzahl die Position des MSB */
int find_msb_loc(unsigned int n)
{
    if (n == 0)
        return 0;

    int loc = sizeof(n)  * 8 - 1;
    while (!(n & (1 << loc)))
        loc--;
    return loc;
}

/* Nehmen Sie an, dass sowohl a als auch b positiv sind, geben Sie a/b zurück */
int divide_bitwise(const unsigned int a, const unsigned int b)
{
    int int_size = sizeof(unsigned int) * 8;
    int b_msb_loc = find_msb_loc(b);

    int d = 0; // Dividende
    int r = 0; // Erinnerung
    int t_a = a;
    int t_a_msb_loc = find_msb_loc(t_a);
    int t_b = b << (t_a_msb_loc - b_msb_loc);

    int i;
    for(i = t_a_msb_loc; i >= b_msb_loc; i--)  {
        if (t_a > t_b) {
            d = (d << 1) | 0x1;
            t_a -= t_b; // Keine bitweise Operation
            t_b = t_b >> 1;
         }
        else if (t_a == t_b) {
            d = (d << 1) | 0x1;
            t_a = 0;
        }
        else { // t_a < t_b
            d = d << 1;
            t_b = t_b >> 1;
        }
    }

    r = t_a;
    printf("==> %d %d\n", d, r);
    return d;
}

Die bitweise Addition wurde bereits in einer der Antworten gegeben, daher überspringen wir sie.

Answer 2

Alle Antworten sind wahrscheinlich nicht das, was der Interviewer hören wollte:

Meine Antwort:

"Das würde ich nie tun, wer wird mich für solche dummen Dinge bezahlen. Niemand wird davon profitieren, es ist nicht schneller, es ist nur albern. Prozessordesigner müssen das wissen, aber es muss dann für alle Zahlen funktionieren, nicht nur für die Division durch 3."

Answer 3

Warum wenden wir nicht einfach die im College studierte Definition an? Das Ergebnis ist vielleicht ineffizient, aber klar, da die Multiplikation nur eine rekursive Subtraktion ist und die Subtraktion eine Addition ist. Dann kann die Addition durch eine rekursive XOR/AND-Logikport-Kombination durchgeführt werden.

#include <stdio.h>

int add(int a, int b){
   int rc;
   int carry;
   rc = a ^ b; 
   carry = (a & b) << 1;
   if (rc & carry) 
      return add(rc, carry);
   else
      return rc ^ carry; 
}

int sub(int a, int b){
   return add(a, add(~b, 1)); 
}

int div( int D, int Q )
{
/* lets do only positive and then
 * add the sign at the end
 * inversion needs to be performed only for +Q/-D or -Q/+D
 */
   int result=0;
   int sign=0;
   if( D < 0 ) {
      D=sub(0,D);
      if( Q<0 )
         Q=sub(0,Q);
      else
         sign=1;
   } else {
      if( Q<0 ) {
         Q=sub(0,Q);
         sign=1;
      } 
   }
   while(D>=Q) {
      D = sub( D, Q );
      result++;
   }
/*
* Apply sign
*/
   if( sign )
      result = sub(0,result);
   return result;
}

int main( int argc, char ** argv ) 
{
    printf( "2 plus 3=%d\n", add(2,3) );
    printf( "22 div 3=%d\n", div(22,3) );
    printf( "-22 div 3=%d\n", div(-22,3) );
    printf( "-22 div -3=%d\n", div(-22,-3) );
    printf( "22 div 03=%d\n", div(22,-3) );
    return 0;
}

Wie jemand sagt... mach erstmal dass das funktioniert. Beachten Sie, dass der Algorithmus auch für negative Q funktionieren sollte...

Answer 4

#include 

typedef struct { char a,b,c; } Triple;

unsigned long div3(Triple *v, char *r) {
  if ((long)v <= 2)  
    return (unsigned long)r;
  return div3(&v[-1], &r[1]);
}

int main() {
  unsigned long v = 21; 
  int r = div3((Triple*)v, 0); 
  printf("%ld / 3 = %d\n", v, r); 
  return 0;
}

Answer 5

Wenn Sie sich an die Standard-Schulmethode der Division erinnern und dies im Binärcode tun, werden Sie feststellen, dass Sie im Falle von 3 nur eine begrenzte Anzahl von Werten dividieren und subtrahieren (in diesem Fall von 0 bis 5). Diese können mit einer Switch-Anweisung behandelt werden, um arithmetische Operatoren loszuwerden.

static unsigned lamediv3(unsigned n)
{
  unsigned result = 0, remainder = 0, mask = 0x80000000;

  // Gehe durch alle Bits von n von MSB bis LSB.
  for (int i = 0; i < 32; i++, mask >>= 1)
  {
    result <<= 1;
    // Schiebe das nächste Bit von n in den Rest.
    remainder = remainder << 1 | !!(n & mask);

    // Teile den Rest durch 3, aktualisiere das Ergebnis und den Rest.
    // Wenn der Rest kleiner als 3 ist, bleibt er intakt.
    switch (remainder)
    {
    case 3:
      result |= 1;
      remainder = 0;
      break;

    case 4:
      result |= 1;
      remainder = 1;
      break;

    case 5:
      result |= 1;
      remainder = 2;
      break;
    }
  }

  return result;
}

#include 

int main()
{
  // Überprüfen Sie alle möglichen Werte eines 32-Bit-Unsigned-Integers.
  unsigned i = 0;

  do
  {
    unsigned d = lamediv3(i);

    if (i / 3 != d)
    {
      printf("failed for %u: %u != %u\n", i, d, i / 3);
      return 1;
    }
  }
  while (++i != 0);
}