Esse número é uma potência inteira de -2?

41

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

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

Regras

  • Você pode escrever um programa ou uma função e usar qualquer um dos métodos padrão de recebimento de entrada e saída.

  • Sua entrada é um único número inteiro e a saída deve ser um valor verdadeiro se o número inteiro for uma potência inteira de -2 e, caso contrário, um valor falso. Nenhuma outra saída (por exemplo, mensagens de aviso) é permitida.

  • As regras usuais de estouro de números inteiros se aplicam: sua solução deve ser capaz de trabalhar com números inteiros arbitrariamente grandes em uma versão hipotética (ou talvez real) do seu idioma, na qual todos os números inteiros são ilimitados por padrão, mas se o seu programa falhar na prática devido à implementação não suporta números inteiros tão grandes, que não invalida a solução.

  • Você pode usar qualquer linguagem de programação , mas observe que essas brechas são proibidas por padrão.

Condição vencedora

Este é um concurso de : a resposta que tiver menos bytes (na codificação escolhida) é a vencedora.

Toby Speight
fonte
17
@KritixiLithos Não vejo por que deveria. Não existe um número inteiro ital que(-2)^i = 2
Fatalize 6/17
2
Os expoentes são positivos ou -0.5devem ser válidos, pois são 2 ^ (- 1) .
Mr. Xcoder
11
@ Mr.Xcoder, Como as entradas são sempre valores inteiros , um expoente negativo não será necessário (ou possível).
perfil completo de Toby Speight
11
@SIGSEGV talvez enquanto inão é natural
Mr. Xcoder
2
@ Jason, quantos são suportados / naturais no seu idioma - veja a terceira regra. E é código-golfe, porque ele precisa de um critério de vitória objetivo para ser abordado aqui - "uma solução agradável" não é suficiente (embora eu goste da resposta do Mathematica - que me surpreendeu).
perfil completo de Toby Speight

Respostas:

26

Mathematica, 22 bytes

EvenQ@Log2@Max[#,-2#]&

Experimente online! (Em vez disso, usando a matemática, onde esta solução também funciona.)

Tentei encontrar uma solução com operadores bit a bit por um tempo e, embora exista definitivamente, acabei encontrando algo que provavelmente é mais simples:

  • Max[#,-2#]multiplica a entrada por -2 se for negativo. A multiplicação por outro fator de -2 não muda se o valor é uma potência de -2 ou não. Mas agora todos os poderes ímpares de -2 foram transformados em poderes pares de -2 .
  • Mas mesmo potências de -2 também são potências de 2 , então podemos usar um simples Log2@...e verificar se o resultado é um número inteiro (para verificar se é uma potência de 2 ). Isso já economiza mais dois bytes Log[4,...](outra maneira de analisar as potências pares de -2 ).
  • Como um bônus adicional, verificar se um valor é um número inteiro par é mais curto do que apenas verificar se é um número inteiro: podemos salvar mais três bytes usando em EvenQvez de IntegerQ.
Martin Ender
fonte
Ajuda considerar que potências iguais de -2 são potências inteiras de 4? Eu gosto da ideia de multiplicar por -2 para obter tudo positivo - embora desapontado por não ter mexido até agora.
perfil completo de Toby Speight
5
@TobySpeight Tratá-los como potências de 2 na verdade economiza 5 bytes. Eu usei potências de 4 no começo, mas Log[4,...]é maior que Log2@...e IntegerQé maior que EvenQ.
Martin Ender
16

Gelatina , 5 bytes

æḟ-2=

Experimente online!

Como funciona

æḟ-2=  Main link. Argument: n

æḟ-2   Round n towards 0 to the nearest power of -2.
    =  Test if the result is equal to n.
Dennis
fonte
12

Python , 46 bytes

-2 bytes graças a @ovs.

def g(x):
 while x%-2==0!=x:x/=-2
 return x==1

Função com uso:

g(4) # put your number between the brackets

Experimente online!

Mr. Xcoder
fonte
print g(8)gravurasFalse
Felipe Nardi Batista
2
@FelipeNardiBatista não deveria?
Mr. Xcoder
2
desculpe, meu exemplo foi um mau, print g(4)faz o mesmo
Felipe Nardi Batista
Espere, há um pequeno erro, corrigi-lo logo
Mr. Xcoder
11
Eu coloquei um em ;vez de uma nova linha ... desculpe por isso. Corrigido @FelipeNardiBatista
Mr. Xcoder
11

Gelatina , 6 bytes

b-2S⁼1

Experimente online!

Isso se baseia em como o Jelly converte um número inteiro N em qualquer base arbitrária B , fazendo isso convertendo N em uma matriz, na qual cada número inteiro é um dígito d de ( N ) B , que pode ter um valor 0≤ V d < B . Aqui, vamos 0-índice dígitos da direita, de modo que todos os dígitos adiciona V d B d para formar N . V d < BV d B d < BB d = B d +1 , portanto, todos os possíveisN tem apenas uma única representação, se ignorarmos 0s principais em ( N ) B .

Aqui, d = entrada, B = -2. N = B d = 1 B d = V d B d ⇔ 1 = V dV d = 1 e, como não estamos adicionando outros múltiplos de potências de B , todos os outros V seriam 0. No momento, a matriz deve ser 1 concatenada com d 0s. Como o Jelly 1 indexa da esquerda, devemos verificar se o primeiro elemento do array é 1 e todos os outros elementos são 0.

Hmm ... tudo bem, certo? Não? O que está acontecendo? Ah, sim, tenho uma ideia melhor! Primeiro, vamos pegar a soma de todos os números inteiros na matriz, tratando-a como se fosse uma matriz inteira e não um número na base -2. Se for 1, significa que existe apenas um 1 e todos os outros números inteiros são 0. Como não pode haver zeros à esquerda, exceto no caso de 0 -2(onde a soma seria 0 ≠ 1 de qualquer maneira), o primeiro número inteiro deve ser diferente de zero. O único número inteiro diferente de zero na matriz é o 1, portanto deve ser o primeiro. Portanto, este é o único caso em que a soma de todos os números inteiros na matriz seria 1, porque a menor soma possível de um par de números inteiros positivos é Σ {1,1} = 2, pois o menor número inteiro positivo é 1 Todo número inteiro em uma representação de base é não negativo, portanto, a única maneira de a soma ser 1 é ter apenas 1 e todos os outros números inteiros são 0. Portanto, podemos apenas verificar se a soma de todos os números inteiros na matriz é 1.

Aqui está o que o código faz:

b-2S⁼1 Main link. Arguments: d
b-2    Convert d to base -2.
   S   Take the sum.
    ⁼1 Check if the sum is equal to 1.
Erik, o Outgolfer
fonte
11
Ufa, essa explicação teve tempo para escrever ...
Erik o Outgolfer
Eu odiaria ver o que uma explicação para um longo programa ficaria assim então ...
boboquack
11
@boboquack Aqui estou explicando por que uso o material de conversão base. Não acho que a explicação para programas longos seja tão longa. Uma postagem pode conter até 30000 caracteres de remarcação, e as explicações para programas mais longos seriam mais concisas de qualquer maneira. Além disso, li explicações muito mais longas e elas não são tão chatas.
Erik the Outgolfer
11

Python 2 , 98 50 bytes

lambda x:x*(x&-x==abs(x))*((x<0)^x.bit_length()&1)

Experimente online!

Felipe Nardi Batista
fonte
10

Excel, 40 36 bytes

Salvo 4 bytes por CallumDA

O Excel certamente pode fazê-lo, mas a correção de erros adiciona 11 bytes

=IFERROR(-2^IMREAL(IMLOG2(A1)),1)=A1

A entrada está na célula A1. A saída é TRUEouFALSE

Se fosse permitido retornar um FALSEou #NUM!erro para valores falsos, seriam apenas 25 bytes:

=-2^IMREAL(IMLOG2(A1))=A1
Engenheiro Toast
fonte
Heres uma pequena melhoria:=IFERROR(-2^IMREAL(IMLOG2(A1)),1)=A1
CallumDA 06/04
11
@CallumDA Thanks! Tentei descobrir uma maneira de usar as funções numéricas complexas, mas tudo o que surgiu foi mais longo.
Engenheiro brinde
9

05AB1E , 8 bytes

Y(IÄÝm¹å

Experimente online! ou como um conjunto de testes

Explicação

Y(         # push -2
  IÄÝ      # push range [0 ... abs(input)]
     m     # element-wise power
      ¹å   # check if input is in the resulting list
Emigna
fonte
Por que o voto negativo?
precisa saber é o seguinte
@ KritixiLithos: Parece que alguém diminuiu o voto em todos os idiomas do golfe.
Emigna
6
Notei isso também. Embora eu não conheça o PPCG há muito tempo, aprendi que as soluções criativas e interessantes em idiomas padrão são muito mais apreciadas do que as soluções de 3 bytes nos idiomas de golfe. No entanto, algumas pessoas (infelizmente) rejeitam soluções muito criativas em linguagens de golfe, simplesmente porque acham que tudo está embutido e não entendem o quão bons são os algoritmos (embora escritos em idiomas de golfe). +1 para a incrível @Emigna solução
Mr. Xcoder
ÄLY(småOfor 8. Y(sÄLm¢Zfor 8 ... Nevermind, all 8.
Magic Octopus Urn
9

JavaScript (ES6), 37 28 24 bytes

f=x=>!x|x%2?x==1:f(x/-2)

Economizou 4 bytes graças a Arnauld.

f=x=>!x|x%2?x==1:f(x/-2)

console.log(f(-2));
console.log(f(-1));
console.log(f(0));
console.log(f(1));
console.log(f(2));
console.log(f(3));
console.log(f(4));

Tom
fonte
Por que vejo alguns erros (antes dos valores verdadeiro / falso) quando clico em "Executar trecho de código"?
numbermaniac
@numbermaniac Não tenho certeza, talvez você esteja usando um navegador que não suporta totalmente o ES6?
Tom
Welp, atualizado e tentado novamente, sem erros. Não tenho certeza do que aconteceu pela primeira vez.
numbermaniac
8

MATL , 9 8 bytes

2_y|:q^m

Experimente online! Ou verifique todos os casos de teste .

Como funciona

Considere a entrada -8como um exemplo

2_    % Push -2
      % STACK: -2
y     % Implicit input. Duplicate from below
      % STACK: -8, -2, -8
|     % Absolute value
      % STACK: -8, -2, 8
:     % Range
      % STACK: -8, -2, [1 2 3 4 5 6 7 8]
q     % Subtract 1, element-wise
      % STACK: -8, -2, [0 1 2 3 4 5 6 7]
^     % Power, element-wise
      % STACK: -8, [1 -2 4 -8 16 -32 64 -128]
m     % Ismember. Implicit display
      % STACK: 1
Luis Mendo
fonte
Se eu entendi sua explicação corretamente, e, em seguida, com a entrada n, isso cria uma matriz de tamanho ncomo uma etapa intermediária. Bom trabalho que a eficiência não é um critério aqui!
perfil completo de Toby Speight
2
@Toby Claro! Este é o código de golfe, quem se importa com eficiência? :-D
Luis Mendo
6

Oitava , 28 bytes

@(n)any((-2).^(0:abs(n))==n)

Isso define uma função anônima. A abordagem é semelhante à da minha resposta MATL.

Experimente online!

Luis Mendo
fonte
6

PHP, 41 bytes

for(;$argn%-2==0;)$argn/=-2;echo$argn==1;

PHP, 52 bytes

echo($l=log(abs($argn),2))==($i=$l^0)&&$argn>0^$i%2;

PHP, 64 bytes

Trabalhando com um Regex

echo preg_match("#^".($argn>0?1:"1+0")."(00)*$#",decbin($argn));
Jörg Hülsermann
fonte
5

Python 3, 34 bytes

lambda n:n==(-2)**~-n.bit_length()
orlp
fonte
5

JavaScript (ES6), 21 bytes

Uma função recursiva que retorna 0ou true.

f=n=>n==1||n&&f(n/-2)

Como funciona

Isso não inclui nenhum teste explícito - como nestranho ou abs(n)menor que um - para interromper a recursão mais cedo quando a entrada não é uma potência exata de -2.

Saímos apenas quando né exatamente igual a um 1ou0 .

No entanto, isso funciona porque qualquer flutuador IEEE-754 será arredondado para 0quando dividido por 2 (ou -2) vezes suficientes, devido ao fluxo aritmético .

Casos de teste

Arnauld
fonte
4

Java 7, 55 bytes

boolean c(int n){return n==0?0>1:n%-2==0?c(n/-2):n==1;}

Explicação:

boolean c(int n){  // Method with integer parameter and boolean return-type
  return n==0 ?    //  If n is zero:
    0>1//false     //   Return false
   : n%-2==0 ?     //  Else-if n mod -2 is zero:
    c(n/-2)        //   Recursive call for the input divided by -2
   :               //  Else:
    n==1;          //   Return if n is one
}                  // End of method

Código do teste:

Experimente aqui.

class M{
  static boolean c(int n){return n==0?0>1:n%-2==0?c(n/-2):n==1;}

  public static void main(String[] a){
    for(int i = -2; i <= 4; i++){
      System.out.println(i + ": " + c(i));
    }
  }
}

Saída:

-2: true
-1: false
0: false
1: true
2: false
3: false
4: true
Kevin Cruijssen
fonte
A forma não-recursiva é mais curta por 5 bytes: boolean c(int n){while(0==n%-2)n/=-2;return 1==n;}.
Olivier Grégoire
@ OlivierGrégoire Infelizmente, isso não funciona para n=0Java, porque 0%-2==0será truee 0/-2ainda está 0causando um loop infinito, razão pela qual adicionei a n==0?0>1peça ao meu método recursivo.
Kevin Cruijssen
Bem detectado!
Olivier Grégoire
4

Haskell, 24 23 bytes

f 0=0
f 1=1
f n=f(-n/2)

Define uma função fque retorna 1para potências de -2 e 0outras.

Uma versão em golfe da minha primeira submissão ao outro desafio .

Oportunista
fonte
3

Javascript (ES7), 45 bytes

x=>-1**Math.log2(Math.abs(x))*Math.abs(x)==x
Matthew Roh
fonte
Math.abs (x) é maior que x> 0? X: -x, 11 bytes a 8 bytes. Você também deve poder fazer -2 ** ... em vez de -1 ... para remover o segundo Math.abs (x)
fəˈnɛtɪk
O que é o ES7 específico nisso?
Arjun #
@ DobbyTheFree-Elf, **é.
precisa saber é o seguinte
3

Perl 6 , 21 bytes

{$_==(-2)**(.lsb//0)}

Tente

Expandido:

{  # bare block lambda with implicit parameter 「$_」

  $_                  # is the input
  ==                  # equal to
  (-2)**( .lsb // 0 ) # -2 to the power of the least significant bit of the input
}

Observe que 0.lsbretorna Nilque produz um aviso quando usado como um número; portanto, o operador ou definido  //é usado.
(Pense //como|| uma inclinação diferente)

Uma chamada de método sem invocador, em que um termo é esperado, é implicitamente chamada $_. ( .lsb)

Também trabalha com.msb .

Brad Gilbert b2gills
fonte
Eu gosto deste!
precisa saber é o seguinte
3

Python , 24 bytes

lambda n:n*n&n*n-1<n%3%2

Experimente online!

O truque de bit k&k-1==0verifica se ké uma potência de 2 (ou k==0). Verificando isso k=n*ncomo n*n&n*n-1==0diz-nos seabs(n) é uma potência de 2.

Para ver ainda se né uma potência de -2, precisamos apenas verificar sen%3==1 . Isso funciona porque o mod 3, o valor -2 é igual a 1, então seus poderes são 1. Em contraste, suas negações são 2 mod 3 e, é claro, 0 fornece 0 mod 3.

Combinamos as verificações n*n&n*n-1==0e n%3==1em uma única expressão. O primeiro pode ser escrito com <1for ==0, pois nunca é negativo. O n%3==1é equivalente a n%3%2, dando 0 ou 1. Portanto, podemos combiná-los como n*n&n*n-1<n%3%2.

xnor
fonte
2

R, 22 bytes

Recebe entrada de stdin, retorna TRUEou de FALSEacordo.

scan()%in%(-2)^(0:1e4)

Não tenho 100% de certeza de que seja uma resposta válida, pois só funciona para números inteiros até o limite de tamanho de R e, se os números inteiros fossem ilimitados, não funcionaria. No entanto, as regras declaram:

As regras usuais de estouro de números inteiros se aplicam: sua solução deve ser capaz de trabalhar com números inteiros arbitrariamente grandes em uma versão hipotética (ou talvez real) do seu idioma, na qual todos os números inteiros são ilimitados por padrão, mas se o seu programa falhar na prática devido à implementação não suporta números inteiros tão grandes, que não invalida a solução.

Em uma versão hipotética de R que não permitem inteiros sem limites, então poderíamos usar o código a seguir, para o mesmo número de bytes:

scan()%in%(-2)^(0:Inf)

Obviamente, no R real, o código acima apenas fornece Error in 0:Inf : result would be too long a vector.

rturnbull
fonte
2

bc 88 bytes

bc -l <<< "n=$1;q=l(sqrt(n*n));p=4*a(1);((n<1)*c(q/l(2)*p/2)+(n>1)*(s(q/l(4)*p)))^2==0"

Eu tenho isso em um arquivo neg2.she ele imprime 1para poderes de -2ou 0não

Eu sei que é muito longo, mas foi divertido

Teste

$ for i in {-129..257}; do echo -n "$i: "; ./neg2.sh $i; done | grep ': 1'
-128: 1
-32: 1
-8: 1
-2: 1
1: 1
4: 1
16: 1
64: 1
256: 1

Explicação

O corpo principal tem duas metades, ambas tentando igual a zero para potências de -2.

q=l(sqrt(n*n))               % ln of the absolute value of the input
p=4*a(1)                     % pi: arctan(1) == pi/4
q/l(2) -> l(sqrt(n*n))/l(2)  % change of base formula -- this gives
                             % the power to which 2 is raised to equal
                             % sqrt(n*n). It will be an integer for 
                             % numbers of interest
n<1                          % 1 if true, 0 if false. for negative
                             % numbers check for powers of 2
n>1                          % for positive numbers, check for powers
                             % of 4
c(q/l(2)*p/2)                % cos(n*pi/2) == 0 for integer n (2^n)
s(q/l(4)*p)                  % sin(n*pi) == 0 for integer n (4^n)
(....)^2==0                  % square the result because numbers are
                             % not exactly zero and compare to 0
JoshRagem
fonte
Eu nunca esperava trigonometria! Boa resposta!
perfil completo de Toby Speight
2

Fourier , 53 bytes

I~X1~N~G0(0-2*G~GX*X~PG*G>P{1}{0~O~N}G{X}{1~O0~N}N)Oo

Vou trabalhar no golfe isso mais tarde, mas o esboço disso é:

X = User input
G = N = 1
Loop until N = 0
    G = -2 * G
    P = X*X 
    If G*G > P then
        N = O = 0
    End if
    If G = X then
        O = 1
        N = 0
    End if
End loop
Print O

Onde a saída é 0para falsey e 1para verdade .

Experimente online!

Beta Decay
fonte
Na descrição de algo não seria melhor não usar a variável P e escrever Se G * G> X * X então ...?
RosLuP
@RosLuP Isso seria melhor, mas Fourier simplesmente trataria isso como(G*G > X)*X
Decay Beta
2

Casio BASIC , 76 bytes

Observe que 76 bytes é o que diz minha calculadora.

?→X
0→O
While Abs(X)≥1
X÷-2→X
If X=1
Then 1→O
IfEnd
WhileEnd
O

Este é o meu primeiro empreendimento no Casio BASIC ... Eu nunca percebi que poderia escrever programas decentes em uma calculadora: D

Beta Decay
fonte
1

Python 2.7, 40 bytes

a=input()
while a%-2==0:a/=-2
print a==1

Créditos ao Sr. Xcoder pelo original código de 43 bytes de comprimento. Tive que postar como uma resposta separada, pois não tenho reputação suficiente para comentar.

Koishore Roy
fonte
É meio que a mesma coisa, já que tornei minha resposta universal como universal, por isso funciona tanto no Python 2 quanto no 3. Se você fizesse isso no Python 3, deveria ter adicionado o int(input())que ultrapassaria o limite de a deffunção like. Além disso, no python 3, você deve usar o print()que desperdiçaria 1 byte. É por isso que eu escolhi essa maneira, porque em Python 3 ele fica mais tempo ...
Mr. Xcoder
1

Retina , 27 bytes

+`(1+)\1
$1_
^(1|-1_)(__)*$

Experimente online!

Recebe entrada em unário, o que é bastante padrão para a Retina. As duas primeiras linhas fazem uma conversão parcial unária para binária, com base nas duas primeiras linhas de código da entrada Tutorial (quaisquer 1s estranhos causarão uma falha na correspondência de qualquer maneira), enquanto a última linha verifica uma potência de quatro ou uma potência ímpar negativa de dois.

+`(1+)\1\1\1
$1_
^(-1)?1_*$

Experimente online!

Desta vez eu faço unário parcial para basear quatro conversões. Poderes de quatro acabam como ^1_*$enquanto poderes ímpares negativos de dois acabam como ^-11_*$.

+`\b(1111)*$
$#1$*
^(-1)?1$

Experimente online!

Dessa vez, continuo dividindo por quatro o máximo que posso e verifico 1ou -11no final.

+`\b(1+)\1\1\1$
$1
^(-1)?1$

Experimente online!

Outra maneira de dividir por quatro. E ainda irritantemente 27 bytes ...

Neil
fonte
1

Esquema, 60 bytes

(define(f n)(cond((= 1 n)#t)((<(abs n)1)#f)(#t(f(/ n -2)))))

Solução recursiva.

Penguino
fonte