¿Es este número una potencia entera de -2?

41

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

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

Reglas

  • Puede escribir un programa o una función y utilizar cualquiera de los métodos estándar para recibir entradas y proporcionar salidas.

  • Su entrada es un entero único, y la salida debe ser un valor verdadero si el entero es una potencia entera de -2, y un valor falso de lo contrario. No se permite ninguna otra salida (por ejemplo, mensajes de advertencia).

  • Se aplican las reglas habituales de desbordamiento de enteros: su solución debe poder funcionar para enteros arbitrariamente grandes en una versión hipotética (o tal vez real) de su idioma en la que todos los enteros están ilimitados de forma predeterminada, pero si su programa falla en la práctica debido a la implementación no admite enteros tan grandes, eso no invalida la solución.

  • Puede usar cualquier lenguaje de programación , pero tenga en cuenta que estas lagunas están prohibidas de forma predeterminada.

Condición ganadora

Este es un concurso de : la respuesta que tiene la menor cantidad de bytes (en la codificación elegida) es la ganadora.

Toby Speight
fuente
17
@ KritixiLithos No veo por qué debería hacerlo. No hay un número entero ital que(-2)^i = 2
Fatalize
2
Son los exponentes positivos o -0.5deberían ser válidos ya que es 2 ^ (- 1) .
Sr. Xcoder
1
@ Mr.Xcoder, dado que las entradas son siempre valores enteros , no se requerirá (ni será posible) un exponente negativo.
Toby Speight
1
@SIGSEGV tal vez mientras ique no es natural
Sr. Xcoder
2
@ Jason, tantos como sean compatibles / naturales en su idioma - vea la tercera regla. Y es un código de golf porque necesita un criterio ganador objetivo para estar en el tema aquí: "una solución agradable" no es suficiente (aunque me gusta la respuesta de Mathematica, eso me sorprendió).
Toby Speight

Respuestas:

26

Mathematica, 22 bytes

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

Pruébalo en línea! (Usando Mathics en su lugar, donde esta solución también funciona).

Intenté encontrar una solución con operadores bit a bit por un tiempo, y aunque definitivamente existe, terminé encontrando algo que probablemente sea más simple:

  • Max[#,-2#]multiplica la entrada por -2 si es negativa. Multiplicar por otro factor de -2 no cambia si el valor es una potencia de -2 o no. Pero ahora todos los poderes impares de -2 se han convertido en poderes pares de -2 .
  • Pero incluso los poderes de -2 también son poderes de 2 , por lo que podemos usar un simple Log2@...y verificar si el resultado es un entero (para verificar si es un poder de 2 ). Esto ya ahorra dos bytes Log[4,...](otra forma de ver los poderes pares de -2 ).
  • Como una ventaja adicional, verificar si un valor es un número entero par es más corto que solo verificar si es un número entero: podemos ahorrar tres bytes más al usar en EvenQlugar de IntegerQ.
Martin Ender
fuente
¿Ayuda tener en cuenta que incluso las potencias de -2 son potencias enteras de 4? Me gusta la idea de multiplicar por -2 para que todo sea positivo, aunque decepcionado al ver que no hay ningún giro hasta ahora.
Toby Speight
55
@TobySpeight Tratarlos como potencias de 2 en realidad ahorra 5 bytes. Al principio usé poderes de 4, pero Log[4,...]es más largo Log2@...y IntegerQmás largo que EvenQ.
Martin Ender
16

Jalea , 5 bytes

æḟ-2=

Pruébalo en línea!

Cómo 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
fuente
12

Python , 46 bytes

-2 bytes gracias a @ovs.

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

Función con uso:

g(4) # put your number between the brackets

Pruébalo en línea!

Sr. Xcoder
fuente
print g(8)impresionesFalse
Felipe Nardi Batista
2
@FelipeNardiBatista no debería?
Sr. Xcoder
2
lo siento, mi ejemplo fue malo, print g(4)hace lo mismo
Felipe Nardi Batista
Espere, hay un pequeño error, lo solucionaremos en breve
Sr. Xcoder
1
He puesto una en ;lugar de una nueva línea ... perdón por eso. Arreglado @FelipeNardiBatista
Mr. Xcoder
11

Jalea , 6 bytes

b-2S⁼1

Pruébalo en línea!

Esto se basa en cómo Jelly convierte un entero N en cualquier base B arbitraria , al convertir N en una matriz, en la que cada entero es un dígito d de ( N ) B , que puede tener un valor 0≤ V d < B . Aquí, vamos a dígitos 0-índice desde la derecha, por lo que cada dígito añade V d B d para formar N . V d < BV d B d < BB d = B d +1 , por lo tanto, cada posibleN tiene sólo una representación única, si ignoramos que conducen 0s en ( N ) B .

Aquí, d = input, B = -2. N = B d = 1 B d = V d B d ⇔1 = V dV d = 1 y, dado que no estamos agregando ningún otro múltiplo de potencias de B , cualquier otra V sería 0. En este momento, la matriz debe ser un 1 concatenado con d 0s. Dado que Jelly 1 indexa desde la izquierda, debemos verificar si el primer elemento de la matriz es 1 y todos los demás elementos son 0.

Hmm ... todo bien, ¿verdad? ¿No? ¿Que esta pasando? ¡Oh sí, tengo una mejor idea! Primero, tomemos la suma de todos los enteros en la matriz, tratándola como si fuera una matriz entera y no un número en la base -2. Si es 1, significa que solo hay un 1, y todos los demás enteros son 0. Dado que no puede haber ceros a la izquierda, excepto en el caso de 0 -2(donde la suma sería 0 ≠ 1 de todos modos), el primer entero debe ser distinto de cero. El único entero distinto de cero en la matriz es el 1, por lo que debe ser el primero. Por lo tanto, este es el único caso en que la suma de todos los enteros en la matriz sería 1, porque la suma más pequeña posible de un par de enteros positivos es Σ {1,1} = 2, ya que el entero positivo más pequeño es 1 Todos los enteros en una representación base no son negativos, por lo que la única forma en que la suma es 1 es tener solo un 1, y todos los demás enteros son 0. Por lo tanto, podemos verificar si la suma de todos los enteros en el matriz es 1.

Esto es lo que hace el código:

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 el Outgolfer
fuente
1
Uf, esa explicación tomó tiempo para escribir ...
Erik the Outgolfer
No me gustaría ver lo que una explicación para un programa de largo se vería entonces ...
boboquack
1
@boboquack Aquí estoy explicando por qué uso las cosas de conversión de base. No creo que la explicación para programas largos sea tan larga. Una publicación puede contener hasta 30000 caracteres de descuento, y las explicaciones para programas más largos serían más concisas de todos modos. Además, he leído explicaciones mucho más largas, y no son tan aburridas.
Erik the Outgolfer
10

Excel, 40 36 bytes

Guardado 4 bytes por CallumDA

Excel ciertamente puede hacerlo, pero corregir errores agrega 11 bytes

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

La entrada está en la celda A1. La salida es TRUEoFALSE

Si se le permitiera devolver FALSEo un #NUM!error para valores falsos, solo serían 25 bytes:

=-2^IMREAL(IMLOG2(A1))=A1
Tostadas de ingeniero
fuente
Heres una pequeña mejora:=IFERROR(-2^IMREAL(IMLOG2(A1)),1)=A1
CallumDA
1
@CallumDA ¡Gracias! Traté de encontrar una manera de usar las funciones de números complejos, pero todo lo que se me ocurrió fue más largo.
Engineer Toast el
9

05AB1E , 8 bytes

Y(IÄÝm¹å

Pruébalo en línea! o como un conjunto de pruebas

Explicación

Y(         # push -2
  IÄÝ      # push range [0 ... abs(input)]
     m     # element-wise power
      ¹å   # check if input is in the resulting list
Emigna
fuente
¿Por qué el voto negativo?
Kritixi Lithos
@ KritixiLithos: Parece que alguien ha votado en contra de todos los idiomas de golf.
Emigna
66
También me di cuenta de eso. Aunque no he estado cerca de PPCG por mucho tiempo, he aprendido que las soluciones creativas e interesantes en idiomas estándar son mucho más apreciadas que las soluciones de 3 bytes en idiomas de golf. Sin embargo, hay algunas personas que (desafortunadamente) rechazan las soluciones muy creativas en los idiomas de golf, simplemente porque piensan que todo está integrado y no entienden lo buenos que son los algoritmos (aunque escritos en idiomas de golf). +1 por la increíble solución @Emigna
Mr. Xcoder
ÄLY(småOpara 8. Y(sÄLm¢Zpara 8 ... Nevermind, all 8.
Urna de pulpo mágico
9

JavaScript (ES6), 37 28 24 bytes

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

Guardado 4 bytes gracias 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
fuente
¿Por qué veo algunos errores (antes de los valores verdadero / falso) cuando hago clic en "Ejecutar fragmento de código"?
numbermaniac
@numbermaniac No estoy seguro, ¿tal vez estás usando un navegador que no es totalmente compatible con ES6?
Tom
Welp, actualizado e intentado de nuevo, sin errores. No estoy seguro de lo que pasó la primera vez.
numbermaniac
8

MATL , 9 8 bytes

2_y|:q^m

Pruébalo en línea! O verificar todos los casos de prueba .

Cómo funciona

Considere la entrada -8como un ejemplo

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
fuente
Si entiendo su explicación correctamente, entonces, dada la entrada n, esto crea una matriz de tamaño ncomo un paso intermedio. Buen trabajo que la eficiencia no es un criterio aquí!
Toby Speight
2
@Toby ¡Por supuesto! Este es el código de golf, ¿a quién le importa la eficiencia? :-D
Luis Mendo
6

Octava , 28 bytes

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

Esto define una función anónima. El enfoque es similar al de mi respuesta MATL.

Pruébalo en línea!

Luis Mendo
fuente
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

Trabajando con una expresión regular

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

Python 3, 34 bytes

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

JavaScript (ES6), 21 bytes

Una función recursiva que devuelve 0o true.

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

Cómo funciona

Esto no incluye ninguna prueba explícita, como nser impar o abs(n)ser menor que uno, para detener la recursividad temprano cuando la entrada no es una potencia exacta de -2.

Salimos solo cuando nes exactamente igual a 1o 0.

Sin embargo, esto funciona porque cualquier flotador IEEE-754 eventualmente se redondeará 0cuando se divida por 2 (o -2) suficientes veces, debido al flujo inferior aritmético .

Casos de prueba

Arnauld
fuente
4

Java 7, 55 bytes

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

Explicación:

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 de prueba:

Pruébalo aquí

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

Salida:

-2: true
-1: false
0: false
1: true
2: false
3: false
4: true
Kevin Cruijssen
fuente
La forma no recursiva es más corto por 5 bytes: boolean c(int n){while(0==n%-2)n/=-2;return 1==n;}.
Olivier Grégoire
@ OlivierGrégoire Desafortunadamente, eso no funciona n=0en Java, porque 0%-2==0será truey 0/-2sigue 0causando un bucle infinito, por eso agregué la n==0?0>1parte a mi método recursivo.
Kevin Cruijssen
Muy bien visto!
Olivier Grégoire
4

Haskell, 24 23 bytes

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

Define una función fque devuelve 1potencias de -2 y de lo 0contrario.

Una versión de golf de mi primera sumisión al otro desafío .

Oportunista
fuente
3

Javascript (ES7), 45 bytes

x=>-1**Math.log2(Math.abs(x))*Math.abs(x)==x
Matthew Roh
fuente
Math.abs (x) es más largo que x> 0? X: -x, 11 bytes a 8 bytes. También debería poder hacer -2 ** ... en lugar de -1 ... para eliminar el segundo Math.abs (x)
fəˈnɛtɪk
¿Qué es ES7 específico en esto?
Arjun
@ DobbyTheFree-Elf, **es.
Qwertiy
3

Perl 6 , 21 bytes

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

Intentalo

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
}

Tenga en cuenta que 0.lsbdevuelve lo Nilque produce una advertencia cuando se usa como un número, por lo que //se usa el operador definido  .
(Piense //como ||con una inclinación diferente)

Se invoca implícitamente una llamada a método sin invocante donde se espera un término $_. ( .lsb)

También funciona con.msb .

Brad Gilbert b2gills
fuente
¡Me gusta este!
tale852150
3

Python , 24 bytes

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

Pruébalo en línea!

El truco de bits k&k-1==0comprueba si kes una potencia de 2 (o k==0). Verificando esto k=n*ncomo n*n&n*n-1==0nos dice si abs(n)es una potencia de 2.

Para ver más a fondo si nes una potencia de -2, solo necesitamos verificar eso n%3==1. Esto funciona porque mod 3, el valor -2 es igual a 1, por lo que sus poderes son 1. En contraste, sus negaciones son 2 mod 3, y por supuesto 0 da 0 mod 3.

Combinamos los cheques n*n&n*n-1==0y n%3==1en una sola expresión. El primero se puede escribir con <1for ==0, ya que nunca es negativo. El n%3==1es equivalente a n%3%2, dando 0 o 1. Por lo tanto, podemos combinarlos como n*n&n*n-1<n%3%2.

xnor
fuente
2

R, 22 bytes

Toma la entrada de stdin, devuelve TRUEo en FALSEconsecuencia.

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

No estoy 100% seguro de que esta sea una respuesta válida, ya que solo funciona para enteros hasta el límite de tamaño de R, y si los enteros fueran ilimitados, no funcionaría. Sin embargo, las reglas establecen:

Se aplican las reglas habituales de desbordamiento de enteros: su solución debe poder funcionar para enteros arbitrariamente grandes en una versión hipotética (o tal vez real) de su idioma en la que todos los enteros están ilimitados de forma predeterminada, pero si su programa falla en la práctica debido a la implementación no admite enteros tan grandes, eso no invalida la solución.

En una hipotética versión de R que no permiten enteros sin límites, entonces se podría utilizar el siguiente código, para la misma cuenta de bytes:

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

Por supuesto, en R real, el código anterior simplemente da Error in 0:Inf : result would be too long a vector.

rturnbull
fuente
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"

Tengo esto en un archivo neg2.she imprime 1para poderes de -2y de 0otra manera

Sé que es muy largo, pero fue divertido

Prueba

$ 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

Explicación

El cuerpo principal tiene dos mitades, ambas están tratando de igualar cero para potencias 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
fuente
¡Nunca esperé trigonometría! ¡Buena respuesta!
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

Trabajaré en esto más tarde, pero el resumen de esto es:

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

Donde la salida es 0para falsey y 1para la verdad .

Pruébalo en línea!

Decaimiento Beta
fuente
En la descripción de algo, no sería mejor no usar la variable P y escribir Si G * G> X * X entonces ...?
RosLuP
@RosLuP Eso sería mejor, pero Fourier simplemente lo trataría como(G*G > X)*X
Beta Decay
2

Casio BASIC , 76 bytes

Tenga en cuenta que 76 bytes es lo que dice en mi calculadora.

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

Esta es mi primera aventura en Casio BASIC ... Nunca me di cuenta de que podía escribir programas tan decentes en una calculadora: D

Decaimiento Beta
fuente
1

Python 2.7, 40 bytes

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

Créditos al Sr. Xcoder por el código original de 43 bytes de longitud. Tuve que publicar como respuesta separada ya que no tengo suficiente reputación para comentar.

Koishore Roy
fuente
Es casi lo mismo, ya que hice que mi versión de respuesta fuera universal, por lo que funciona tanto en Python 2 como en 3. Si tuviera int(input())que hacer esto en Python 3, debería haber agregado lo que habría superado el límite de la deffunción similar. Además, en python 3, debe usar print()cuál de los dos desperdiciaría. Es por eso que elegí esa manera, porque en Python 3 se alarga ...
Sr. Xcoder
1

Retina , 27 bytes

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

Pruébalo en línea!

Toma entrada en unario, que es bastante estándar para Retina. Las primeras dos líneas realizan una conversión parcial de unario a binario en base a las dos primeras líneas de código de la entrada del Tutorial (cualquier 1s extraño hará que la coincidencia falle de todos modos), mientras que la última línea comprueba una potencia de cuatro o una potencia impar negativa de dos.

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

Pruébalo en línea!

Esta vez hago conversión unaria parcial a base cuatro. Los poderes de cuatro terminan como ^1_*$mientras que los poderes impares negativos de dos terminan como ^-11_*$.

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

Pruébalo en línea!

Esta vez sigo dividiendo entre cuatro tanto como puedo y compruebo por 1o -11al final.

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

Pruébalo en línea!

Otra forma de dividir entre cuatro. Y todavía molesto 27 bytes ...

Neil
fuente
1

Esquema, 60 bytes

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

Solución recursiva.

Penguino
fuente