Est-ce que ce nombre est une puissance entière de -2?

41

Il existe des méthodes astucieuses pour déterminer si un nombre est une puissance de 2. Ce n'est plus un problème intéressant. Déterminons donc si un entier donné est une puissance entière de -2 . Par exemple:

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

Règles

  • Vous pouvez écrire un programme ou une fonction et utiliser l’une des méthodes standard de réception d’entrée et de sortie.

  • Votre entrée est un entier unique et la sortie doit être une valeur de vérité si l'entier est une puissance entière de -2 et une valeur de faux sinon. Aucune autre sortie (par exemple, des messages d'avertissement) n'est autorisée.

  • Les règles habituelles de dépassement d'entier s'appliquent: votre solution doit pouvoir fonctionner avec des entiers arbitrairement grands dans une version hypothétique (ou peut-être réelle) de votre langue dans laquelle tous les entiers sont non liés par défaut, mais si votre programme échoue dans la pratique en raison de la mise en œuvre ne prenant pas en charge des entiers aussi gros, cela n'invalide pas la solution.

  • Vous pouvez utiliser n’importe quel langage de programmation , mais notez que ces échappatoires sont interdites par défaut.

Condition gagnante

Il s’agit d’un concours de : la réponse qui a le moins d’octets (dans l’encodage choisi) est gagnante.

Toby Speight
la source
17
@KritixiLithos Je ne vois pas pourquoi cela devrait l'être. Il n'y a pas d'entier itel que(-2)^i = 2
Fatalize
2
Les exposants sont-ils positifs ou -0.5devraient-ils être valides puisqu'il s'agit de 2 ^ (- 1) .
M. Xcoder
1
@ Mr.Xcoder, Les entrées étant toujours des valeurs entières , un exposant négatif ne sera pas requis (ni possible).
Toby Speight
1
@SIGSEGV peut-être alors que ce in'est pas naturel
Mr. Xcoder
2
@Jason, autant que pris en charge / naturel dans votre langue - voir la troisième règle. Et c'est du code-golf parce qu'il faut un critère objectif gagnant pour être sur le sujet ici - "une solution agréable" ne le coupe pas (même si j'aime bien la réponse de Mathematica - cela m'a surpris).
Toby Speight

Réponses:

26

Mathematica, 22 octets

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

Essayez-le en ligne! (Utilisation des mathématiques à la place, où cette solution fonctionne également.)

J'ai essayé de trouver une solution avec les opérateurs au niveau des bits pendant un certain temps, et bien qu'il en existe une définitivement, j'ai fini par trouver quelque chose qui est probablement plus simple:

  • Max[#,-2#]multiplie l'entrée par -2 si elle est négative. Multiplier par un autre facteur de -2 ne change pas si la valeur est une puissance de -2 ou non. Mais maintenant, tous les impairs de -2 ont été transformés en pairs de -2 .
  • Mais même des puissances de -2 sont même des puissances de 2 , nous pouvons donc utiliser un simple Log2@...et vérifier si le résultat est un entier (pour vérifier s'il s'agit d'une puissance de 2 ). Cela enregistre déjà deux octets de plus Log[4,...](une autre façon de regarder des puissances égales de -2 ).
  • En prime, vérifier si une valeur est un entier pair est plus court que simplement vérifier si c'est un entier: nous pouvons sauvegarder trois octets supplémentaires en utilisant à la EvenQplace de IntegerQ.
Martin Ender
la source
Est-il utile de considérer que même les puissances de -2 sont des puissances entières de 4? J'aime l'idée de multiplier par -2 pour que tout soit positif - bien que déçue de ne pas avoir fait de bêtises à ce jour.
Toby Speight
5
@TobySpeight Les traiter comme des puissances de 2 économise en réalité 5 octets. J'ai utilisé des puissances de 4 au début, mais Log[4,...]est plus long que Log2@...et IntegerQest plus long que EvenQ.
Martin Ender
16

Gelée , 5 octets

æḟ-2=

Essayez-le en ligne!

Comment ça marche

æḟ-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
la source
12

Python , 46 octets

-2 octets grâce à @ovs.

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

Fonction à l'usage:

g(4) # put your number between the brackets

Essayez-le en ligne!

M. Xcoder
la source
print g(8)impressionsFalse
Felipe Nardi Batista
2
@ FelipeNardiBatista devrait pas?
M. Xcoder
2
désolé, mon exemple était mauvais, print g(4)fait de même
Felipe Nardi Batista
Attendez, il y a une petite erreur, la réparer sous peu
Mr. Xcoder
1
J'ai mis un ;au lieu d'une nouvelle ligne ... désolé pour cela. Correction de @FelipeNardiBatista
M. Xcoder le 06
11

Gelée , 6 octets

b-2S⁼1

Essayez-le en ligne!

Ceci est basé sur la façon dont Jelly convertit un entier N en une base quelconque B , en convertissant N en un tableau, dans lequel chaque entier est un chiffre d de ( N ) B , qui peut avoir une valeur 0≤ V d < B . Ici, nous allons chiffres 0-index de la droite, de sorte que chaque chiffre ajoute V d B d pour former N . V d < BV d B d < BB d = B d +1 , donc toutes les possibilités Nn'a qu'une seule représentation unique, si nous négligeons leader dans 0s ( N ) B .

Ici, d = entrée, B = -2. N = B d = 1 B d = V d B d ⇔1 = V dV d = 1, et, puisque nous ne sommes pas ajouter d'autres multiples de pouvoirs de B , tous les autres V serait 0. En ce moment, le tableau doit être un 1 concaténé avec d 0s. Depuis Jelly 1-indexes à gauche, nous devrions vérifier si le 1er élément du tableau est 1 et tous les autres éléments sont 0.

Hmm ... tout va bien, non? Non? Que se passe-t-il? Oh oui, j'ai une meilleure idée! Tout d'abord, prenons la somme de tous les entiers du tableau, en le traitant comme s'il s'agissait d'un tableau d'entiers et non d'un nombre en base -2. Si c'est 1, cela signifie qu'il n'y a qu'un seul 1 et que tous les autres entiers sont 0. Puisqu'il ne peut y avoir de zéros en tête, sauf dans le cas de 0 -2(où la somme serait de toute façon 0 ≠ 1), le premier entier doit être différent de zéro. Le seul entier non nul du tableau est le 1, il doit donc être le premier. Par conséquent, il s'agit du seul cas où la somme de tous les entiers du tableau serait 1, car la plus petite somme possible d'une paire d'entiers positifs est Σ {1,1} = 2, car le plus petit entier positif est 1. Chaque entier d'une représentation de base étant non négatif, la seule manière dont la somme est 1 consiste à n'en avoir qu'un seul et tous les autres entiers à 0. Par conséquent, nous pouvons simplement vérifier si la somme de tous les entiers du tableau est 1.

Voici ce que fait le code:

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 l'Outgolfeur
la source
1
Ouf, cette explication a pris du temps à écrire ...
Erik the Outgolfer
Je détesterais voir à quoi pourrait ressembler une explication pour un long programme alors ...
boboquack
1
@boboquack Ici, j'explique pourquoi j'utilise les trucs de conversion de base. Je ne pense pas que l'explication de longs programmes serait aussi longue. Une publication peut contenir jusqu'à 30000 caractères, et de toute façon, les explications relatives à des programmes plus longs seraient plus concises. De plus, j'ai lu des explications beaucoup plus longues, et elles ne sont pas si ennuyeuses.
Erik l'Outgolfer
10

Excel, 40 36 octets

4 octets enregistrés par CallumDA

Excel peut certainement le faire, mais la correction des erreurs ajoute 11 octets.

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

L'entrée est dans la cellule A1. La sortie est TRUEouFALSE

S'il était autorisé à renvoyer l'une FALSEou l' autre ou une #NUM!erreur pour les valeurs fausses, il ne s'agirait que de 25 octets:

=-2^IMREAL(IMLOG2(A1))=A1
Rôti d'ingénieur
la source
Voici une petite amélioration:=IFERROR(-2^IMREAL(IMLOG2(A1)),1)=A1
CallumDA
1
@ CallumDA Merci! J'ai essayé de trouver un moyen d'utiliser les fonctions numériques complexes, mais tout ce que j'ai créé est plus long.
Ingénieur Toast
9

05AB1E , 8 octets

Y(IÄÝm¹å

Essayez-le en ligne! ou en tant que suite de tests

Explication

Y(         # push -2
  IÄÝ      # push range [0 ... abs(input)]
     m     # element-wise power
      ¹å   # check if input is in the resulting list
Emigna
la source
Pourquoi le vote négatif?
Kritixi Lithos
@KritixiLithos: On dirait que quelqu'un a voté contre toutes les langues de golf.
Emigna
6
Remarqué ça aussi. Bien que je ne sois plus chez PPCG depuis longtemps, j'ai appris que les solutions créatives et intéressantes dans les langages standard sont bien plus appréciées que les solutions à trois octets dans les langages de golf. Cependant, il y a des gens qui (malheureusement) refusent les solutions très créatives dans les langues de golf, simplement parce qu'ils pensent que tout est intégré, et ne comprennent pas la qualité des algorithmes (bien que écrits en golfing languges). +1 pour l'incroyable solution @Emigna
Mr. Xcoder
ÄLY(småOpour Y(sÄLm¢Z8 ... pour 8 ... Nevermind, tous les 8.
Urne Octopus Magique
9

JavaScript (ES6), 37 28 24 octets

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

4 octets sauvés grâce à 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));

À M
la source
Pourquoi vois-je des erreurs (avant les valeurs true / false) lorsque je clique sur "Exécuter l'extrait de code"?
numbermaniac
@numbermaniac Je ne suis pas sûr, vous utilisez peut-être un navigateur qui ne prend pas totalement en charge ES6?
Tom
Welp, rafraîchi et réessayé, pas d'erreur. Pas sûr de ce qui s'est passé la première fois.
numbermaniac
8

MATL , 9 8 octets

2_y|:q^m

Essayez-le en ligne! Ou vérifiez tous les cas de test .

Comment ça marche

Considérez l'entrée -8comme un exemple

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
la source
If I understand your explanation correctly, then given input n, this creates an array of size n as an intermediate step. Good job that efficiency is not a criterion here!
Toby Speight
2
@Toby Of course! This is code golf, who cares about efficiency? :-D
Luis Mendo
6

Octave, 28 bytes

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

This defines an anonymous function. The approach is similar to that in my MATL answer.

Try it online!

Luis Mendo
la source
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

Working with a Regex

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

Python 3, 34 bytes

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

JavaScript (ES6), 21 bytes

A recursive function that returns 0 or true.

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

How it works

This doesn't include any explicit test -- like n being odd or abs(n) being less than one -- to stop the recursion early when the input is not an exact power of -2.

We exit only when n is exactly equal to either 1 or 0.

This does work however because any IEEE-754 float will eventually be rounded to 0 when divided by 2 (or -2) enough times, because of arithmetic underflow.

Test cases

Arnauld
la source
4

Java 7, 55 bytes

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

Explanation:

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

Test code:

Try it here.

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

Output:

-2: true
-1: false
0: false
1: true
2: false
3: false
4: true
Kevin Cruijssen
la source
The non-recursive way is shorter by 5 bytes: boolean c(int n){while(0==n%-2)n/=-2;return 1==n;}.
Olivier Grégoire
@OlivierGrégoire Unfortunately that one doesn't work for n=0 in Java, because 0%-2==0 will be true and 0/-2 is still 0, causing an infinite loop, which is why I added the n==0?0>1 part to my recursive method.
Kevin Cruijssen
Nicely spotted!
Olivier Grégoire
4

Haskell, 24 23 bytes

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

Defines a function f which returns 1 for powers of -2 and 0 otherwise.

A golfed version of my first submission to the other challenge.

Opportunist
la source
3

Javascript(ES7), 45 bytes

x=>-1**Math.log2(Math.abs(x))*Math.abs(x)==x
Matthew Roh
la source
Math.abs(x) is longer than x>0?x:-x, 11 bytes to 8 bytes. You should also be able to do -2**... instead of -1... to remove the second Math.abs(x)
fəˈnɛtɪk
What's ES7 specific in this?
Arjun
@DobbyTheFree-Elf, ** is.
Qwertiy
3

Perl 6, 21 bytes

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

Try it

Expanded:

{  # 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
}

Note that 0.lsb returns Nil which produces a warning when used as a number, so the defined or operator // is used.
(Think of // as || with a different slant)

A method call with no invocant where a term is expected is implicitly called on $_. (.lsb)

Also works with .msb.

Brad Gilbert b2gills
la source
I like this one!
tale852150
3

Python, 24 bytes

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

Try it online!

The bit trick k&k-1==0 checks whether k is a power of 2 (or k==0). Checking this for k=n*n as n*n&n*n-1==0 tells us whether abs(n) is a power of 2.

To further see if n is a power of -2, we need only check that n%3==1. This works because mod 3, the value -2 is equal to 1, so its powers are 1. In contrast, their negations are 2 mod 3, and of course 0 gives 0 mod 3.

We combine the checks n*n&n*n-1==0 and n%3==1 into a single expression. The first can be written with <1 for ==0, since it's never negative. The n%3==1 is equivalent to n%3%2, giving 0 or 1. So, we can combine them as n*n&n*n-1<n%3%2.

xnor
la source
2

R, 22 bytes

Takes input from stdin, returns TRUE or FALSE accordingly.

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

I'm not 100% sure that this is a valid answer, as it only works for integers up to R's size limit, and if the integers were unbounded it wouldn't work. However, the rules state:

The usual integer overflow rules apply: your solution must be able to work for arbitrarily large integers in a hypothetical (or perhaps real) version of your language in which all integers are unbounded by default, but if your program fails in practice due to the implementation not supporting integers that large, that doesn't invalidate the solution.

In a hypothetical version of R which does allow unbounded integers, then we could use the following code, for the same byte count:

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

Of course, in real R, the above code just gives Error in 0:Inf : result would be too long a vector.

rturnbull
la source
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"

I have this in a file neg2.sh and it prints 1 for powers of -2 and 0 otherwise

I know it's really long, but it was fun

Test

$ 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

Explanation

The main body has two halves, both are trying to equal zero for powers of -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
la source
I never expected trigonometry! Good answer!
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

I'll work on golfing this later, but the outline of this is:

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

Where the output is 0 for falsey and 1 for truthy.

Try it online!

Beta Decay
la source
In the algo description not would be better not use P variable and write If G*G > X*X then...?
RosLuP
@RosLuP That would be better, but Fourier would simply treat that as (G*G > X)*X
Beta Decay
2

Casio BASIC, 76 bytes

Note that 76 bytes is what it says on my calculator.

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

This is my first venture into Casio BASIC... I never realised I could write such decent programs on a calculator :D

Beta Decay
la source
1

Python 2.7, 40 bytes

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

Credits to Mr. Xcoder for the original code of length 43 bytes. Had to post as a separate answer since I don't have enough reputation to comment.

Koishore Roy
la source
It's kind of the same thing, since I've made my answer version-universal, so it works in both Python 2 and 3. If you were to do this in Python 3, you should have added int(input()) which would have gone over the limit of the def-like function. Additionally, In python 3, you must use print() which would of wasted 1 byte. That's why I chose that way, because in Python 3 it gets longer...
Mr. Xcoder
1

Retina, 27 bytes

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

Try it online!

Takes input in unary, which is fairly standard for Retina. The first two lines do partial unary to binary conversion based on the first two lines of code from the Tutorial entry (any extraneous 1s will cause the match to fail anyway), while the last line checks for a power of four or a negative odd power of two.

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

Try it online!

This time I do partial unary to base four conversion. Powers of four end up as ^1_*$ while negative odd powers of two end up as ^-11_*$.

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

Try it online!

This time I just keep dividing by four as much as I can and check for 1 or -11 at the end.

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

Try it online!

Another way of dividing by four. And still annoyingly 27 bytes...

Neil
la source
1

Scheme, 60 bytes

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

Recursive solution.

Penguino
la source