Divisez un nombre par 3 sans utiliser les opérateurs *, /, +, -, %
https://stackoverflow.com//questions/11694546
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Comment diviseriez-vous un nombre par 3 sans utiliser *, /, +, -, %, les opérateurs?
Le numéro peut être signé ou non.
La solution
C'est un fonction simple qui effectue l'opération désirée.Mais cela nécessite le + opérateur, il ne vous reste donc plus qu'à ajouter les valeurs avec les opérateurs 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 + bn / 3 = a + (a + b) / 3Donc
sum += a,n = a + b, et itérerQuand
a == 0 (n < 4),sum += floor(n / 3);c'est à dire.1,if n == 3, else 0
Autres conseils
Des 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 result comme double et on y ajoute le résultat de fmod(number,divisor).
Explication de son fonctionnement
- Le
fwriteécritnumberoctets (le nombre étant 123456 dans l’exemple ci-dessus). rewindréinitialise le pointeur de fichier au début du fichier.freadlit au maximumnumberdes « enregistrements » qui sontdivisoren longueur du fichier et renvoie le nombre d'éléments 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 assembly en ligne (en fonction 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;
}
Utiliser itoa pour convertir en chaîne de base 3.Lâchez le dernier trit et reconvertissez-vous 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é qu'il y paraît, car vous avez dit "sans utiliser le [..] + [..] les opérateurs".Voir ci-dessous, si vous souhaitez interdire l'utilisation du + personnage 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 également :
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)
}
Modifier 2 :Version légèrement plus rapide sans utiliser d'opérateur contenant 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 add fonction 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 le 0x55555556 astuce 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 le Ordinateur de configuration.
Pour diviser un entier par 3, décaler vers la droite d'une 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 étendre un peu les règles, comme interpréter « au moins 8 bits » comme « capable de contenir au moins des nombres entiers de -128 à +127 ».
Puisqu'il s'agit d'Oracle, que diriez-vous d'une table de recherche de réponses pré-calculées.:-D
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, notons 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 légèrement décalées de a !Oops!Cependant, nous ne pouvons pas ajouter, nous devrons donc écrire une fonction d'ajout en utilisant des opérateurs au niveau du bit !Si vous êtes familier avec les opérateurs bit-wise, ma solution devrait paraître assez simple...mais juste au cas où ce ne serait pas le cas, je vais vous donner un exemple à la fin.
Une autre chose à noter est que je décale d'abord vers la gauche de 30 !Cela permet de s'assurer que les fractions ne soient 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 ajout que vous avez appris étant enfant !
111
1011
+0110
-----
10001
Cette mise en œuvre échoué car on ne peut pas additionner 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 résultat de div_by_3(a) = x, alors x <= floor(f(a, i)) < a / 3.Quand a = 3k, nous obtenons une mauvaise réponse.
Pour diviser un nombre de 32 bits par 3, on peut le multiplier par 0x55555556 puis prenez les 32 bits supérieurs du résultat 64 bits.
Il ne reste plus qu'à implémenter la multiplication à l'aide d'opérations sur bits 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 minimale d'un int, qui devrait être traitée comme une exception codée en dur.Cela effectue essentiellement une division par soustraction, mais en utilisant uniquement des opérateurs de bits (shifts, xor et & et complément).Pour une vitesse plus rapide, il soustrait 3* (puissances décroissantes de 2).En C#, il exécute environ 444 de ces appels DivideBy3 par milliseconde (2,2 secondes pour 1 000 000 de divisions), donc pas terriblement lent, mais loin d'être aussi rapide qu'un simple x/3.En comparaison, la solution intéressante 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 par rapport à c devraient être mineures.
C'est vraiment très 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 en a assez de tout taper, je suis sûr qu'il pourrait écrire un programme séparé pour le générer pour lui.Il se trouve que je connais un certain opérateur, /, cela 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 taguée c, vous pouvez probablement écrire une fonction en Pascal et l'appeler depuis votre programme C ;la méthode pour y parvenir est spécifique au système.
Mais voici un exemple qui fonctionne sur mon système Ubuntu avec Free Pascal fp-compiler paquet installé.(Je fais cela par simple entêtement 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 vérifié si cette réponse est déjà publiée.Si le programme doit être étendu aux nombres flottants, les nombres peuvent être multipliés par 10*nombre de précision nécessaire, puis le code suivant peut être à nouveau appliqué.
#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 trois.Actuellement uniquement pour les non signés, mais l'étendre aux signés 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 le / opérateur "en coulisses" en utilisant eval et concaténation de chaînes ?
Par exemple, en Javascript, vous pouvez faire
function div3 (n) {
var div = String.fromCharCode(47);
return eval([n, div, 3].join(""));
}
En utilisant Mathématiques de la Colombie-Britannique dans PHP:
<?php
$a = 12345;
$b = bcdiv($a, 3);
?>
MySQL (c'est une interview d'Oracle)
> SELECT 12345 DIV 3;
a:= 12345;
b:= a div 3;
Langage assembleur x86-64 :
mov r8, 3
xor rdx, rdx
mov rax, 12345
idiv r8
C'est d'abord celui 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
MODIFIER: Désolé, je n'ai pas remarqué l'étiquette 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));
}
''')
En utilisant 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 math.h entête.
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;
}
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 ?
Solution utilisant 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);
}
Utiliser cblas, inclus dans le cadre Accelerate d'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
D'abord:
x/3 = (x/4) / (1-1/4)
Découvrez ensuite 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à l'ajout par opération au niveau du bit.
D'accord, je pense que nous sommes tous d'accord sur le fait que ce n'est pas un problème réel.Alors juste pour le fun, voici comment faire avec Ada et le 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;
