Esta é uma versão do desafio recente. Esse número é uma potência inteira de -2? com um conjunto diferente de critérios projetados para destacar a natureza interessante do problema e dificultar o desafio. Eu coloquei alguma consideração nisso aqui .

O desafio, maravilhosamente declarado por Toby na questão vinculada, é:

Existem maneiras inteligentes de determinar se um número inteiro é uma potência exata de 2. Isso não é mais um problema interessante, então vamos determinar se um número inteiro inteiro é uma potência exata de -2 . Por exemplo:

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

Regras:

• Um número inteiro é de 64 bits, assinado, complemento de dois. Esse é o único tipo de dados com o qual você pode trabalhar.
• Você só pode usar as seguintes operações. Cada um deles conta como uma operação.
  • n << k, n >> k: Deslocamento esquerdo / direito nem kbits. O bit de sinal é estendido no turno direito.
  • n >>> k: Desloque para a direita, mas não estenda o bit de sinal. 0s são trocados.
  • a & b, a | b, a ^ b: Bitwise AND, OR, XOR.
  • a + b, a - b, a * b: Adicionar, subtrair, multiplicar.
  • ~b: Inverter bit a bit.
  • -b: Negação do complemento de dois.
  • a / b, a % b: Divide (quociente inteiro, arredonda para 0) e módulo.
    • O módulo de números negativos usa as regras especificadas em C99 : (a/b) * b + a%bdevem ser iguais a. Assim 5 % -3é 2e -5 % 3é -2:
    • 5 / 3é 1, 5 % 3é 2, como 1 * 3 + 2 = 5.
    • -5 / 3é -1, -5 % 3é -2, como -1 * 3 + -2 = -5.
    • 5 / -3é -1, 5 % -3é 2, como -1 * -3 + 2 = 5.
    • -5 / -3é 1, -5 % -3é -2, como 1 * -3 + -2 = -5.
    • Observe que o //operador de divisão de piso do Python %não atende à propriedade "round round 0" da divisão aqui, e o operador do Python também não atende aos requisitos.
  • As atribuições não contam como uma operação. Como em C, as atribuições avaliam o valor do lado esquerdo após a atribuição: a = (b = a + 5)define bpara a + 5, depois define apara be conta como uma operação.
  • As atribuições de compostos podem ser usadas como a += bmédias a = a + be contam como uma operação.
• Você pode usar constantes inteiras, elas não contam como nada.
• Parênteses para especificar a ordem das operações são aceitáveis.
• Você pode declarar funções. As declarações de função podem ter qualquer estilo conveniente para você, mas observe que números inteiros de 64 bits são o único tipo de dados válido. As declarações de função não contam como operações, mas uma chamada de função conta como uma. Além disso, fique claro: as funções podem conter várias returninstruções returnes de qualquer ponto são permitidas. O returnpróprio não conta como uma operação.
• Você pode declarar variáveis ​​sem nenhum custo.
• Você pode usar whileloops, mas não pode usar ifou for. Os operadores usados ​​na whilecondição contam para sua pontuação. whileos loops são executados desde que sua condição seja avaliada como um valor diferente de zero (um "verdadeiro" 0 em idiomas que possuem esse conceito não é um resultado válido). Desde o início de retorno é permitido, você tem permissão para usar breakbem
• Estouro / estouro insuficiente é permitido e nenhum valor de fixação será feito. É tratado como se a operação realmente tivesse ocorrido corretamente e foi truncado para 64 bits.

Critérios de pontuação / vencedor:

Seu código deve produzir um valor diferente de zero se a entrada for uma potência de -2 e zero, caso contrário.

Isso é código-atômico-golfe . Sua pontuação é o número total de operações presentes no seu código (conforme definido acima), não o número total de operações que são executadas em tempo de execução. O código a seguir:

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

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

Contém 5 operações: duas na função e três chamadas de função.

Não importa como você apresenta seu resultado, use o que for conveniente em seu idioma, seja ele armazenando o resultado em uma variável, retornando-o de uma função ou qualquer outra coisa.

O vencedor é o post que está comprovadamente correto (forneça uma prova casual ou formal, se necessário) e tem a menor pontuação, conforme descrito acima.

Desafio de modo muito difícil de bônus !

Para ter a chance de ganhar absolutamente nada, exceto a capacidade potencial de impressionar as pessoas nas festas, envie uma resposta sem usar whileloops! Se um número suficiente deles for submetido, posso até considerar dividir os grupos vencedores em duas categorias (com e sem loops).

Nota: Se você desejar fornecer uma solução em um idioma que suporte apenas números inteiros de 32 bits, faça isso, desde que justifique suficientemente que ainda será correto para números inteiros de 64 bits em uma explicação.

Além disso: certos recursos específicos do idioma podem ser permitidos sem custo, se eles não violarem as regras, mas forem necessários para coagir o seu idioma a se comportar de acordo com as regras acima . Por exemplo (artificial), permitirei uma comparação livre não igual a 0 em whileloops, quando aplicada à condição como um todo, como uma solução alternativa para um idioma que possui 0s "verdadeiros". Não são permitidas tentativas claras de tirar proveito desses tipos de coisas - por exemplo, o conceito de valores "verdadeiros" 0 ou "indefinidos" não existe no conjunto de regras acima e, portanto, eles não podem ser invocados.

C ++, 15 operações

Não faço ideia por que os whileloops são permitidos, pois destroem todo o desafio. Aqui está uma resposta sem nenhuma:

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
}

Operações Python 2 , 3

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

Experimente online!

As operações são >>, &, /.

A idéia é dividir repetidamente por -2. Poderes de -2 cadeia até 1: -8 -> 4 -> -2 -> 1. Se acertarmos um 1, aceite. Se acertarmos um número ímpar antes de bater 1, rejeite. Também precisamos rejeitar 0, o que sempre vai para si.

Os while n>>1:loops até nsão 0 ou 1. Quando o loop quebra, nele próprio é retornado e 1é uma saída Truthy e 0uma saída Falsey. Dentro do loop, rejeitamos repetidamente aplicar n -> n/-2e rejeitar qualquer ímpar n.

Como o método /é usado apenas em valores pares, seu comportamento de arredondamento nunca entra em jogo. Portanto, não importa que o Python seja diferente das especificações.

Ferrugem, 14 12 operações (sem loops)

Requer otimização ( -O) ou -C overflow-checks=nopara ativar a subtração transbordante em vez 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 esclarecer: NÃO!x é bit a bit aqui, não é lógico)

Casos de teste:

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

Experimente online!

A idéia é verificar se | x | é uma potência de 2 (usando (y & (y - 1)) == 0como de costume). Se x é uma potência de 2, então verificamos (1) quando x >= 0, também deve ser uma potência par de 2 ou (2) quando x < 0, deve ser uma potência ímpar de 2. Verificamos isso &ao " bad_power_of_two"mascara 0x… aaaa quando x >= 0(produz 0 somente quando é uma potência uniforme) ou 0x… 5555 quando x < 0.

Haskell, 2 3 operações

import Data.Bits (.&.)

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

Define uma função recursiva f(n). As operações usadas são chamada de função ( f), divisão ( div) e bit a bit e ( .&.).

Não contém loops devido ao fato de que Haskell não possui instruções de loop :-)

Operações em Python 3, 10 ou 11 9

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

Retorna 5para poderes de -2, 0caso contrário

C, 5 operações

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 operações, sem loops

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 operação

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

Montagem, 1 operação

.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

Usa uma enorme tabela de pesquisa para descobrir se o número é uma potência de 2. Você pode expandir isso para 64 bits, mas encontrar um computador para armazenar esses dados é deixado como exercício para o leitor :-P

C, 31 operações

Demonstração ao vivo

Minha idéia é simples, se é uma potência de dois, então, se o log for par, deve ser positivo; caso contrário, o log deve ser impar.

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 operações

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

ou:

C, 13 operações sem loops como condicionais

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

Explicação:

• n&-nproduz o menor bit definido de n.
• aé o valor absoluto negado de n/2, necessariamente negativo, porque /2impede o excesso de negação.
• a/xé zero somente se afor uma potência exata de dois; caso contrário, pelo menos um outro bit está definido e é maior que xo bit mais baixo, produzindo um resultado negativo.
• ~(a/x >> 63)em seguida, produz uma máscara de bits que é todo-queridos se nou -né uma potência de dois, caso contrário, todos os-zeros.
• ^sé aplicado à máscara para verificar o sinal de npara ver se é uma potência -2.

PHP, 3 operações

ternário e ifnão permitido; então vamos abusar 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: se number for 0 ou 1, retorne number
2. $n&1: se o número for ímpar, retorne 0
3. teste else $n/-2(+ converter para int)

JavaScript ES6, 7 operações

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

Experimente online!

Explicação

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

Enquanto x! = 0 e x% 2 == 0 4 ops
x / x é igual a 1 desde que x não seja 0 (0/0 fornece NaN que é avaliado como falso)
& bit a bit e
x & 1 ^ 1 é igual a 1 se x é par (x e 1) xor 1

x/=-2;x=x|0

Essa é a forma de divisão definida pela pergunta 1

while(x&0xfffffffe)  

Enquanto x! = 1 e x! = 0 1 op
A condição necessária para sair quando x == 0 ou x == 1, pois esses dois são os valores de retorno e a inserção de um loop infinito não seria produtiva. Teoricamente, isso poderia ser estendido para valores maiores, aumentando o número hexadecimal. Atualmente trabalha para até ± 2 ^ 32-1

x-=x

Defina x como 0 1 op.
Embora eu pudesse ter usado o retorno 0 para 0 ops, senti que qualquer loop while quebrado por outra instrução parece muito trapaceiro.

return x

retorna x (1 se potência de -2, 0 caso contrário)