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

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

Il s'agit d'une fonction simple qui effectue l'opération souhaitée. Mais cela nécessite l' +opérateur, donc tout ce qu'il vous reste à faire est d'ajouter les valeurs avec des 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 l'a commenté, cela fonctionne, car:

• n = 4 * a + b
• n / 3 = a + (a + b) / 3

• Alors sum += a, n = a + bet itérer

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

Les conditions idiotes 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, déclarez simplement resultas doubleet ajoutez-y le résultat de fmod(number,divisor).

Explication de son fonctionnement

1. Les octets d' fwriteécriture number(le nombre étant 123456 dans l'exemple ci-dessus).
2. rewind réinitialise le pointeur de fichier à l'avant du fichier.
3. freadlit un maximum d ' number"enregistrements" qui sont divisorlongs dans le fichier et renvoie le nombre d'éléments qu'il a lus.

Si vous écrivez 30 octets puis relisez le fichier par unités de 3, vous obtenez 10 "unités". 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;
}

Vous pouvez utiliser un assemblage en ligne (dépendant de la plate-forme), 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;
}

Utilisez itoa pour convertir en une chaîne de base 3. Déposez le dernier trit et reconvertissez 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
}

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

Ce n'est pas aussi compliqué que cela puisse paraître, car vous avez dit "sans utiliser les opérateurs [..] +[..] ". Voir ci-dessous, si vous souhaitez interdire d'utiliser le 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;
}

puis dites simplement div_by(100,3)de diviser 100par 3.

Edit : Vous pouvez continuer et remplacer également l' ++opérateur:

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 l' opérateur qui contient les +, -, *, /, % caractères .

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 addfonction car nous ne pouvons pas désigner 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 implémenter une fonction de multiplication en utilisant une astuce similaire pour utiliser l' 0x55555556astuce proposée par AndreyT :

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

C'est facilement possible sur l' ordinateur Setun .

Pour diviser un entier par 3, décaler vers la droite de 1 place .

Je ne sais pas s'il est 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".

Comme il s'agit d'Oracle, que diriez-vous d'un tableau de recherche de réponses pré-calculées. :-RÉ

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

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

Il ne nous reste plus qu'à additionner ces valeurs décalées d'un bit! Oops! Nous ne pouvons pas ajouter cependant, alors à la place, nous devrons écrire une fonction d'ajout à l'aide d'opérateurs bit à bit! Si vous connaissez les opérateurs au niveau du bit, ma solution devrait être assez simple ... mais juste au cas où vous ne le seriez pas, je vais parcourir un exemple à la fin.

Une autre chose à noter est que je décale d'abord de 30 par gauche! Il s'agit de 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 un complément que vous avez appris enfant!

111
 1011
+0110
-----
10001

Cette implémentation a échoué car 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 alors la retaille de div_by_3(a)= x x <= floor(f(a, i)) < a / 3. Quand a = 3k, nous obtenons une mauvaise réponse.

Pour diviser un nombre 32 bits par 3, on peut le multiplier par 0x55555556puis prendre les 32 bits supérieurs du résultat 64 bits.

Il ne reste plus qu'à implémenter la multiplication à l'aide d'opérations binaires et de décalages ...

Encore une autre solution. Cela devrait gérer tous les entiers (y compris les entiers négatifs) à l'exception de la valeur min d'un entier, qui devrait être traitée comme une exception codée en dur. Cela fait essentiellement la division par soustraction mais uniquement en utilisant des opérateurs de bits (décalages, xor et & et complément). Pour une vitesse plus rapide, il soustrait 3 * (puissance décroissante de 2). En c #, il exécute environ 444 de ces appels DivideBy3 par milliseconde (2,2 secondes pour 1000000 de divisions), donc pas terriblement lent, mais pas aussi rapide qu'un simple x / 3. En comparaison, la belle solution de Coodey est environ 5 fois plus rapide que celle-ci.

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

C'est c # parce que c'est ce que j'avais à portée de main, mais les différences par rapport à c devraient être mineures.

C'est vraiment assez simple.

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;

(J'ai bien sûr omis une partie du programme par souci de concision.) Si le programmeur se lasse de tout taper, je suis sûr qu'il ou elle pourrait écrire un programme distinct pour le générer pour lui. Il se trouve que je connais un certain opérateur /, qui simplifierait énormément son travail.

L'utilisation de compteurs est une solution de base:

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

Il est également facile d'effectuer une fonction de module, vérifiez les commentaires.

Celui-ci est l'algorithme de division classique en 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);
}

Écrivez le programme en Pascal et utilisez le DIV opérateur.

Puisque la question est balisée c, vous pouvez probablement écrire une fonction en Pascal et l'appeler depuis votre programme C; la méthode pour ce faire est spécifique au système.

Mais voici un exemple qui fonctionne sur mon système Ubuntu avec le fp-compilerpackage Free Pascal installé. (Je le fais par entêtement purement déplacé; je ne prétends pas que cela soit utile.)

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

Construire:

fpc divide_by_3.pas && gcc divide_by_3.o main.c -o main

Exemple d'exécution:

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

Je n'ai pas recoupé si cette réponse est déjà publiée. Si le programme doit être étendu à des nombres flottants, les nombres peuvent être multipliés par 10 * nombre de précision nécessaire, puis le code suivant peut être appliqué à nouveau.

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

Cela devrait fonctionner pour n'importe quel diviseur, pas seulement pour trois. Actuellement uniquement pour les non signés, mais l'étendre à signé ne devrait pas être si difficile.

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

Serait-ce de la triche d'utiliser l' /opérateur "en coulisses" en utilisant evalet la concaténation de chaînes?

Par exemple, dans Javacript, vous pouvez faire

function div3 (n) {
    var div = String.fromCharCode(47);
    return eval([n, div, 3].join(""));
}

Utilisation de BC Math en PHP :

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

MySQL (c'est une interview d'Oracle)

> SELECT 12345 DIV 3;

Pascal :

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

langage d'assemblage x86-64:

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

D'abord que j'ai trouvé.

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

EDIT: Désolé, je n'ai pas remarqué la balise C. Mais vous pouvez utiliser l'idée du formatage des chaînes, je suppose ...

Le script suivant génère un programme C qui résout le problème sans utiliser les opérateurs * / + - %:

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

Utilisation du calculateur de nombres Hacker's Delight Magic

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

Où fma est une fonction de bibliothèque standard définie dans l'en- math.htête.

Et cette approche (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;
    }

Je pense que la bonne réponse est:

Pourquoi ne devrais-je pas utiliser un opérateur de base pour effectuer une opération de base?

Solution utilisant la fonction de bibliothèque fma () , fonctionne pour tout nombre positif:

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

Voir ma autre réponse .

Utilisez cblas , inclus dans le cadre de l'accélération OS X.

[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

En règle générale, une solution à ce problème serait:

log(pow(exp(numerator),pow(denominator,-1)))

Première:

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

Ensuite, découvrez comment résoudre x / (1 - y):

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

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

Bien qu'il utilise +, mais quelqu'un implémente déjà add by bitwise op.