Comment diviser un nombre par 3 sans utiliser *
, /
, +
, -
, %
, les opérateurs?
Le numéro peut être signé ou non signé.
Comment diviser un nombre par 3 sans utiliser *
, /
, +
, -
, %
, les opérateurs?
Le numéro peut être signé ou non signé.
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 + b
et itérez
Quand a == 0 (n < 4)
, sum += floor(n / 3);
c'est-à-dire 1, if n == 3, else 0
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
fwrite
écrit number
octets (le numéro étant 123456 dans l'exemple ci-dessus).rewind
réinitialise le pointeur de fichier à l'avant du fichier.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
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 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;
}
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
}
(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
.
++
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)
}
+
,-
,*
,/
,%
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]);
}
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".
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.
Puisque c'est d'Oracle, que diriez-vous d'une table de recherche de réponses pré calculées. :-RÉ