Dividere un numero per 3 senza usare *, /, +, -,% operatori
https://stackoverflow.com//questions/11694546
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Come si dividerebbe un numero per 3 senza utilizzare *, /, +, -, %, Operatori?
Il numero può essere firmato o non firmato.
Soluzione
Questo è un Semplice funzione che esegue l'operazione desiderata.Ma richiede l'operatore +, quindi tutto ciò che hai lasciato per fare è aggiungere i valori con gli operatori di bit:
// 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;
}
AS JIM ha commentato questo funziona, perché:
- .
-
n = 4 * a + b -
n / 3 = a + (a + b) / 3 -
così
sum += a,n = a + be iterare -
Quando
a == 0 (n < 4),sum += floor(n / 3);I.e. 1,if n == 3, else 0
Altri suggerimenti
Le condizioni idiota richiedono una soluzione idiota:
#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;
}
Se è necessario anche la parte decimale, basta dichiarare result come double e aggiungere ad esso il risultato di fmod(number,divisor).
Spiegazione di come funziona
- .
- Il
fwritescrive bytenumber(numero di 123456 nell'esempio sopra). -
rewindReimposta il puntatore del file nella parte anteriore del file. -
freadlegge un massimo dinumber"Records" che sonodivisorin lunghezza del file e restituisce il numero di elementi che ha letto.
Se si scrivono 30 byte, quindi leggere il file in unità di 3, ottieni 10 "unità".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;
}
È possibile utilizzare Assemblea in linea (Platform Dependent), ad esempio, per X86: (funziona anche per numeri negativi)
#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;
}
Usa iToa da convertire in una stringa di base 3.Drop the Last Trit e convertire torna alla 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
}
(Nota: vedere Modifica 2 sotto per una versione migliore!)
Questo non è così complicato come suona, perché hai detto "senza usare il [..] + [..] Operatori ". Vedi sotto, se vuoi vietare di utilizzare il carattere + tutti insieme.
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;
}
Quindi dire solo div_by(100,3) per dividere 100 da 3.
.
Modifica : è possibile accedere e sostituire anche l'operatore ++:
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)
}
.
Modifica 2: versione leggermente più veloce senza utilizzare alcun operatore che contiene il +, -, *, /, % caratteri .
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;
}
Utilizziamo il primo argomento della funzione add perché non possiamo indicare il tipo di puntatori senza utilizzare il carattere *, ad eccezione degli elenchi dei parametri delle funzioni, in cui la sintassi type[] è identica a type* const.
fwiw, è possibile implementare facilmente una funzione di moltiplicazione utilizzando un trucco simile per utilizzare il trucco 0x55555556 proposto da Andreyt : < / P >.
int mul(int const x, int const y) {
return sizeof(struct {
char const ignore[y];
}[x]);
}
È facilmente possibile su Computer Setun .
Per dividere un numero intero per 3, Sposta a destra di 1 posto .
Non sono sicuro che sia rigorosamente possibile implementare un compilatore C conforme su tale piattaforma però.Potremmo dover estendere le regole un po ', come interpretare "almeno 8 bit" come "in grado di tenere almeno numeri interi da -128 a +127".
Dal momento che è da Oracle, che ne dici di una tabella di ricerca di risposte pre calcolate.MrGreen
Ecco la mia soluzione:
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);
}
In primo luogo, nota che
1/3 = 1/4 + 1/16 + 1/64 + ...
Ora, il resto è semplice!
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 + ...
Ora tutto ciò che dobbiamo fare è aggiungere insieme questi bit spostati valori di A!Oops!Non possiamo aggiungere però, quindi invece, dovremo scrivere una funzione Aggiungi usando gli operatori bit-saggi!Se hai familiarità con gli operatori bit-saggi, la mia soluzione dovrebbe sembrare abbastanza semplice ... ma solo nel caso non lo sei, passerò attraverso un esempio alla fine.
Un'altra cosa da notare è che prima che mi spostassi a sinistra entro il 30!Questo per assicurarsi che le frazioni non vengano arrotondate.
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!
È semplicemente coniuga aggiunta che hai imparato da bambino!
111
1011
+0110
-----
10001
Questa implementazione Failed perché non possiamo aggiungere tutti i termini dell'equazione:
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
Supponiamo che il resUt di div_by_3(a)= X, quindi x <= floor(f(a, i)) < a / 3.Quando a = 3k, otteniamo una risposta sbagliata.
Per dividere un numero a 32 bit per 3 si può moltiplicare da 0x55555556 e quindi prendere i 32 bit superiori del risultato di 64 bit.
Ora tutto ciò che rimane da fare è implementare la moltiplicazione utilizzando le operazioni di bit e spostamenti ...
Ancora un'altra soluzione.Ciò dovrebbe gestire tutti gli interi (compresi gli intercetti negativi), ad eccezione del valore minimo di un INT, che dovrebbe essere gestito come un'eccezione rigida.Questo fondamentalmente fa divisione per sottrazione, ma solo usando gli operatori di bit (spostamenti, xor, e complemento).Per una velocità più veloce, sottrae 3 * (diminuendo poteri di 2).In C #, esegue circa 444 di queste chiamate Divideby3 per millisecondo (2,2 secondi per 1.000.000 divide), quindi non orrendolmente lento, ma no dove vicino a un semplice X / 3.In confronto, la bella soluzione di Cooody è di circa 5 volte più veloce di questa.
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;
}
Questo è C # perché è quello che ho avuto a portata di mano, ma le differenze da C dovrebbero essere minorenne.
È davvero abbastanza 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;
(Ho ovviamente omesso un po 'del programma per il gusto di Brevity.) Se il programmatore si stanca di digitare tutto questo, sono sicuro che lui o lei potesse scrivere un programma separato per generarlo per lui.Mi capita di essere consapevole di un certo operatore, /, che semplificherebbe immensamente il suo lavoro.
Utilizzo dei contatori è una soluzione di 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
}
}
È anche facile da eseguire una funzione di moduli, controllare i commenti.
Questo è l'algoritmo di divisione classica nella 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);
}
Scrivi il programma in Pascal e utilizzare l'operatore DIV.
Dal momento che la domanda è taggata c probabilmente può scrivere una funzione a Pascal e chiamarlo dal tuo programma C;Il metodo per farlo è specifico del sistema.
Ma ecco un esempio che funziona sul mio sistema Ubuntu con il pacchetto fp-compiler Pascal gratuito installato.(Lo sto facendo fuori da peli testardaggine sbalavoli; non prendo rivendicazione che questo sia 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;
}
fpc divide_by_3.pas && gcc divide_by_3.o main.c -o main
Esecuzione del campione:
$ ./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;
}
Non ha verificato se questa risposta è già pubblicata.Se il programma deve essere esteso ai numeri flottanti, i numeri possono essere moltiplicati per 10 * Numero di precisione necessari e quindi il seguente codice può essere applicato.
#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;
}
Questo dovrebbe funzionare per qualsiasi divisore, non solo tre.Attualmente solo per non firmato, ma che si estende a firmato non dovrebbe essere così 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;
}
Aiutare a utilizzare l'operatore / "dietro le quinte" utilizzando eval e String Concatenation?
Ad esempio, in JavaCript, puoi fare
function div3 (n) {
var div = String.fromCharCode(47);
return eval([n, div, 3].join(""));
}
Prima che ho trovato.
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
Modifica: Siamo spiacenti, non ho notato il tag C.Ma puoi usare l'idea della formattazione della stringa, immagino ...
Il seguente script genera un programma C che risolve il problema senza utilizzare gli operatori * / + - %:
#!/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));
}
''')
Usando Delight del hacker Magic Number Calculator
int divideByThree(int num)
{
return (fma(num, 1431655766, 0) >> 32);
}
Dove FMA è una funzione di libreria standard definita nell'intestazione math.h.
Che ne dici di questo approccio (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;
}
Penso che la risposta giusta sia:
Perché non dovrei usare un operatore di base per eseguire un'operazione di base?
soluzione usando FMA () Funzione libreria , funziona per qualsiasiNumero positivo:
#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);
}
Utilizzare cblas , inclusoCome parte del quadro accelerato di 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
Primo:
x/3 = (x/4) / (1-1/4)
Quindi capire come risolvere 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))
con 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)
}
Sebbene utilizzi +, ma qualcuno già implementa Aggiungi bitWise op.
Va bene Penso che siamo tutti d'accordo sul fatto che questo non è un problema del mondo reale.Quindi, solo per divertimento, ecco come farlo con ADA e 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;
