Question Diviser un nombre par 3 sans utiliser les opérateurs *, /, +, -,%


Comment diviser un nombre par 3 sans utiliser *, /, +, -, %, les opérateurs?

Le numéro peut être signé ou non signé.


650


origine


Réponses:


C'est un fonction simple qui effectue l'opération souhaitée. Mais cela nécessite le + opérateur, il ne vous reste plus qu'à ajouter les valeurs avec les opérateurs de bits:

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

Comme Jim a commenté cela fonctionne parce que:

  • n = 4 * a + b
  • n / 3 = a + (a + b) / 3 
  • So sum += a, n = a + bet itérez

  • Quand a == 0 (n < 4), sum += floor(n / 3); c'est-à-dire 1, if n == 3, else 0


530



Les conditions idiotiques appellent une solution idiote:

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

Si la partie décimale est également nécessaire, il suffit de déclarer result comme double et ajoutez-y le résultat de fmod(number,divisor).

Explication de comment cela fonctionne

  1. le fwrite écrit number octets (le numéro étant 123456 dans l'exemple ci-dessus).
  2. rewind réinitialise le pointeur de fichier à l'avant du fichier.
  3. fread lit un maximum de number "records" qui sont divisor en longueur du fichier, et renvoie le nombre d'éléments lus.

Si vous écrivez 30 octets puis relisez le fichier en unités de 3, vous obtenez 10 "unités". 30/3 = 10


429



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

304



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

199



Vous pouvez utiliser un assemblage en ligne (dépendant de la plateforme), par exemple, pour x86: (fonctionne également pour les nombres négatifs)

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

111



Utilisation Itoa convertir en une chaîne de base 3. Déposez le dernier trit et convertir en base 10.

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

102



(note: voir Edit 2 ci-dessous pour une meilleure version!)

Ce n'est pas aussi difficile que cela puisse paraître, parce que vous avez dit "sans utiliser le [..] + [..] les opérateurs"Voir ci-dessous, si vous voulez interdire l'utilisation de + caractère tous ensemble.

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

alors dis juste div_by(100,3) diviser 100 par 3.


modifier: Vous pouvez continuer et remplacer le ++ opérateur aussi:

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: Version légèrement plus rapide sans utiliser d'opérateur qui contient le +,-,*,/,%  personnages.

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

Nous utilisons le premier argument de la add fonction parce que nous ne pouvons pas indiquer le type de pointeurs sans utiliser le * caractère, sauf dans les listes de paramètres de fonction, où la syntaxe type[] est identique à type* const.

FWIW, vous pouvez facilement mettre en œuvre une fonction de multiplication en utilisant un truc similaire pour utiliser le 0x55555556 astuce proposée par AndreyT:

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

56



Il est facilement possible sur le Setun ordinateur.

Pour diviser un nombre entier par 3, passer à droite par 1 place.

Je ne suis pas sûr qu'il soit strictement possible d'implémenter un compilateur C conforme sur une telle plate-forme. Nous devrons peut-être étirer un peu les règles, comme interpréter "au moins 8 bits" comme "capable de contenir au moins des entiers de -128 à +127".


44



Voici ma solution:

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

D'abord, notez que

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

Maintenant, le reste est simple!

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 + ...

Maintenant tout ce que nous avons à faire est d'additionner ces valeurs de bits décalées d'un! Oops! Nous ne pouvons pas ajouter cependant, donc à la place, nous devrons écrire une fonction add en utilisant des opérateurs bit-wise! Si vous êtes familier avec les opérateurs peu pointus, ma solution devrait sembler assez simple ... mais juste au cas où vous ne l'êtes pas, je vais passer en revue un exemple à la fin.

Une autre chose à noter est que d'abord je décale à gauche par 30! C'est pour s'assurer que les fractions ne sont pas arrondies.

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!

C'est tout simplement porter plus que vous avez appris comme un enfant!

111
 1011
+0110
-----
10001

Cette implémentation échoué parce que nous ne pouvons pas ajouter tous les termes de l'équation:

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

Supposons que le reslut de div_by_3(a) = x, alors x <= floor(f(a, i)) < a / 3. Quand a = 3k, nous avons une mauvaise réponse.


32



Puisque c'est d'Oracle, que diriez-vous d'une table de recherche de réponses pré calculées. :-RÉ


31