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 el código atómico de golf . 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.

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
}

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.

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.

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 :-)

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

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;
}

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

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) );
}

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.

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)

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)