Is this number an integer power of -2?

Question

There are clever ways of determining whether a number is a power of 2. That's no longer an interesting problem, so let's determine whether a given integer is an integer power of -2. For example:

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

Rules

• You may write a program or a function and use any of the standard methods of receiving input and providing output.

• Your input is a single integer, and output must be a truthy value if the integer is an integer power of -2, and a falsy value otherwise. No other output (e.g. warning messages) is permitted.

• 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.

• You may use any programming language, but note that these loopholes are forbidden by default.

Winning condition

This is a code-golf contest: the answer which has the fewest bytes (in your chosen encoding) is the winner.

Answer 1

Mathematica, 22 bytes

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

Try it online! (Using Mathics instead, where this solution also works.)

I tried to find a solution with bitwise operators for a while, and while one definitely exists, I ended up finding something which is probably simpler:

• Max[#,-2#] multiplies the input by -2 if it's negative. Multiplying by another factor of -2 doesn't change whether the value is a power of -2 or not. But now all odd powers of -2 have been turned into even powers of -2.
• But even powers of -2 are also even powers of 2, so we can use a simple Log2@... and check if the result is an integer (to check whether it's a power of 2). This already saves two bytes over Log[4,...] (another way to look at even powers of -2).
• As an added bonus, checking whether a value is an even integer is shorter than just checking whether it's an integer: we can save three more bytes by using EvenQ instead of IntegerQ.

Answer 2

Jelly, 5 bytes

æḟ-2=

Try it online!

How it works

æḟ-2=  Main link. Argument: n

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

Answer 3

Python, 46 bytes

-2 bytes thanks to @ovs.

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

Function with usage:

g(4) # put your number between the brackets

Try it online!

Answer 4

Python 2, 98 50 bytes

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

Try it online!

Answer 5

Jelly, 6 bytes

b-2S⁼1

Try it online!

This is based on how Jelly converts an integer N to any arbitrary base B, doing so by converting N to an array, in which each integer is a digit d of (N)_B, which can have a value 0≤V_d<B. Here, we will 0-index digits from the right, so every digit adds V_dB^d to form N. V_d<B⇔V_dB^d<BB^d=B^d+1, therefore every possible N has only one unique representation, if we ignore leading 0s in (N)_B.

Here, d=input, B=-2. N=B^d=1B^d=V_dB^d⇔1=V_d⇔V_d=1, and, since we're not adding any other multiples of powers of B, every other V would be 0. Right now, the array should be a 1 concatenated with d 0s. Since Jelly 1-indexes from the left, we should check whether the array's 1st element is 1, and all other elements are 0.

Hmm... all good, right? No? What's going on? Oh yeah, I have a better idea! First, let's take the sum of all of the integers in the array, treating it as if it was an integer array and not a number in base -2. If it is 1, it means that there is only one 1, and all other integers are 0. Since there can't be leading zeroes, except in the case of 0_-2 (where the sum would be 0≠1 anyways), the 1st integer must be non-zero. The only non-zero integer in the array is the 1, so it must be the first one. Therefore, this is the only case that the sum of all of the integers in the array would be 1, because the smallest possible sum of a pair of positive integers is Σ{1,1}=2, since the smallest positive integer is 1. Every integer in a base representation is non-negative, so the only way the sum is 1 is to only have one 1, and all other integers are 0. Therefore, we can just check if the sum of all of the integers in the array is 1.

Here is what the code does:

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.

Answer 6

Python 2, 35 34 32 bytes

f=lambda n:n==1or n!=n%2<f(n/-2)

Try it online!

Answer 7

Excel, 40 36 bytes

^{Saved 4 bytes by CallumDA}

Excel can certainly do it but correcting errors adds 11 bytes

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

Input is in cell A1. Output is TRUE or FALSE

If it was allowed to return either FALSE or #NUM! error for false values, it would be only 25 bytes:

=-2^IMREAL(IMLOG2(A1))=A1

Answer 8

JavaScript (ES6), 37 28 24 bytes

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

Saved 4 bytes thanks to 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));

Answer 9

C (gcc), 34 29 bytes

f(n){n=n%2?n==1:f(n?n/-2:2);}

Try it online!

Answer 10

05AB1E, 8 bytes

Y(IÄÝm¹å

Try it online! or as a Test suite

Explanation

Y(         # push -2
  IÄÝ      # push range [0 ... abs(input)]
     m     # element-wise power
      ¹å   # check if input is in the resulting list

Answer 11

MATL, 9 8 bytes

2_y|:q^m

Try it online! Or verify all test cases.

How it works

Consider input -8 as an example

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

Answer 12

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!

Answer 13

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

Answer 14

Python 3, 34 bytes

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

Answer 15

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

f=n=>n==1||n&&f(n/-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));

Answer 16

C (gcc), 33 bytes

f(n){return n%2?n==1:n&&f(n/-2);}

Try it online!

Answer 17

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

Answer 18

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.

Answer 19

Javascript(ES7), 45 bytes

x=>-1**Math.log2(Math.abs(x))*Math.abs(x)==x

Answer 20

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.

Answer 21

Prolog (SWI), 44 bytes

p(X):-X=1;X\=0,X mod 2=:=0,Z is X/(-2),p(Z).

Online interpreter

Answer 22

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.

Answer 23

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.

Answer 24

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

Answer 25

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!

Answer 26

Julia 0.5, 20 bytes

!n=n∈(-2).^(0:n^2)

Try it online!

Answer 27

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

Answer 28

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.

Answer 29

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...

Answer 30

Scheme, 60 bytes

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

Recursive solution.

Answer 31

Alice, 12 bytes, non-competing

/o|\ntzR2
@i

Try it online!

Explanation

Alice has a fairly weird built-in, which was added because I needed something that goes well thematically with the string operation "discard everything up to this substring". That operation is "drop small factors" and what it does for positive x and y is that it divides x by all of its prime factors less than or equal to y. But if y is negative, then Alice tries negative prime factors greater than or equal to y instead, which means that every time a prime factor is removed, the sign of x changes. So if we use -2 as the second argument, we'll end up with 1 if and only if the input is a power of -2 (if the input is not a power of two, other factors will remain in the end, and if it has the wrong sign, we'll end up with -1 instead of 1).

The rest of the program is just a bit of weird control flow.

/   Reflect southeast. Switch to Ordinal.
i   Read all input as a string.
    Reflect off boundary, move northeast.
|   Reflect northwest.
    Reflect off boundary, move southwest.
i   Read all input as a string, but there's no input left, so this pushes "".
    Reflect off boundary, move northwest.
/   Reflect west. Switch to Cardinal.
    Wrap around to the end of line 1.
2R  Push -2. (Really: push 2, negate.)
z   Drop small factors. When trying to find a second integer argument,
    this discards the empty string and then implicitly converts the input
    string to an integer. Turns only valid inputs to 1.
tn  Decrement, logical NOT. Effectively an "equals 1?" check.
\   Reflect southwest. Switch to Ordinal.
    Reflect off boundary, move northwest.
o   Implicitly convert result to a string and print it. 
    Reflect off boundary, move southwest.
@   Terminate the program.

Answer 32

Clojure, 57 bytes

(defn i[n](if(= n 1)true(if(=(int n)0)false(i(/ n -2)))))

Try it online!

Full function, with annotations:

;; Define function `is-pow?` with 1 argument, `n`
(defn is-pow? [n]
  ;; If n = 1, that means it's a power of -2,
  ;; so we return true
  (if (= n 1) true
    ;; When we recursively call the function,
    ;; -1 > n > 1. `int` rounds up when the number
    ;; is negative (`(int -1/2)` = 0), and rounds down
    ;; when the number is positive. It also catches
    ;; the edgecase of 0.
    (if (= (int n) 0) false
      ;; If n made it to here, n < -1 or n > 1 - we have
      ;; to call the function recursively.
      (is-pow? (/ n -2)))))

Answer 33

Axiom, 50 bytes

g(n:INT):INT==(n=0 or n=1=>n;n rem 2=0=>g(n/-2);0)

It would return 0 if n is not power of (-2), else return 1; exercises

(70) -> n:=-10000;repeat(if g(n)=1 then output n; n>10000=>break;n:=n+1)
   - 8192
   - 2048
   - 512
   - 128
   - 32
   - 8
   - 2
   1
   4
   16
   64
   256
   1024
   4096

Answer 34

Pyth, 7 bytes

!tsjQ_2

Test suite

Explanation:

     _2   # -2
   jQ     # Cast input to that base
          # Iff input is a power of -2, then jQ_2 returns something of the form [1]+[0]*n
          # where n is the power of -2
          # This is also the only situation in which the sum of that is 1
!ts       # so we check for that: is the (s)um equal to 1 (or, equivalently, "!(sum - 1)" )

Answer 35

Jelly, 6 bytes

AḶ-2*i

Try it online!

Explanation:

        Argument: -8
A       Get the absolute value of n             8
 Ḷ      Create a range from 0 to that number-1  0, 1, 2, 3, 4, 5, 6, 7
  -2*   converts that range into the list       -2^0, -2^1, ..., -2^7
     i  Returns >0 if n is in this range, 0 otherwise.

Dennis pointed out a flaw in my approach, which I fixed by taking the absolute value of the input for the range generation.

Answer 36

Common Lisp, 51 bytes

(defun f(n)(or(= 1 n)(and(< 1(abs n))(f(/ n -2)))))

Recursive version.

Answer 37

Excel, 28 bytes

=(-2)^INT(LOG(ABS(B2),2))=B2

Or using approach from @Martin Ender's Mathematica approach:

29 bytes

=ISEVEN(LOG(MAX(B1,-2*B1),2))

Answer 38

C#, 104 107 bytes

+3 bytes, for using system, and finding another method to count bits

using System;b=>Enumerable.Range(0,1+(int)Math.Log(int.MaxValue,2)).Select(x=>Math.Pow(-2,x)).Any(x=>b==x);

It uses Linq to calculate all of -2-s integer powers, and then to test if the input is one them. It would be a bit shorter, if it didn't have to work in a theoretical version, where int can be of any size. Ungolfed:

bool IsPowerOfMinus2(int number)
{
    return Enumerable.Range(0, 2 + (int)Math.Log(int.MaxValue, 2))
        // We generate an IEnumerable, with values from 0 to the length of 
        // maximum number in binary. We need to add one, because we need to
        // know, how many integers to 
        .Select(x => Math.Pow(-2, x))
        //Replace every number with -2 raised to the number
        .Any(x => number == x);    
        //Determine, if the input is one of them
}

Answer 39

Cjam, 12 bytes

li_z2mLi-2#=

Explanation comes later.

Answer 40

Javascript ES6, 51 50 chars

Not very short, but I hope interesting :)

x=>eval(`for(w=q=1;w<=(x<0?-x:x);w*=2,q*=-2)q==x`)

Test:

f=x=>eval(`for(w=q=1;w<=(x<0?-x:x);w*=2,q*=-2)q==x`)
for(x=-2049; x<2049; ++x) if(f(x)) console.log(x)