47
\$\begingroup\$

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 contest: the answer which has the fewest bytes (in your chosen encoding) is the winner.

\$\endgroup\$
12
  • 19
    \$\begingroup\$ @KritixiLithos I don't see why it should. There is no integer i such that (-2)^i = 2 \$\endgroup\$
    – Fatalize
    Apr 6 '17 at 12:10
  • 2
    \$\begingroup\$ Are the exponents positive or -0.5 should be valid since it's 2^(-1). \$\endgroup\$
    – Mr. Xcoder
    Apr 6 '17 at 12:13
  • 1
    \$\begingroup\$ @Mr.Xcoder, Since inputs are always integer values, a negative exponent won't be required (or possible). \$\endgroup\$ Apr 6 '17 at 12:16
  • 1
    \$\begingroup\$ @SIGSEGV maybe whereas i is not natural \$\endgroup\$
    – Mr. Xcoder
    Apr 6 '17 at 12:55
  • 2
    \$\begingroup\$ @Jason, as many as supported/natural in your language - see the third rule. And it's code-golf because it needs an objective winning criterion to be on-topic here - "a pleasing solution" doesn't cut it (though I do like the Mathematica answer - that surprised me). \$\endgroup\$ Apr 6 '17 at 14:55

52 Answers 52

27
\$\begingroup\$

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.
\$\endgroup\$
2
  • \$\begingroup\$ Does it help to consider that even powers of -2 are integer powers of 4? I like the idea of multiplying by -2 to get everything positive - though disappointed to see no bit-twiddling so far. \$\endgroup\$ Apr 6 '17 at 13:04
  • 6
    \$\begingroup\$ @TobySpeight Treating them as powers of 2 actually saves 5 bytes. I used powers of 4 at first, but Log[4,...] is longer than Log2@... and IntegerQ is longer than EvenQ. \$\endgroup\$ Apr 6 '17 at 13:05
18
\$\begingroup\$

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.
\$\endgroup\$
13
\$\begingroup\$

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≤Vd<B. Here, we will 0-index digits from the right, so every digit adds VdBd to form N. Vd<BVdBd<BBd=Bd+1, therefore every possible N has only one unique representation, if we ignore leading 0s in (N)B.

Here, d=input, B=-2. N=Bd=1Bd=VdBd⇔1=VdVd=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.
\$\endgroup\$
3
  • 2
    \$\begingroup\$ Phew, that explanation took time to write... \$\endgroup\$ Apr 6 '17 at 13:34
  • \$\begingroup\$ I'd hate to see what an explanation for a long program would look like then... \$\endgroup\$
    – boboquack
    Apr 8 '17 at 8:32
  • 1
    \$\begingroup\$ @boboquack Here I am explaining why I use the base conversion stuff. I don't think explanation for long programs would be this long. A post can contain up to 30000 markdown characters, and explanations for longer programs would be more terse anyways. Also, I have read much longer explanations, and they are not that boring. \$\endgroup\$ Apr 8 '17 at 8:38
13
\$\begingroup\$

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!

\$\endgroup\$
14
  • \$\begingroup\$ print g(8) prints False \$\endgroup\$ Apr 6 '17 at 13:02
  • 2
    \$\begingroup\$ @FelipeNardiBatista shouldn't it? \$\endgroup\$
    – Mr. Xcoder
    Apr 6 '17 at 13:04
  • 2
    \$\begingroup\$ sorry, my example was a bad one, print g(4) does the same \$\endgroup\$ Apr 6 '17 at 13:05
  • \$\begingroup\$ Wait, there is a small error, fixing it shortly \$\endgroup\$
    – Mr. Xcoder
    Apr 6 '17 at 13:06
  • 1
    \$\begingroup\$ I've put a ; instead of a newline... sorry for that. Fixed @FelipeNardiBatista \$\endgroup\$
    – Mr. Xcoder
    Apr 6 '17 at 13:08
12
\$\begingroup\$

Python 2, 98 50 bytes

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

Try it online!

\$\endgroup\$
0
11
\$\begingroup\$

Python 2, 35 34 32 bytes

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

Try it online!

\$\endgroup\$
10
\$\begingroup\$

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
\$\endgroup\$
4
  • \$\begingroup\$ Why the downvote? \$\endgroup\$
    – user41805
    Apr 6 '17 at 15:28
  • \$\begingroup\$ @KritixiLithos: Seems like someone has downvoted all golfing languages. \$\endgroup\$
    – Emigna
    Apr 6 '17 at 15:29
  • 7
    \$\begingroup\$ Noticed that too. Although I haven't been around PPCG for long, I've learned that creative and interesting solutions in standard languages are far more appreciated than 3-byte solutions in golfing languages. However, there are some people who (unfortunately) downvote very creative solutions in golfing languages, simply because they think everything is built-in, and don't understand how good the algorithms (although written in golfing languges) are. +1 for the incredible solution @Emigna \$\endgroup\$
    – Mr. Xcoder
    Apr 6 '17 at 15:32
  • \$\begingroup\$ ÄLY(småO for 8. Y(sÄLm¢Z for 8... Nevermind, all 8. \$\endgroup\$ Jul 13 '17 at 14:04
10
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ Heres a small improvement: =IFERROR(-2^IMREAL(IMLOG2(A1)),1)=A1 \$\endgroup\$
    – CallumDA
    Apr 6 '17 at 23:49
  • 1
    \$\begingroup\$ @CallumDA Thanks! I tried to figure a way to use the complex number functions but everything I came up with was longer. \$\endgroup\$ Apr 7 '17 at 3:43
9
\$\begingroup\$

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

\$\endgroup\$
3
  • \$\begingroup\$ Why do I see some errors (before the true/false values) when I click on "Run code snippet"? \$\endgroup\$ Apr 6 '17 at 13:49
  • \$\begingroup\$ @numbermaniac I'm not sure, maybe you're using a browser that doesn't fully support ES6? \$\endgroup\$
    – Tom
    Apr 6 '17 at 13:51
  • \$\begingroup\$ Welp, refreshed and tried again, no errors. Not sure what happened the first time. \$\endgroup\$ Apr 6 '17 at 13:54
9
\$\begingroup\$

C (gcc), 34 29 bytes

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

Try it online!

\$\endgroup\$
0
8
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ 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! \$\endgroup\$ Apr 6 '17 at 15:03
  • 2
    \$\begingroup\$ @Toby Of course! This is code golf, who cares about efficiency? :-D \$\endgroup\$
    – Luis Mendo
    Apr 6 '17 at 15:05
8
\$\begingroup\$

Regex (ECMAScript), 38 37 34 33 bytes

\b(?=(^|x))((x*)\3\3(?=\3$))*x\1$

Try it online!

Takes its input in unary, as an optional - sign followed by a string of x characters, the count of which represents the absolute value of the number. (As such, it is not bijective unary, as zero can be represented in two ways. The regex works with both.)

Sets a flag for whether a negative sign is present. Operating on the absolute value, repeatedly divides by 4 (requiring that there is no remainder), and then asserts that the remaining number is 1 if there was no negative sign, or 2 if there was.

\b                    # Anchor on the border between {start or "-"} and "x"; in the
                      # domain of this problem, it is actually equivalent to
                      # (?<=^(?=x)|-|x$) - so it can anchor on the end instead of the
                      # beginning, but that would result in a non-match.
(?=(^|x))             # \1 = 1 if negative sign is present, 0 if not
(                     # loop the following:
    (x*)\3\3(?=\3$)   # assert tail is divisible by 4; tail = tail / 4
)*                    # iterate as many times as possible (minimum 0)
x                     # tail -= 1
\1                    # tail -= \1
$                     # assert tail==0

Regex (ECMAScript), 36 bytes

^(-(x*)(?=\2$))?((x*)\4\4(?=\4$))*x$

Try it online!

This was the original version I posted; I'm keeping it here, as it's sufficiently different, yet close enough in length, to be interesting.

If it sees a negative sign, it strips it and divides the number by 2 (requiring that there is no remainder). It then asserts that the remaining number is a power of 4.

^
(
    -                 # eat a leading negative sign
    (x*)(?=\2$)       # assert tail is even; tail = tail / 2
)?                    # do the above optionally
# Assert that tail is a power of 4
(                     # loop the following:
    (x*)\4\4(?=\4$)   # assert tail is divisible by 4; tail = tail / 4
)*                    # iterate as many times as possible (minimum 0)
x$                    # assert tail == 1; if this fails to match, the regex engine will
                      # try backtracking the loops, but that cannot result in a match

Regex (PCRE / .NET), 32 bytes

^(-)?((x*)\3\3(?=\3$))*x(?(1)x)$

Try it online! - PCRE2
Try it online! - .NET

Uses essentially the same algorithm as the 33 byte ECMAScript version, but in a more straightforward way, which never matches strings outside the problem's domain.

^
(-)?                  # \1 = negative sign if it is present; unset otherwise
(                     # loop the following:
    (x*)\3\3(?=\3$)   # assert tail is divisible by 4; tail = tail / 4
)*                    # iterate as many times as possible (minimum 0)
x                     # tail = tail - 1
(?(1)x)               # if \1 is set, then tail = tail - 1, else do nothing
$                     # assert tail == 0
\$\endgroup\$
6
\$\begingroup\$

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!

\$\endgroup\$
6
\$\begingroup\$

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));
\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

HP 28s 36 bytes

WHILE DUP ABS 1 > REPEAT 2 NEG / END 1 ==
\$\endgroup\$
2
  • 3
    \$\begingroup\$ Welcome to Code Golf! Nice first answer! \$\endgroup\$ Jul 20 at 2:59
  • \$\begingroup\$ @RedwolfPrograms Thanks! \$\endgroup\$ Jul 20 at 14:46
5
\$\begingroup\$

Python 3, 34 bytes

lambda n:n==(-2)**~-n.bit_length()
\$\endgroup\$
5
\$\begingroup\$

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

\$\endgroup\$
5
\$\begingroup\$

C (gcc), 33 bytes

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

Try it online!

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ The non-recursive way is shorter by 5 bytes: boolean c(int n){while(0==n%-2)n/=-2;return 1==n;}. \$\endgroup\$ Apr 7 '17 at 14:14
  • \$\begingroup\$ @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. \$\endgroup\$ Apr 7 '17 at 14:40
  • \$\begingroup\$ Nicely spotted! \$\endgroup\$ Apr 7 '17 at 14:51
4
\$\begingroup\$

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.

\$\endgroup\$
0
4
\$\begingroup\$

05AB1E, 5 4 bytes

2(вO

Try it online! Beats all other answers.

2(вO  # full program
   O  # push sum of...
  в   # list of base-10 values of base...
 (    # negative...
2     # literal....
  в   # digits of...
      # implicit input
      # implicit output
\$\endgroup\$
3
\$\begingroup\$

Javascript(ES7), 45 bytes

x=>-1**Math.log2(Math.abs(x))*Math.abs(x)==x
\$\endgroup\$
4
  • \$\begingroup\$ 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) \$\endgroup\$ Apr 7 '17 at 1:38
  • \$\begingroup\$ What's ES7 specific in this? \$\endgroup\$
    – Arjun
    Apr 8 '17 at 3:36
  • \$\begingroup\$ @DobbyTheFree-Elf, ** is. \$\endgroup\$
    – Qwertiy
    Apr 10 '17 at 20:11
  • \$\begingroup\$ What interpreter are you using. This code is syntax error on my Firefox. \$\endgroup\$
    – tsh
    Jul 19 at 11:35
3
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ I like this one! \$\endgroup\$
    – tale852150
    Apr 7 '17 at 14:03
3
\$\begingroup\$

Prolog (SWI), 44 bytes

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

Online interpreter

\$\endgroup\$
3
\$\begingroup\$

Julia 0.5, 20 bytes

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

Try it online!

\$\endgroup\$
1
3
\$\begingroup\$

K (ngn/k), 14 bytes

{|/x=*\1,x#-2}

Try it online!

  • *\1,x#-2 return list of -2 raised from 0 to x, i.e. (1 -2 4 -8)
  • |/x= are any items in that list equal to x?
\$\endgroup\$
3
\$\begingroup\$

APL (Dyalog Extended), 10 bytes

-3 thanks to @rak1507

⊢∊¯2*⍳∘|

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Currently fails for 1, can be fixed with ⎕IO←0 and can be golfed to ⊢∊¯2*⍳∘| \$\endgroup\$
    – rak1507
    Dec 20 '20 at 20:54
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.