¿Es este número una potencia exacta de -2: (Muy) Modo difícil

26

Esta es una versión del desafío reciente ¿Es este número una potencia entera de -2? con un conjunto diferente de criterios diseñados para resaltar la naturaleza interesante del problema y hacer que el desafío sea más difícil. Puse algo de consideración aquí .

El desafío que Toby afirma maravillosamente en la pregunta vinculada es:

Hay formas inteligentes de determinar si un número entero es una potencia exacta de 2. Eso ya no es un problema interesante, así que determinemos si un entero dado es una potencia exacta de -2 . Por ejemplo:

-2 => yes: (-2)¹
-1 => no
0 => no
1 => yes: (-2)⁰
2 => no
3 => no
4 => yes: (-2)²

Reglas:

  • Un número entero es de 64 bits, con signo, complemento de dos. Este es el único tipo de datos con el que puede trabajar.
  • Solo puede usar las siguientes operaciones. Cada uno de estos cuenta como una operación.
    • n << k, n >> k: Desplazamiento a la izquierda / derecha npor kbits. El bit de signo se extiende en el desplazamiento a la derecha.
    • n >>> k: Desplazamiento a la derecha pero no extiende el bit de signo. Los 0 se desplazan.
    • a & b, a | b, a ^ b: Bitwise AND, OR, XOR.
    • a + b, a - b, a * b: Sumar, restar, multiplicar.
    • ~b: Inversión bit a bit.
    • -b: Negación del complemento a dos.
    • a / b, a % b: Divide (cociente entero, se redondea hacia 0) y módulo.
      • El módulo de números negativos utiliza las reglas especificadas en C99 : (a/b) * b + a%bserá igual a. Así 5 % -3es 2y -5 % 3es -2:
      • 5 / 3es 1, 5 % 3es 2, como 1 * 3 + 2 = 5.
      • -5 / 3es -1, -5 % 3es -2, como -1 * 3 + -2 = -5.
      • 5 / -3es -1, 5 % -3es 2, como -1 * -3 + 2 = 5.
      • -5 / -3es 1, -5 % -3es -2, como 1 * -3 + -2 = -5.
      • Tenga en cuenta que el //operador de división de piso de Python no satisface la propiedad de "redondear hacia 0" de la división aquí, y el %operador de Python tampoco cumple con los requisitos.
    • Las asignaciones no cuentan como una operación. Como en C, las asignaciones evalúan el valor del lado izquierdo después de la asignación: se a = (b = a + 5)establece ben a + 5, luego se establece aen b, y cuenta como una operación.
    • Las asignaciones compuestas pueden usarse como a += bmedios a = a + by contar como una operación.
  • Puede usar constantes enteras, no cuentan como nada.
  • Los paréntesis para especificar el orden de las operaciones son aceptables.
  • Puedes declarar funciones. Las declaraciones de funciones pueden tener cualquier estilo que sea conveniente para usted, pero tenga en cuenta que los enteros de 64 bits son el único tipo de datos válido. Las declaraciones de funciones no cuentan como operaciones, pero una llamada de función cuenta como una. Además, para ser claros: las funciones pueden contener múltiples returndeclaraciones y returnse permiten mensajes de correo electrónico desde cualquier punto. El returnsí mismo no cuenta como una operación.
  • Puede declarar variables sin costo.
  • Puede usar whilebucles, pero no puede usar ifo for. Los operadores utilizados en la whilecondición cuentan para su puntaje. whilelos bucles se ejecutan siempre que su condición se evalúe a un valor distinto de cero (un "verdadero" 0 en lenguajes que tienen este concepto no es un resultado válido). Ya que se permite a principios de retención, se le permite utilizar break, así
  • Se permite el desbordamiento / subflujo y no se realizará una fijación de valor. Se trata como si la operación realmente sucediera correctamente y luego se truncara a 64 bits.

Criterios de puntuación / victoria:

Su código debe producir un valor que no sea cero si la entrada es una potencia de -2, y cero en caso contrario.

Este es . Su puntaje es el número total de operaciones presentes en su código (como se definió anteriormente), no el número total de operaciones que se ejecutan en tiempo de ejecución. El siguiente código:

function example (a, b) {
    return a + ~b;
}

function ispowerofnegtwo (input) {
    y = example(input, 9);
    y = example(y, 42);
    y = example(y, 98);
    return y;
}

Contiene 5 operaciones: dos en la función y tres llamadas a funciones.

No importa cómo presente su resultado, use lo que sea conveniente en su idioma, ya sea en última instancia, almacenando el resultado en una variable, devolviéndolo de una función, o lo que sea.

El ganador es la publicación que es demostrablemente correcta (proporcione una prueba informal o formal si es necesario) y tiene el puntaje más bajo como se describió anteriormente.

Bonus muy difícil modo desafío!

Para tener la oportunidad de ganar absolutamente nada, excepto la capacidad potencial de impresionar a las personas en las fiestas, envíe una respuesta sin usar whilebucles Si se presentan suficientes de estos, incluso podría considerar dividir los grupos ganadores en dos categorías (con y sin bucles).


Nota: Si desea proporcionar una solución en un lenguaje que solo sea compatible con enteros de 32 bits, puede hacerlo, siempre que justifique suficientemente que seguirá siendo correcta para enteros de 64 bits en una explicación.

Además: ciertas características específicas del idioma pueden permitirse sin costo si no eluden las reglas, pero son necesarias para obligar a su idioma a comportarse de acuerdo con las reglas anteriores . Por ejemplo (artificial), permitiré una comparación libre no igual a 0 en whilebucles, cuando se aplica a la condición como un todo, como una solución para un lenguaje que tiene ceros "verdaderos". No se permiten intentos claros de aprovechar este tipo de cosas , por ejemplo, el concepto de valores "verdaderos" 0 o "indefinidos" no existe en el conjunto de reglas anterior, por lo que no se puede confiar en ellos.

Jason C
fuente
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
Dennis
@hvd Si lees esto: ¡Deberías recuperar totalmente tu respuesta! Asumiendo que es correcto, incluso sin m ^= s que sea todavía impresionante, y creo que estaría totalmente bien hacer la sustitución para mejorarlo aún más.
Jason C
¿Cómo tiene sentido permitir whiley breakno permitir if? if (x) { ... }es equivalente a while (x) { ... break; }.
R ..
@R .. No tiene 100% de sentido ( breaky los retornos tempranos son la parte lamentable) y es una larga historia y una lección aprendida en reglas para futuros desafíos. ¡Siempre existe la versión "bonus"! :)
Jason C
1
¿Por qué ify forno están permitidos? int x=condition; while (x) { ... x=0; }es gratis, solo más código. Lo mismo con c-style for.
Qwertiy

Respuestas:

35

C ++, 15 operaciones

No tengo idea de por qué los whilebucles están permitidos ya que destruyen todo el desafío. Aquí hay una respuesta sin ninguna:

int64_t is_negpow2(int64_t n) {
    int64_t neg = uint64_t(n) >> 63; // n >>> 63
    n = (n ^ -neg) + neg; // if (n < 0) n = -n;
    int64_t evenbits = n & int64_t(0xaaaaaaaaaaaaaaaaull >> neg);
    int64_t n1 = n - 1;
    int64_t pot = n & n1;
    int64_t r = pot | (n1 >> 63) | evenbits;
    return ~((r | -r) >> 63); // !r
}
orlp
fuente
¿Por qué los whilebucles destruyen todo el desafío ?
Sr. Xcoder
10
@ Mr.Xcoder Porque el desafío es hacerlo con operaciones simples a nivel de bits y whileva en contra de eso en todos los sentidos.
orlp
Quiero decir, a menos que hagas que los bucles while multipliquen el número de operaciones por el número de veces ejecutadas en el bucle para una estática no algo así.
Magic Octopus Urn
Hice un comentario sobre esto aquí .
Jason C
@JasonC Eso es porque debería haber usado un desplazamiento a la derecha sin bit de signo. He editado el código (que utiliza uint64_t, porque esa es la única manera de conseguir el desplazamiento a la derecha sin extensión de signo.)
orlp
25

Python 2 , 3 operaciones

def f(n):
 while n>>1:
  while n&1:return 0
  n=n/-2
 return n

Pruébalo en línea!

Las operaciones son >>, &, /.

La idea es dividir repetidamente por -2. Powers de -2 cadena abajo a 1: -8 -> 4 -> -2 -> 1. Si damos con un 1, acepta. Si tocamos un número impar antes de golpear 1, rechazar. También tenemos que rechazar 0, lo que siempre se va solo.

Los while n>>1:bucles hasta nson 0 o 1. Cuando el bucle se rompe, nse devuelve y 1es una salida de 0Verdad y una de Falsey. Dentro del ciclo, rechazamos aplicar repetidamente n -> n/-2y rechazamos cualquier impar n.

Como /solo se usa en valores pares, su comportamiento de redondeo nunca entra en juego. Por lo tanto, no importa que Python redondea de manera diferente a la especificación.

xnor
fuente
Agradable. Lógica inteligente en el algoritmo y buen trabajo combinando condicionales en operaciones de bits. Además, puedo confirmar que la implementación funciona en C.
Jason C
¿Por qué en while n&1lugar de if n&1?
Mark Ransom
2
@MarkRansom El desafío no lo permite if.
xnor
Ajá, lo extrañé. Muy inteligente sustitución.
Mark Ransom
1
@EvSunWoodard El puntaje es el número de operadores en el código, no el número de llamadas a ellos durante la ejecución, que depende de la entrada: "Este es el código de golf atómico. Su puntaje es el número total de operaciones presentes en su código ".
xnor
11

Moho, 14 12 operaciones (sin bucles)

Requiere optimización ( -O) o -C overflow-checks=nopara habilitar la resta desbordante en lugar de pánico.

fn is_power_of_negative_2(input: i64) -> i64 {
    let sign = input >> 63;
    // 1 op
    let abs_input = (input ^ sign) - sign;
    // 2 ops
    let bad_power_of_two = sign ^ -0x5555_5555_5555_5556; // == 0xaaaa_aaaa_aaaa_aaaa
    // 1 op
    let is_not_power_of_n2 = abs_input & ((abs_input - 1) | bad_power_of_two);
    // 3 ops 
    let is_not_power_of_n2 = (is_not_power_of_n2 | -is_not_power_of_n2) >> 63;
    // 3 ops 
    input & !is_not_power_of_n2
    // 2 ops
}

(Para aclarar: !xes bit a bit, NO aquí, no es lógico, NO)

Casos de prueba:

#[test]
fn test_is_power_of_negative_2() {
    let mut value = 1;
    for _ in 0 .. 64 {
        assert_ne!(0, is_power_of_negative_2(value), "wrong: {} should return nonzero", value);
        value *= -2;
    }
}

#[test]
fn test_not_power_of_negative_2() {
    for i in &[0, -1, 2, 3, -3, -4, 5, -5, 6, -6, 7, -7, 8, 1<<61, -1<<62, 2554790084739629493, -4676986601000636537] {
        assert_eq!(0, is_power_of_negative_2(*i), "wrong: {} should return zero", i);
    }
}

Pruébalo en línea!


La idea es verificar si | x | es una potencia de 2 (usando (y & (y - 1)) == 0como de costumbre). Si x es una potencia de 2, entonces verificamos (1) cuándo x >= 0, también debería ser una potencia par de 2, o (2) cuándo x < 0, debería ser una potencia impar de 2. Verificamos esto &marcando el " bad_power_of_two"enmascara 0x ... aaaa cuando x >= 0(produce 0 solo cuando es una potencia par), o 0x ... 5555 cuando x < 0.

kennytm
fuente
Robé tu ~((r | -r) >> 63)truco para terminar arreglando mi respuesta.
orlp
6

Haskell, 2 3 operaciones

import Data.Bits (.&.)

f 0 = False
f 1 = True
f n | n .&. 1 == 0 = f (n `div` -2)
f n | otherwise    = False

Define una función recursiva f(n). Las operaciones utilizadas son la función call ( f), division ( div) y bitwise y ( .&.).

No contiene bucles debido al hecho de que Haskell no tiene declaraciones de bucle :-)

Oportunista
fuente
44
¿Por qué no me sorprende que la solución de Haskell que no utiliza bucles sea proporcionada por alguien llamado "Oportunista"? =)
Cort Ammon - Restablece a Mónica el
1
Estoy muy indeciso sobre el f 0, f 1, f n ...aquí, ya que son esencialmente if's en el encubrimiento, aunque, de nuevo, me permito while+ breaky principios del returns, por lo que parece justo. Si bien parece aprovechar que mi conjunto de reglas se deja inadvertidamente abierto a la interpretación, es una buena solución.
Jason C
3
En particular, los |s están especialmente en el aire. Dicho esto, esto viola una regla en particular de una manera menos discutible: la comparación ==no está permitida. Nótese, sin embargo, que si mi interpretación de este código es correcto, el uso de booleanos aquí no parece aceptable como la sustitución de valores enteros arbitrarios en su lugar no parece cambiar los resultados, y son más de una forma de presentación final.
Jason C
@JasonC Solo lo estoy usando ==porque no hay otra forma de transmitir desde o Inthacia Bool"Truthy" en Haskell. Si la coincidencia de patrones y los guardias violan la ifregla de "no s" es su decisión ;-)
Oportunista el
18
Con la coincidencia de patrones, puede codificar los resultados de todos los enteros de 64 bits utilizando operaciones 0.
xnor
5

Python 3, 10 u 11 9 operaciones

def g(x):
 while x:
  while 1 - (1 + ~int(x - -2 * int(float(x) / -2))) & 1: x /= -2
  break
 while int(1-x):
     return 0
 return 5  # or any other value

Devoluciones 5por poderes de -2, de lo 0contrario

Sr. Xcoder
fuente
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
Dennis
5

C, 5 operaciones

long long f(long long x){
    x=x ^ ((x & 0xaaaaaaaaaaaaaaaa) * 6);
    while(x){
        while(x&(x-1))
            return 0;
        return 1;
    }
    return 0;
}

C, 10 operaciones, sin bucles

long long f(long long x){
    x = x ^ ((x & 0xaaaaaaaaaaaaaaaa) * 6);
    long long t = x & (x-1);
    return (((t-1) & ~t) >> 63) * x;
}

C, 1 operación

long long f(long long x){
    long long a0=1, a1=-2, a2=4, a3=-8, a4=16, a5=-32, a6=64, a7=-128, a8=256, a9=-512, a10=1024, a11=-2048, a12=4096, a13=-8192, a14=16384, a15=-32768, a16=65536, a17=-131072, a18=262144, a19=-524288, a20=1048576, a21=-2097152, a22=4194304, a23=-8388608, a24=16777216, a25=-33554432, a26=67108864, a27=-134217728, a28=268435456, a29=-536870912, a30=1073741824, a31=-2147483648, a32=4294967296, a33=-8589934592, a34=17179869184, a35=-34359738368, a36=68719476736, a37=-137438953472, a38=274877906944, a39=-549755813888, a40=1099511627776, a41=-2199023255552, a42=4398046511104, a43=-8796093022208, a44=17592186044416, a45=-35184372088832, a46=70368744177664, a47=-140737488355328, a48=281474976710656, a49=-562949953421312, a50=1125899906842624, a51=-2251799813685248, a52=4503599627370496, a53=-9007199254740992, a54=18014398509481984, a55=-36028797018963968, a56=72057594037927936, a57=-144115188075855872, a58=288230376151711744, a59=-576460752303423488, a60=1152921504606846976, a61=-2305843009213693952, a62=4611686018427387904, a63=-9223372036854775807-1, a64=0;
    while(a0){
        long long t = x ^ a0;
        long long f = 1;
        while(t){
            f = 0;
            t = 0;
        }
        while(f)
            return 1;
        a0=a1; a1=a2; a2=a3; a3=a4; a4=a5; a5=a6; a6=a7; a7=a8; a8=a9; a9=a10; a10=a11; a11=a12; a12=a13; a13=a14; a14=a15; a15=a16; a16=a17; a17=a18; a18=a19; a19=a20; a20=a21; a21=a22; a22=a23; a23=a24; a24=a25; a25=a26; a26=a27; a27=a28; a28=a29; a29=a30; a30=a31; a31=a32; a32=a33; a33=a34; a34=a35; a35=a36; a36=a37; a37=a38; a38=a39; a39=a40; a40=a41; a41=a42; a42=a43; a43=a44; a44=a45; a45=a46; a46=a47; a47=a48; a48=a49; a49=a50; a50=a51; a51=a52; a52=a53; a53=a54; a54=a55; a55=a56; a56=a57; a57=a58; a58=a59; a59=a60; a60=a61; a61=a62; a62=a63; a63=a64;
    }
    return 0;
}
jimmy23013
fuente
2
Oh hombre, ese último es simplemente malvado. Agradable.
Jason C
4

Asamblea, 1 operación

.data

    .space 1         , 1 # (-2)^31
    .space 1610612735, 0
    .space 1         , 1 # (-2)^29
    .space 402653183 , 0
    .space 1         , 1 # (-2)^27
    .space 100663295 , 0
    .space 1         , 1 # (-2)^25
    .space 25165823  , 0
    .space 1         , 1 # (-2)^23
    .space 6291455   , 0
    .space 1         , 1 # (-2)^21
    .space 1572863   , 0
    .space 1         , 1 # (-2)^19
    .space 393215    , 0
    .space 1         , 1 # (-2)^17
    .space 98303     , 0
    .space 1         , 1 # (-2)^15
    .space 24575     , 0
    .space 1         , 1 # (-2)^13
    .space 6143      , 0
    .space 1         , 1 # (-2)^11
    .space 1535      , 0
    .space 1         , 1 # (-2)^9
    .space 383       , 0
    .space 1         , 1 # (-2)^7
    .space 95        , 0
    .space 1         , 1 # (-2)^5 = -32
    .space 23        , 0
    .space 1         , 1 # (-2)^3 = -8
    .space 5         , 0
    .space 1         , 1 # (-2)^1 = -2
    .space 1         , 0
dataZero:
    .space 1         , 0
    .space 1         , 1 # (-2)^0 = 1
    .space 2         , 0
    .space 1         , 1 # (-2)^2 = 4
    .space 11        , 0
    .space 1         , 1 # (-2)^4 = 16
    .space 47        , 0
    .space 1         , 1 # (-2)^6 = 64
    .space 191       , 0
    .space 1         , 1 # (-2)^8
    .space 767       , 0
    .space 1         , 1 # (-2)^10
    .space 3071      , 0
    .space 1         , 1 # (-2)^12
    .space 12287     , 0
    .space 1         , 1 # (-2)^14
    .space 49151     , 0
    .space 1         , 1 # (-2)^16
    .space 196607    , 0
    .space 1         , 1 # (-2)^18
    .space 786431    , 0
    .space 1         , 1 # (-2)^20
    .space 3145727   , 0
    .space 1         , 1 # (-2)^22
    .space 12582911  , 0
    .space 1         , 1 # (-2)^24
    .space 50331647  , 0
    .space 1         , 1 # (-2)^26
    .space 201326591 , 0
    .space 1         , 1 # (-2)^28
    .space 805306367 , 0
    .space 1         , 1 # (-2)^30
    .space 3221225471, 0
    .space 1         , 1 # (-2)^32

.globl isPowNeg2
isPowNeg2:
    movl dataZero(%edi), %eax
    ret

Utiliza una gran tabla de búsqueda para determinar si el número es una potencia de 2. Puede expandir esto a 64 bits, pero encontrar una computadora para almacenar esa cantidad de datos queda como ejercicio para el lector :-P

Oportunista
fuente
1
La indexación de una tabla no es una de las operaciones permitidas.
R ..
1
Además, esto claramente no es extensible a 64 bits. :-)
R ..
De hecho, la indexación de una tabla no estaba destinada a ser permitida bajo las reglas actuales. Especifiqué "puede declarar variables" y "puede especificar literales enteros" con la intención de escalares, y semánticamente se trata de una matriz (y pedantemente hablando no permití tipos de matriz ni permití indexar ningún tipo como uno de los operaciones, aunque podría llamarlo "adición" en el contexto del ensamblador), pero siendo el oportunista que eres ... :)
Jason C
3

C, 31 operaciones

Demo en vivo

Mi idea es simple, si es una potencia de dos, entonces si su registro es par, entonces tiene que ser positivo, de lo contrario su registro tiene que ser extraño.

int isPositive(int x) // 6
{
    return ((~x & (~x + 1)) >> 31) & 1;
}

int isPowerOfTwo(int x) // 5
{
    return isPositive(x) & ~(x & (x-1));
}

int log2(int x) // 3
{
    int i = (-1);

    while(isPositive(x))
    {
        i  += 1;
        x >>= 1;
    }

    return i;
}

int isPowerOfNegativeTwo(int x) // 17
{
    return (  isPositive(x) &  isPowerOfTwo(x) & ~(log2(x) % 2) )
         | ( ~isPositive(x) & isPowerOfTwo(-x) & (log2(-x) % 2) );
}
Khaled.K
fuente
1
Realmente lo hiciste mejor de lo que piensas. Una llamada de función solo cuenta como 1, no como el número de operadores en la función. Entonces, si he contado correctamente (verificación doble), tienes algo como 6 para isPositive + 5 para isPowerOfTwo + 3 para log2 + 17 para isPowerOfNegativeTwo = 31.
Jason C
1

C, 7 operaciones

int64_t is_power_of_neg2(int64_t n)
{
    int64_t x = n&-n;
    while (x^n) {
        while (x^-n)
            return 0;
        return x & 0xaaaaaaaaaaaaaaaa;
    }
    return x & 0x5555555555555555;
}

o:

C, 13 operaciones sin bucles como condicionales

int64_t is_power_of_neg2(int64_t n)
{
    int64_t s = ~(n>>63);
    int64_t a = ((n/2)^s)-s;
    int64_t x = n&-(uint64_t)n; // Cast to define - on INT64_MIN.
    return ~(a/x >> 63) & x & (0xaaaaaaaaaaaaaaaa^s);
}

Explicación:

  • n&-nproduce el bit de ajuste más bajo de n.
  • aes el valor absoluto negado de n/2, necesariamente negativo porque /2impide el desbordamiento de la negación.
  • a/xes cero solo si aes una potencia exacta de dos; de lo contrario, se establece al menos otro bit, y es más alto que xel bit más bajo, produciendo un resultado negativo.
  • ~(a/x >> 63)luego produce una máscara de bits que es todo uno no si -nes una potencia de dos, de lo contrario, todos ceros.
  • ^sse aplica a la máscara para verificar el signo de npara ver si es un poder de -2.
R ..
fuente
1

PHP, 3 operaciones

ternario y ifno se permiten; así que maltratemos while:

function f($n)
{
    while ($n>>1)               # 1. ">>1"
    {
        while ($n&1)            # 2. "&1"
            return 0;
        return f($n/-2|0);      # 3. "/-2" ("|0" to turn it into integer division)
    }
    return $n;
}
  1. $n>>1: si el número es 0 o 1, devuelve el número
  2. $n&1: si el número es impar, devuelve 0
  3. prueba else $n/-2(+ cast a int)
Titus
fuente
0

JavaScript ES6, 7 operaciones

x=>{
  while(x&1^1&x/x){
    x/=-2;x=x|0
  }
  while(x&0xfffffffe)x-=x
  return x
}

Pruébalo en línea!

Explicación

while(x&1^1&x/x)

Mientras x! = 0 yx% 2 == 0 4 operaciones
x / x es igual a 1 siempre que x no sea 0 (0/0 da NaN que se evalúa como falso)
y bit a bit y
x & 1 ^ 1 es igual a 1 si x es par (x y 1) xo 1

x/=-2;x=x|0

Esta es la forma de división definida por la pregunta 1 op

while(x&0xfffffffe)  

Mientras x! = 1 yx! = 0 1 op
La condición necesaria para salir cuando x == 0 o x == 1 ya que esos dos son los valores de retorno e ingresar un ciclo infinito no sería productivo. Teóricamente, esto podría extenderse para valores mayores aumentando el número hexadecimal. Actualmente funciona para hasta ± 2 ^ 32-1

x-=x

Establezca x en 0 1 op.
Si bien podría haber usado return 0 para 0 ops, sentí que cualquier ciclo while que se rompe con otra declaración se parece demasiado a hacer trampa.

return x

devuelve x (1 si la potencia de -2, de lo contrario 0)

fəˈnɛtɪk
fuente