Calcular n% 12

27

Calcule el nmódulo 12para un entero de 32 bits sin signo.

Las normas:

  • Debe funcionar para todos nentre 0 y 23. Otros números opcionales.
  • Solo debe usar cualquiera de los operadores +-*, ~&^|o <<, >>como se define comúnmente en unidades de 32 bits.
  • Puede usar un número arbitrario de uniones constantes.
  • No puede utilizar ningún tipo de punteros, incluidas las matrices, ni ninguna ifdeclaración, incluidas las cosas que se compilan con declaraciones if como operadores ternarios u operadores "mayores que".

La puntuación:

  • Los operadores + -y los operadores bit a bit ~ & ^ | << >>(NOT, AND, XOR, OR, bit shift ) dan una puntuación de 1, *da una puntuación de 2.
  • La puntuación total más baja gana.
nbubis
fuente
66
Es posible que desee definir los operadores para usuarios de lenguajes que no sean C / Java. Entiendo +-*son sumar, restar, multiplicar; ~&^|son bit a bit NOT, AND, XOR, OR; y << >>son bithifts
Level River St
@steveverrill - gracias. Esa es de hecho la intención.
nbubis
Puedo usar for i in x:y:z, .dostuff?
Agradable
¿Puedo establecer una variable igual a un valor para usar en una expresión?
xnor
44
la mayoría de los compiladores se optimizarán n % 12para una multiplicación y un cambio como en el deleite de los hackers, por lo que esto es trivial, solo
envíe

Respuestas:

29

4 4

(El lenguaje es irrelevante)

n-((48&(11-n))>>2)

¡Cortejar! Tengo que 4.

11-n asegurará que todos los bits de orden superior estén establecidos si y solo si n> = 12.

48&(11-n) == si n> 11 entonces 48 más 0

(48&(11-n))>>2 == si n> 11 entonces 12 más 0

n-((48&(11-n))>>2) es la respuesta

isaacg
fuente
1
Aww shucks, me ganaste con este enfoque! Estaba a solo unos minutos de publicar n - (((11 - n) & 0xC0000000) >> 28). Bien hecho, no creo que se pueda hacer en menos de cuatro.
Runer112
1
@ Runner112 Sí, esperaba que nadie me ganara mientras lo publicaba. Bien hecho por encontrarlo para ti, sin embargo
isaacg
1
Impresionante :) 4 es de hecho un logro.
nbubis
11

4 4

Una solución con una tabla de búsqueda (se ve hacia arriba i ^ (i % 12)):

i ^ (0x1d4c000 >> (i & 0xfc) & 30)

4 4

Aquí hay otra solución con 4 operaciones:

i - ((0xffff >> (i - 12)) & 12)

Se supone que el operando de conteo de los cambios de bits se toma implícitamente en el mod 32, x >> -1es decir, es el mismo que x >> 31.

5 5

Otro enfoque, usando una tabla de búsqueda:

i - (16773120 >> i & 1) * 12
dupdo
fuente
7

bash - 1

echo `seq 0 11` `seq 0 11` | awk '{print $(number+1)}'

p.ej

$ echo `seq 0 11` `seq 0 11` | awk '{print $(0+1)}'
0

$ echo `seq 0 11` `seq 0 11` | awk '{print $(11+1)}'
11

$ echo `seq 0 11` `seq 0 11` | awk '{print $(12+1)}'
0

$ echo `seq 0 11` `seq 0 11` | awk '{print $(23+1)}'
11

fuente
1
Esto no es válido porque usa punteros.
curiousdannii
@curiousdannii ¿A qué punteros te refieres? El stdiny stdoutcorrientes? Claro, internamente, son punteros, pero también podríamos descalificar a Java porque usa la Integerclase internamente para muchas cosas.
Cole Johnson
¿No es $ () efectivamente equivalente a un puntero?
curiousdannii
@curiousdannii: la documentación de awk dice que son variables integradas.
5

C, little-endian - 2

Probablemente sea una trampa, pero creo que satisface las reglas ...

union {
    int i;
    struct {
        int a:4;
        int b:2;
        int c:10;
    } s;
    struct {
        int a:2;
        int b:14;
    } t;
} u;

u.i = 11-n;
u.s.a = 0;
u.s.c = 0;
result = n-u.t.b;
R ..
fuente
¿Como funciona?
nbubis
1
Sorta trampa, ya que está utilizando en = 0 lugar de & 0x0, lo que debería contar como 2 operaciones adicionales. Pero +1 para la creatividad :)
nbubis
4

PHP - puntaje 0

Me pregunto cómo es posible que nadie haya venido con esto antes que yo.

$n = 18;
$s = str_repeat("a", $n);
$s2 = preg_replace('/aaaaaaaaaaaa/', '', $s);
echo strlen($s2);
Tomás
fuente
2
Agradable. Sin embargo, creo que puede haber un problema, ya que las matrices no están permitidas. Realmente agradable sin embargo.
AJMansfield
@AJMansfield Uno podría argumentar que esto no tiene matrices sino cadenas (sí, en cadenas de bajo nivel son matrices de bytes). :)
seequ
1
@seequ Uno también podría argumentar que esto no es válido debido a su uso de RAM (sí, a bajo nivel, ram es técnicamente una matriz indexada) ¯_ (ツ) _ / ¯
Stan Strum
2

C, puntaje 5

Funciona hasta 23, no garantizado por encima de eso.

( ((n+4)>>2)&4 ) + n & 15

((n+4)>>2)&4devuelve 4 para n> = 12. Agrégalo a n y obtendrás la respuesta correcta en los 4 bits menos significativos, luego trunca los otros bits.

Level River St
fuente
¡¡Bien hecho!! Ahora veamos si alguien puede llegar a 4 ..
nbubis
2

cualquier idioma: 5

no va a ganar, pero participa porque es divertido y quizás porque es más fácil de entender que otros

n - ((n+20)>>5)*12

esto es equivalente a

n - (n>11)*12

esto es equivalente porque cuando sumas 20 a 12, obtienes 32, por lo que el quinto bit se convierte en 1. Esto es solo cuando n> 1 ya que 32 es el número más pequeño donde el quinto bit se convierte en 1.

También tenga en cuenta que es fácilmente expandible para un rango más alto, como puede hacer

n - ((n+20)>>5)*12 - ((n+41)>>5)*12

alcanzar un rango hasta 35

Pinna_be
fuente
1

Python 2.x - 4

j=input();m=lambda a,b:a*b;a=(m(j,357913942)>>32);print j-m(12,a)

Es =un operador?

En ese caso el puntaje es 6.

j-12*(j*357913942>>32)

Por cierto, la solución de @steveverrill también se puede usar directamente en Python.

Funciona para el rango 0 .. 23

Entonces, ¿qué está pasando? Multiplique por 357913942 y divida por 2 ^ 32 (o desplazamiento a la derecha 32)

Willem
fuente
Me gusta cómo usaste una función para multiplicar solo una vez. pero en mi opinión, simplemente renombró la multiplicación a la función m (,), lo que para mí significa que la usó dos veces.
Pinna_be
depende de cómo se interpretan las reglas, pero tiene un punto válido
Willem
1

C - 6

(n - (((n * 0xAAAB) >> 19)) * 12 )
nbubis
fuente
Esto debería ser parte de la pregunta o simplemente otra respuesta. Sugiero lo último.
Jwosty
@Jwosty - cambiado.
nbubis
0

Cobra - 2 (o 3)

def modulo12(n as uint32) as uint32
        for i in 11:n to int64:12,n-=12
        return n

Esto podría estar doblando las reglas un poco, pero pregunté y se me permitió usar esto.

También funciona para cualquier número.

Οurous
fuente
0

Kona - 5

Puede no ser válido porque no estoy seguro de si el operador de piso está permitido, pero tengo dos *y un menos:

mod:{x-(_0.08333*x)*12}

Lo que debería funcionar para cualquier número entero.

Kyle Kanos
fuente
No estoy seguro acerca de la operación del piso, pero definitivamente estoy seguro de que la primera multiplicación está operando en algo diferente a los enteros de 32 bits.
Runer112
@ Runer112: OP dice que la entrada debe ser de 32 bits y que los operadores son como se definen, normalmente son con uniones de 32 bits; no dice nada sobre valores no enteros en el código.
Kyle Kanos
A menos que esté malinterpretando algo, 0.08333 * x no parece una multiplicación tal como se define en las uniones de 32 bits, porque 0.08333 no es una uint de 32 bits.
Runer112
1
"Puede usar un número arbitrario de uniones constantes". - es decir, no puede usar flotantes arbitrarios.
nbubis
1
@nbubis: esa línea en realidad no restringe los flotadores.
Kyle Kanos