60
\$\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
  • 22
    \$\begingroup\$ @KritixiLithos I don't see why it should. There is no integer i such that (-2)^i = 2 \$\endgroup\$
    – Fatalize
    Apr 6, 2017 at 12:10
  • 3
    \$\begingroup\$ Are the exponents positive or -0.5 should be valid since it's 2^(-1). \$\endgroup\$
    – Mr. Xcoder
    Apr 6, 2017 at 12:13
  • 2
    \$\begingroup\$ @Mr.Xcoder, Since inputs are always integer values, a negative exponent won't be required (or possible). \$\endgroup\$ Apr 6, 2017 at 12:16
  • 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, 2017 at 14:55
  • 2
    \$\begingroup\$ @TobySpeight I've proposed an alternate version of this challenge here. \$\endgroup\$
    – Jason C
    Apr 6, 2017 at 16:07

64 Answers 64

3
\$\begingroup\$

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
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I never expected trigonometry! Good answer! \$\endgroup\$ Apr 11, 2017 at 8:24
3
\$\begingroup\$

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

\$\endgroup\$
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, 2020 at 20:54
3
\$\begingroup\$

Vyxal r, 6 bytes

ȧʀudec

Try it Online!

Very rude, I know, but it gets the job done.

Explained

ȧʀudec
ȧʀ     # range(0, abs(input) + 1)
  ud   # -2 (-1 * 2). 2N would have worked just the same, but that wouldn't be as funny now would it.
    e  # -2 ** the range (vectorises)
     c # is input in ^
\$\endgroup\$
1
  • \$\begingroup\$ r is for rude \$\endgroup\$
    – Makonede
    Jul 20, 2021 at 16:42
3
\$\begingroup\$

Brachylog, 10 bytes

1|¬0&~×₂ṅ↰

Try it online!

Explanation

A recursive solution:

1|          Either the input is 1 (base case), or...
  ¬0        The input is not 0
    &       and
     ~×₂    some integer times 2 equals the input
        ṅ   Negate that integer
         ↰  and call the predicate recursively
\$\endgroup\$
3
\$\begingroup\$

Brachylog, 7 bytes

ḃb-₂ᵐ×?

Try it online! Or, verify all inputs from -8 to +16.

Explanation

ḃ        Convert to binary, ignoring the sign (so -2 and 2 both become [1,0])
 b       Behead: remove the first element
  -₂ᵐ    Subtract 2 from each element
     ×   Product of that list
      ?  Assert that the result equals the original input number

Some examples to show how this works:

         -8          1    2      0    6
ḃ        [1,0,0,0]   [1]  [1,0]  [0]  [1,1,0]
 b       [0,0,0]     []   [0]    []   [1,0]
  -₂ᵐ    [-2,-2,-2]  []   [-2]   []   [-1,-2]
     ×   -8          1    -2     1    2
  • If the number is \$(-2)^n\$ for some integer \$n\$, ḃb produces a list of \$n\$ zeros; subtracting 2 from each turns it into a list of \$n\$ copies of \$-2\$, and taking the product gives us \$(-2)^n\$ again.
  • If the number is \$-(-2)^n\$, we get \$(-2)^n\$ instead, which doesn't match the input.
  • For any other number, ḃb gives a list containing some amount of \$-2\$ mixed with \$-1\$. The product of this list is \$\pm2^m\$ for some \$m\$; but since our input is not of the form \$\pm2^m\$, it doesn't match.
\$\endgroup\$
3
\$\begingroup\$

TI-Basic, 14 bytes

max(Ans=(-2)^randIntNoRep(0,abs(Ans

Takes input in Ans. randIntNoRep(0, can be replaced with cumSum(1 or rand( for greater compatibility and +4 bytes. - represents the negative sign.

Faster but larger answer that works for larger numbers:

20 19 bytes

Ans=(-2)^int(log(abs(Ans)+not(Ans),2
\$\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\$
2
\$\begingroup\$

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)

\$\endgroup\$
1
  • \$\begingroup\$ w<=(x<0?-x:x)=>w<=x|w<=-x \$\endgroup\$
    – l4m2
    Jan 30, 2022 at 3:37
2
\$\begingroup\$

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

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!

\$\endgroup\$
2
  • \$\begingroup\$ In the algo description not would be better not use P variable and write If G*G > X*X then...? \$\endgroup\$
    – user58988
    Apr 12, 2017 at 15:13
  • \$\begingroup\$ @RosLuP That would be better, but Fourier would simply treat that as (G*G > X)*X \$\endgroup\$
    – Beta Decay
    Apr 12, 2017 at 19:44
2
\$\begingroup\$

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

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

Perl 5 -p, 32 bytes

$.*=-2while(abs)>abs$.;$_=$.==$_

Try it online!

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

Rust, 41 bytes

|x|(|mut e|{while e*e<x*x{e*=-2}e==x})(1)

Try it online!

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

Common Lisp, 51 bytes

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

Recursive version. Try it online.

\$\endgroup\$
2
  • \$\begingroup\$ Try it online! \$\endgroup\$
    – Deadcode
    Mar 22, 2021 at 6:05
  • 1
    \$\begingroup\$ @Deadcode , added, thanks. \$\endgroup\$
    – Renzo
    Mar 22, 2021 at 7:06
2
\$\begingroup\$

Python 3.8 (pre-release), 39 bytes

lambda n:len(x:=bin(n))&1==x.count('1')

Try it online!

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

PowerShell, 102 bytes

$a=$n-replace'-';$p=[convert]::ToString($a,2).length-1;if([math]::pow(-2,$p)-eq$n){return !0}return !1

Try it online!

Ungolfed:

-2..4 | %{                                  # for loop from -2 to 4
    $n=$_                                   # setting n to current number in loop
    $a = $n-replace'-'                      # getting absolute value of num
    $p=[convert]::ToString($a,2).length-1   # converting to binary and counting 0s (2^p)

    if([math]::pow(-2,$p) -eq $n){          # seeing if -2^p is equal to the original num
        return !0                           # returns not 0 or True
    }

    return !1                               # returns not 1 or False
}
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ 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... \$\endgroup\$
    – Mr. Xcoder
    Apr 6, 2017 at 15:27
1
\$\begingroup\$

Cjam, 12 bytes

li_z2mLi-2#=

Explanation comes later.

\$\endgroup\$
1
  • \$\begingroup\$ I think you'll have to use 2b, instead of 2mL, because CJam does have arbitrary-precision integers, so your answer should work for arbitrarily large inputs (but mL won't be able to handle inputs correctly that can't be represented exactly as a 64-bit float). That should save bytes anyway, because you need neither the z, nor the i (although you will need to decrement the result before doing the exponentiation). \$\endgroup\$ Apr 9, 2017 at 18:16
1
\$\begingroup\$

Scheme, 60 bytes

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

Recursive solution.

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

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

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
}
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
1
\$\begingroup\$

Pxem, 53 bytes (filename).

Been a while since my last post of Pxem.

Backslash followed by three digits of octet: a character whose codepoint is so:

._.c\001.y\001.r.-\002.!XX.a.c\003.x.c\004.%.w.d.a\004.$.c\003.a\001.z.d.aY.o

Try it online! Through this problem I noticed a bug in my interpreter. Maybe I need to redesign the interpreter; shortening the code makes maintainance difficult.

Usage

  • As a string of decimal integer from stdin for input.
  • Outputs a letter Y for truthy; nothing for falsey.

How it works: with comments

XX.z
# push an integer of input
.a._XX.z
# NOTE Pxem does not have negative constants
# So negative inputs must be changed to positive
# and then get multiplied by two
.a.c\001.y\001.r.-\002.!XX.aXX.z
# Pxem does not have log() nor something similar
# Just keep dividing by four
# And exit if it seemed not to be 4^n
.a.c\003.xXX.z
  .a.c\004.%.w.d.aXX.z
  .a\004.$XX.z
.a.c\003.aXX.z
# final check for <4
.a\001.z.d.aY.o
\$\endgroup\$
1
\$\begingroup\$

x86_(32/64) machine code, 23 bytes

\x0f\xbc\xc1\xf3\x0f\xb8\xc9\xa8\x01\x74\x06\x01\xc8\x3c\x20\xf5\xc3\x83\xf9\x01\x74\xf9\xc3

Try it online!

This is a kind of problem for which the CPU usually has a built-in instruction to solve it easily but most high level languages don't support it straightforwardly.

Two x86 instructions does the main job.

  • bsf - count trailing zeros (bit-scan forward)
  • popcnt - count bits set

The bsf type of instruction is very common on many architectures with varying names. popcnt is a less popular one, but ARM and RISC-V also supports it as an extension.

algorithm

When you look at the binary representation of an integer power of -2, you can see a pattern.

16 -> 10000
4 -> 100
1 -> 1
-2 -> ..110
-8 -> ..11000
-32 -> ..1100000

When the trailing-zero count is even, there is one bit set. When the trailing-zero count is odd, the sum of this and the set-bit count equals the word size.

assembly

; out: carry flag, in: eax = 1, ecx = arg
entry:
    bsf eax, ecx
    ; if ecx == 0 then eax == 1
    ; relies on an undocumented behaviour (for Intel)
    popcnt ecx, ecx
    test al, 1
    jz even
    add eax, ecx
    cmp al, 32
flip:
    cmc
    ret
even:
    cmp ecx, 1
    je flip
    ret
\$\endgroup\$
1
\$\begingroup\$

J, 21 17 bytes

+/@(=_2:^i.@>:@|)

Try it online!

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

Vyxal, 4 bytes

2Nτ∑

Try it Online!

Port of Makonede's 05AB1E answer, outputting 1 for truthy and anything else for falsy.

   ∑ # Is exactly one of
  τ  # Digits in base...
2N   # -2
     # Truthy?
\$\endgroup\$
2
  • \$\begingroup\$ The challenge asks specifically for a truthy/falsey result, though (or implicitly with the [decision-problem] tag). Unlike 05AB1E, I don't think only 1 is truthy in Vyxal, or is it as well? EDIT: doesn't seem like it, -8 is considered truthy. \$\endgroup\$ Jan 3, 2023 at 12:38
  • \$\begingroup\$ @KevinCruijssen No, but it seems unfair that an output method is considered valid in one language and not in another... \$\endgroup\$
    – emanresu A
    Jan 3, 2023 at 19:37
1
\$\begingroup\$

Pyt, 9 bytes

ĐÅř⁻2~⇹^∈

Try it online!

Đ            implicit input; Đuplicate
 Å           Åbsolute value
  ř          řangify [1,2,...,n]
   ⁻         decrement
    2~       push 2; negate
      ⇹^     swap top two items; element-wise exponentiation
        ∈    is the input in the resultant list?; implicit print
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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