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

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

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

652
demandé sur 13 revs, 6 users 36%unknown 2012-07-27 23:34:31
la source

30 ответов

il s'agit d'une fonction simple qui exécute l'opération désirée. Mais il nécessite l'opérateur + , donc tout ce que vous avez à faire est d'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é ce travail, parce que:

  • n = 4 * a + b
  • n / 3 = a + (a + b) / 3
  • Donc sum += a , n = a + b , et itérer

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

532
répondu qwertz 2018-08-04 08:57:37
la source

Idiot conditions de l'appel pour un idiot solution:

#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 d'y ajouter le résultat de fmod(number,divisor) .

explication de son fonctionnement

  1. le fwrite écrit number octets (le nombre étant 123456 dans l'exemple ci-dessus).
  2. rewind le pointeur de fichier au début du fichier.
  3. fread lit un maximum de number "enregistrements" qui sont divisor de longueur du fichier, et renvoie le nombre d'éléments qu'il a lu.

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

432
répondu Matteo Italia 2012-07-31 16:28:16
la source
log(pow(exp(number),0.33333333333333333333)) /* :-) */
305
répondu Alan Curry 2012-07-28 04:25:38
la source
#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;
}
200
répondu nos 2012-07-28 00:01:49
la source

vous pouvez utiliser l'assemblage en ligne (dépendant de la plate-forme), par exemple, pour x86: (fonctionne aussi 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
répondu moooeeeep 2016-11-22 11:00:20
la source

Utiliser ltid convertir en base 3 de la chaîne. Laisser tomber le dernier trit et convertir de nouveau à la 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])] = '"151900920"'; // Drop last digit
    return strtol(str, NULL, 3); // Read back result
}
104
répondu Alexandre Jasmin 2014-01-12 13:38:23
la source

(note: Voir Modifier 2 ci-dessous pour une meilleure version!)

ce n'est pas aussi délicat que ça en a l'air, parce que vous avez dit" sans utiliser le [..] + [..] opérateurs ". Voir ci-dessous, si vous voulez interdire l'utilisation du 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 il suffit de dire div_by(100,3) pour diviser 100 par 3 .


Edit : vous pouvez continuer et remplacer l'opérateur ++ ainsi:

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 aucun opérateur qui contient le + , - , * , / , % 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 fonction add parce que nous ne pouvons pas dénoter 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 à utiliser le 0x55555556 truc proposé par AndreyT :

int mul(int const x, int const y) {
  return sizeof(struct {
    char const ignore[y];
  }[x]);
}
57
répondu bitmask 2017-05-23 14:33:24
la source

, Il est facilement possible sur le Setun ordinateur .

pour diviser un entier par 3, shift right par 1 place .

Je ne suis pas sûr qu'il soit strictement possible d'implémenter un compilateur C Conforme sur une telle plateforme. Nous pourrions avoir à étirer les règles un peu, comme interpréter "au moins 8 bits" comme "capable de tenir au moins entiers de -128 à +127".

44
répondu Mechanical snail 2012-07-28 03:07:27
la source

Puisqu'il est D'Oracle, Que diriez-vous d'une table de recherche de réponses pré calculées. :- D

32
répondu Jeff Martin 2012-08-01 09:17:18
la source

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 bit shifted de a! Oops! Nous ne pouvons pas ajouter, donc à la place, nous devrons écrire une fonction add en utilisant des opérateurs bit-wise! Si vous êtes familier avec les opérateurs bit-wise, ma solution devrait sembler assez simple... mais au cas où tu ne le serais pas, je le ferai. marcher à travers un exemple à la fin.

une autre chose à noter est que d'abord je suis parti à 30! 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 porter l'addition que vous avez appris comme un enfant!

111
 1011
+0110
-----
10001

Cette mise en œuvre échec 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 le résultat de div_by_3(a) = x, puis x <= floor(f(a, i)) < a / 3 . Quand a = 3k , on a une mauvaise réponse.

32
répondu tschultz 2012-08-04 18:32:56
la source

pour diviser un nombre de 32 bits par 3 on peut le multiplier par 0x55555556 et ensuite prendre les 32 bits supérieurs du résultat de 64 bits.

maintenant tout ce qui reste à faire est d'implémenter la multiplication en utilisant des opérations de bits et des déplacements...

25
répondu AnT 2012-07-27 23:52:12
la source

encore une autre solution. Cela devrait traiter tous les ints (y compris les ints négatifs) à l'exception de la valeur min d'un int, qui devrait être traitée comme une exception codée dur. Cela fait essentiellement division par soustraction, mais seulement en utilisant des opérateurs de bits (shifts, xor, & et complement). Pour une vitesse plus rapide, il soustrait 3 * (puissances décroissantes de 2). En c#, il exécute environ 444 de ces appels par milliseconde (2,2 secondes pour 1.000.000 divisions), donc pas horriblement lent, mais pas où près aussi rapide qu'un simple x/3. En comparaison, la 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 sous la main, mais les différences avec c devraient être mineures.

18
répondu hatchet 2012-08-02 14:30:17
la source

c'est très facile.

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 brièveté.) Si le programmeur est fatigué de taper tout cela, 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.

15
répondu thedayturns 2012-08-03 04:45:07
la source

utilisant des 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érifier les commentaires.

13
répondu GJ. 2014-01-12 13:52:28
la source

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);
}
11
répondu Eric Bainville 2012-07-29 03:48:33
la source
int div3(int x)
{
  int reminder = abs(x);
  int result = 0;
  while(reminder >= 3)
  {
     result++;

     reminder--;
     reminder--;
     reminder--;
  }
  return result;
}
8
répondu Amir Saniyan 2012-08-01 22:35:03
la source

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

puisque la question est marquée , vous pouvez probablement écrire une fonction en Pascal et l'appeler à partir de votre programme C; la méthode pour le faire est spécifique au système.

Mais voici un exemple qui fonctionne sur mon système Ubuntu avec le paquet gratuit Pascal fp-compiler installé. (Je fais cela par pure égaré entêtement; je ne prétends pas que c'est 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;
}

"1519170920 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
8
répondu Keith Thompson 2012-08-22 03:01:26
la source

N'a pas contre-vérifié 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 et puis le code suivant peut être appliqué de 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;
}
7
répondu PermanentGuest 2012-07-29 14:58:00
la source

cela devrait fonctionner pour n'importe quel diviseur, pas seulement trois. À l'heure actuelle, il ne devrait pas être aussi difficile de l'étendre aux documents non signés.

#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;
}
7
répondu wildplasser 2012-07-31 00:02:05
la source

serait-il malhonnête d'utiliser l'opérateur / en coulisse" en utilisant eval et la concaténation de cordes?

par exemple, en Javaccript, vous pouvez faire

function div3 (n) {
    var div = String.fromCharCode(47);
    return eval([n, div, 3].join(""));
}
7
répondu Peter Olson 2012-08-05 21:03:19
la source

à l'Aide BC Mathématiques dans 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;

x86-64 langage d'assemblage:

mov  r8, 3
xor  rdx, rdx   
mov  rax, 12345
idiv r8
7
répondu Pedro L. 2014-01-12 13:49:43
la source

D'abord, j'ai trouvé.

irb(main):101:0> div3 = -> n { s = '%0' + n.to_s + 's'; (s % '').gsub('   ', ' ').size }
=> #<Proc:[email protected](irb):101 (lambda)>
irb(main):102:0> div3[12]
=> 4
irb(main):103:0> div3[666]
=> 222

EDIT: Désolé, je n'avais pas remarqué le tag C . Mais vous pouvez utiliser l'idée de formatage de chaîne, je suppose...

6
répondu Artem Ice 2012-07-28 03:57:06
la source

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));
}
''')
5
répondu Mechanical snail 2012-08-01 22:29:30
la source

utilisant calculateur de nombres magiques Hacker's Delight

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

FMA est une fonction de bibliothèque standard définie dans math.h en-tête.

5
répondu Jaguar 2012-08-02 12:34:12
la source

Qu'en est-il de 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;
    }
4
répondu mclafee 2012-08-22 11:11:07
la source

je pense que la bonne réponse est:

pourquoi n'utiliserais-je pas un opérateur de base pour effectuer une opération de base?

4
répondu Gregoire 2012-08-23 12:08:02
la source

Solution à l'aide de fma() de la bibliothèque de fonction , fonctionne pour n'importe quel 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 .

4
répondu Eight 2017-05-23 15:26:43
la source

Utiliser cblas , inclus en tant que partie du système d'exploitation OS X d'Accélérer cadre.

[02:31:59] [[email protected] ~]$ 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] [[email protected] ~]$ clang div3.c -framework Accelerate -o div3 && ./div3
123456.000000 * 0.333333 == 41151.957031
3
répondu wjl 2012-07-31 02:13:10
la source

d'abord:

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

puis trouver 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 met déjà en œuvre ajouter par bitwise op

3
répondu Zang MingJie 2012-08-23 15:58:21
la source

OK je pense que nous sommes tous d'accord que ce n'est pas un problème du monde réel. Alors juste pour le plaisir, voici comment le faire avec Ada et multithreading:

with Ada.Text_IO;

procedure Divide_By_3 is

   protected type Divisor_Type is
      entry Poke;
      entry Finish;
   private
      entry Release;
      entry Stop_Emptying;
      Emptying : Boolean := False;
   end Divisor_Type;

   protected type Collector_Type is
      entry Poke;
      entry Finish;
   private
      Emptying : Boolean := False;
   end Collector_Type;

   task type Input is
   end Input;
   task type Output is
   end Output;

   protected body Divisor_Type is
      entry Poke when not Emptying and Stop_Emptying'Count = 0 is
      begin
         requeue Release;
      end Poke;
      entry Release when Release'Count >= 3 or Emptying is
         New_Output : access Output;
      begin
         if not Emptying then
            New_Output := new Output;
            Emptying := True;
            requeue Stop_Emptying;
         end if;
      end Release;
      entry Stop_Emptying when Release'Count = 0 is
      begin
         Emptying := False;
      end Stop_Emptying;
      entry Finish when Poke'Count = 0 and Release'Count < 3 is
      begin
         Emptying := True;
         requeue Stop_Emptying;
      end Finish;
   end Divisor_Type;

   protected body Collector_Type is
      entry Poke when Emptying is
      begin
         null;
      end Poke;
      entry Finish when True is
      begin
         Ada.Text_IO.Put_Line (Poke'Count'Img);
         Emptying := True;
      end Finish;
   end Collector_Type;

   Collector : Collector_Type;
   Divisor : Divisor_Type;

   task body Input is
   begin
      Divisor.Poke;
   end Input;

   task body Output is
   begin
      Collector.Poke;
   end Output;

   Cur_Input : access Input;

   -- Input value:
   Number : Integer := 18;
begin
   for I in 1 .. Number loop
      Cur_Input := new Input;
   end loop;
   Divisor.Finish;
   Collector.Finish;
end Divide_By_3;
2
répondu flyx 2012-08-23 17:34:24
la source

Autres questions sur c math division