Dividir un número por 3 sin utilizar los operadores *, /, +, -, %
https://stackoverflow.com//questions/11694546
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
¿Cómo dividirías un número entre 3 sin usar? *, /, +, -, %, operadores?
El número puede estar firmado o sin firmar.
Solución
Esto es un función sencilla que realiza la operación deseada.Pero requiere la + operador, así que todo lo que te queda por hacer es sumar los valores con operadores 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;
}
Como Jim comentó, esto funciona porque:
n = 4 * a + bn / 3 = a + (a + b) / 3Entonces
sum += a,n = a + b, e iterarCuando
a == 0 (n < 4),sum += floor(n / 3);es decir.1,if n == 3, else 0
Otros consejos
Condiciones idiotas exigen una solución 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;
}
Si también se necesita la parte decimal, simplemente declara result como double y le sumamos el resultado de fmod(number,divisor).
Explicación de cómo funciona.
- El
fwriteescribenumberbytes (el número es 123456 en el ejemplo anterior). rewindrestablece el puntero del archivo al frente del archivo.freadlee un máximo denumber"registros" que sondivisorde longitud del archivo y devuelve el número de elementos que leyó.
Si escribe 30 bytes y luego vuelve a leer el archivo en unidades de 3, obtendrá 10 "unidades".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;
}
Puede usar (dependiente de la plataforma) ensamblaje en línea, por ejemplo, para x86: (también funciona para números negativos)
#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;
}
Use itoa para convertir a una cadena de base 3.Drop la última trit y convierte de nuevo a 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])] = '\0'; // Drop last digit
return strtol(str, NULL, 3); // Read back result
}
(nota:¡consulte la Edición 2 a continuación para obtener una versión mejor!)
Esto no es tan complicado como parece, porque dijiste "sin usar el [..] + [..] operadores".Consulte a continuación si desea prohibir el uso de + personaje todos juntos.
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;
}
entonces solo di div_by(100,3) para dividir 100 por 3.
Editar:Puedes continuar y reemplazar el ++ operador también:
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)
}
Edición 2:Versión un poco más rápida sin utilizar ningún operador que contenga el +,-,*,/,% caracteres.
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;
}
Usamos el primer argumento de la add función porque no podemos denotar el tipo de punteros sin usar el * carácter, excepto en las listas de parámetros de funciones, donde la sintaxis type[] es idéntico a type* const.
FWIW, puedes implementar fácilmente una función de multiplicación usando un truco similar para usar el 0x55555556 truco propuesto por AndreyT:
int mul(int const x, int const y) {
return sizeof(struct {
char const ignore[y];
}[x]);
}
Es fácilmente posible en la Setun Computer .
Para dividir un entero por 3, cambiar a la derecha por 1 lugar .
No estoy seguro de si es estrictamente posible implementar un compilador de C conforme a una plataforma de este tipo.Es posible que tengamos que estirar las reglas un poco, como interpretar "al menos 8 bits" como "capaz de mantener al menos enteros de -128 a +127".
Dado que es de Oracle, qué hay de una tabla de búsqueda de respuestas pre calculadas.:-D
Aquí está mi solución:
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);
}
Primero, tenga en cuenta que
1/3 = 1/4 + 1/16 + 1/64 + ...
¡Ahora el resto es sencillo!
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 + ...
¡Ahora todo lo que tenemos que hacer es sumar estos valores de bits desplazados de a!¡Ups!Sin embargo, no podemos sumar, por lo que tendremos que escribir una función de suma usando operadores bit a bit.Si está familiarizado con los operadores bit a bit, mi solución debería parecer bastante simple...pero en caso de que no sea así, le mostraré un ejemplo al final.
¡Otra cosa a tener en cuenta es que primero me desplazo a la izquierda 30!Esto es para asegurar que las fracciones no se redondeen.
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!
¡Es simplemente llevar la suma que aprendiste cuando eras niño!
111
1011
+0110
-----
10001
Esta implementación fallido porque no podemos sumar todos los términos de la ecuación:
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
Supongamos que el resultado de div_by_3(a) =x, entonces x <= floor(f(a, i)) < a / 3.Cuando a = 3k, obtenemos una respuesta incorrecta.
Para dividir un número de 32 bits por 3 uno puede multiplicarlo por 0x55555556 y luego tomar los 32 bits superiores del resultado de 64 bits.
Ahora, todo lo que queda por hacer es implementar la multiplicación utilizando operaciones de bits y turnos ...
otra solución.Esto debe manejar todos los INT (incluidos los INT negativos), excepto el valor mínimo de un INT, que deberían manejarse como una excepción codificada.Básicamente, esto hace la división por resta, pero solo usando operadores de bits (turnos, XOR y y complemento).Para una velocidad más rápida, resta 3 * (potencias decrecientes de 2).En C #, ejecuta alrededor de 444 de estas llamadas Divideby3 por milisegundo (2,2 segundos para 1,000,000 divides), por lo que no es horrible lentamente, pero no, en su lugar tan rápido como simple X / 3.En comparación, la buena solución de Coodey es aproximadamente 5 veces más rápida que esta.
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;
}
Este es C # porque eso es lo que tenía a mano, pero las diferencias de C debería ser menor.
es realmente bastante fácil.
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;
(Por supuesto, he omitido parte del programa por el bien de la brevedad). Si el programador se cansa de escribir todo esto, estoy seguro de que él o ella podría escribir un programa separado para generarlo para él.Sengo que estoy al tanto de un cierto operador, /, que simplificaría enormemente su trabajo.
Uso de contadores es una solución básica:
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
}
}
También es fácil realizar una función de módulo, verifique los comentarios.
Este es el algoritmo de la división clásica en la 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);
}
Escribe el programa en Pascal y usa el DIV operador.
Dado que la pregunta está etiquetada C, probablemente puedas escribir una función en Pascal y llamarla desde tu programa C;el método para hacerlo es específico del sistema.
Pero aquí hay un ejemplo que funciona en mi sistema Ubuntu con Free Pascal. fp-compiler paquete instalado.(Estoy haciendo esto por pura terquedad fuera de lugar;No pretendo que esto sea útil.)
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;
}
Para construir:
fpc divide_by_3.pas && gcc divide_by_3.o main.c -o main
Ejecución de muestra:
$ ./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;
}
No se verificó de nuevo si esta respuesta ya está publicada.Si el programa debe extenderse a los números flotantes, los números se pueden multiplicar por 10 * número de precisión necesaria y luego se puede aplicar nuevamente el siguiente código.
#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;
}
Esto debería funcionar para cualquier divisor, no solo tres.Actualmente solo para sin firmar, pero extenderlo para firmar no debe ser tan difícil.
#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;
}
¿Sería una trampa usar el / operador "entre bastidores" mediante el uso eval y concatenación de cadenas?
Por ejemplo, en Javacript, puedes hacer
function div3 (n) {
var div = String.fromCharCode(47);
return eval([n, div, 3].join(""));
}
primero que he llegado.
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
Editar: lo siento, no noté el etiqueta C.Pero puedes usar la idea sobre el formato de cadena, supongo ...
El siguiente script genera un programa en C que resuelve el problema sin utilizar los operadores. * / + - %:
#!/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 Hacker's Delight Magic Number Calculator
int divideByThree(int num)
{
return (fma(num, 1431655766, 0) >> 32);
}
Donde fma es una función de biblioteca estándar definida en el encabezado de math.h.
¿Qué tal este enfoque (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;
}
Creo que la respuesta correcta es:
¿Por qué no usaría un operador básico para hacer una operación básica?
Solución usando FMA () Función de la biblioteca , funciona para cualquierNúmero 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);
}
Use clalas , incluidaComo parte del marco acelerado de 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
primero:
x/3 = (x/4) / (1-1/4)
Averigua cómo resolver 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)
}
Aunque utiliza +, pero alguien ya implementa agregar de BITWISE OP.
Está bien, creo que todos estamos de acuerdo en que este no es un problema del mundo real.Así que solo por diversión, aquí está cómo hacerlo con ADA y MultiShReading:
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;
