29
\$\begingroup\$

Write a program that checks if the integer is a power of 2.


Sample input:

8

Sample output:

Yes

Sample input:

10

Sample output:

No

Rules:

  • Don't use +,- operations.

  • Use some sort of input stream to get the number. Input is not supposed to be initially stored in a variable.

  • The shortest code (in bytes) wins.

You can use any truthy/falsy response (for instance, true/false). You may assume that input number is greater than 0.

\$\endgroup\$
29
  • 1
    \$\begingroup\$ Is it also allowed to output "true" instead of "yes" and "false" instead of "no"? \$\endgroup\$
    – ProgramFOX
    Jan 4, 2014 at 14:38
  • 2
    \$\begingroup\$ Yes, you can use any positive/negative response. Question is updated. \$\endgroup\$
    – gthacoder
    Jan 4, 2014 at 14:42
  • 1
    \$\begingroup\$ The pred function, when applied to an integer n, returns n - 1. Are functions such as this, which are thin disguises around the forbidden operator, also forbidden? \$\endgroup\$ Jan 4, 2014 at 15:35
  • 1
    \$\begingroup\$ @Wayne just like golfscript's ), or most c-based languages' --. \$\endgroup\$
    – Doorknob
    Jan 4, 2014 at 15:38
  • 2
    \$\begingroup\$ I know we're 3 years in the future now, but "+/- operators" is non-observable, or at the very least weakly defined. \$\endgroup\$
    – ATaco
    Sep 12, 2017 at 22:57

69 Answers 69

1
\$\begingroup\$

Haskell (52 50)

k n=elem n$map(2^)[1..n]
main=interact$show.k.read
\$\endgroup\$
0
1
\$\begingroup\$

Python 2 - 23

x=input();print x&x/3<1

This is a direct port of the golf-script solution above, that beats the current best python solution by 8 characters. The order of operations works out amazingly well here.

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

Bash + dc + grep, 24

dc -e2o?p|grep -c ^10\*$

Reads from stdin. Outputs "1" if a power of 2 and "0" otherwise:

$ dc -e2o?p|grep -c ^10\*$
8
1
$ dc -e2o?p|grep -c ^10\*$
10
0
$ 

Pure Bash (only builtins), 40

[[ `read a;printf %o $a` =~ ^[124]0*$ ]]

Reads from stdin. Returns success (0) if a power of 2 and failure (1) otherwise:

$ [[ `read a;printf %o $a` =~ ^[124]0*$ ]]
8
$ echo $?
0
$ [[ `read a;printf %o $a` =~ ^[124]0*$ ]]
10
$ echo $?
1
$
\$\endgroup\$
1
\$\begingroup\$

Java 7, 124

This is pretty short in Java. Most of the program is just boilerplate code and to read the integer.

class H{public static void main(String[]b){int a=new java.util.Scanner(System.in).nextInt();System.out.println((a&a/3)<1);}}
\$\endgroup\$
1
  • \$\begingroup\$ I know it's been two years, but you can golf it by 2 bytes by simply using print instead of println. \$\endgroup\$ Apr 7, 2017 at 8:08
1
\$\begingroup\$

SmileBASIC, 29 bytes

This is a fairly uncreative and basic (no pun intended) answer. 0 is false, 1 is true.

INPUT N
A=LOG(N,2)?(0OR A)==A

We know that if n is a power of 2, then log2(n) will be an integer. So, this calculates the base-2 log of N, our input number, and checks if it is an integer using the following method.

In SB there are actually two number types, doubles and integers. It also has automatic coercion between doubles and ints depending on the context. When a float is coerced to an int, it simply truncates the fraction and produces an integer which represents the whole part (assuming that number is in the valid integer size–signed 32 bit.) The bitwise OR operator OR expects both of its terms to be integers, so it will automatically cast doubles to ints. Thus, 0 OR double simply produces that double's whole part, which we then check against the original value. If these two are equal, it is a power of two.

\$\endgroup\$
1
  • \$\begingroup\$ A<<0 is shorter and doesn't need parentheses. And you can maybe use > or < instead of == \$\endgroup\$
    – 12Me21
    Feb 9, 2017 at 8:29
1
\$\begingroup\$

Haskell, 47 bytes

(or 21 bytes if input/output can be function argument/return)

f 0=0
f 1=1
f n=f$n/2
main=interact$show.f.read

Returns 1 for powers of 2, and 0 otherwise.

\$\endgroup\$
2
  • \$\begingroup\$ Welcome to PPCG! Check out our Haskell golfing rules. In particular, just functions are fine, you don't need the last line. (Edit: Actually, this challenge is really old (2014) before functions were default. Maybe stick with the program.) \$\endgroup\$
    – xnor
    Apr 7, 2017 at 1:03
  • \$\begingroup\$ @xnor Thanks. I'm aware that this site usually accepts functions as answers, but I was unsure of the rules on function vs full program because the question states "Use some sort of input stream to get the number" and the other haskell answer does the same. Also, I didn't realize that this question was so old. Is it considered rude to neco old questions here? \$\endgroup\$ Apr 7, 2017 at 1:11
1
\$\begingroup\$

Python 2, 29,25 bytes

x=input();print x&x*~0==x

Try it online!

using x&x*~~x/~x is a modified version of x&(~x+1)! Since the later uses + had to use ~x which is equivalent to -x-1!

  • saved 4 bytes by using x*~0 instead of x*~~x/~x!
\$\endgroup\$
0
\$\begingroup\$

PHP, 86 chars

function P($a,$c){if($c==$a)return 1;if($c>$a)return 0;return P($a,$c*2);}echo P(x,2);

Replace x with the number you want to test.

\$\endgroup\$
1
  • \$\begingroup\$ I'm almost sure this can be shorter, by use of ternary operator... then again, ternary operator in PHP is rather strange, so you may need some parenthesis to enforce precedence. \$\endgroup\$ Jan 4, 2014 at 15:36
0
\$\begingroup\$

PHP (58)

<?php $a=fgets(STDIN);while($a%2==0)$a/=2;echo $a==1?1:0;

Simple divide-by-2 loop and remainder check.

\$\endgroup\$
1
  • \$\begingroup\$ This shaves off few characters <?php $a=$argv[1];while(!($a%2))$a/=2;echo $a==1?1:0; Basically $argv[1] instead of fgets(STDIN)` and !($a%2) instead of a%2==0 \$\endgroup\$
    – dkasipovic
    Apr 7, 2014 at 21:19
0
\$\begingroup\$

ActionScript 3 (63 characters*)

var r = Math.log(prompt())/Math.log(2);
return ( (r > 0) && (int(r) == r) );

* I'm going to ignore the fact that AS3 doesn't have a built-in prompt() method, (and hope AS3's lack of implementation doesn't get counted against me).

Extra white-space left in for readability and clarity, but not counted, since they can be removed before execution.

\$\endgroup\$
5
  • \$\begingroup\$ I'm also going to assume that the user didn't enter something funny like NaN. \$\endgroup\$
    – IQAndreas
    Jan 4, 2014 at 18:02
  • \$\begingroup\$ In my opinion, using functions that don't exist is cheating. Just change this into JavaScript code, and replace int(r) with ~~r. \$\endgroup\$ Jan 4, 2014 at 18:43
  • \$\begingroup\$ @xfix No! I refuse to support the use of an un-typed and classless language! Bah, humbug! \$\endgroup\$
    – IQAndreas
    Jan 4, 2014 at 18:46
  • \$\begingroup\$ It's not that you use types or classes here. Also, you have definitely too many parens (return doesn't need parenthesis, and && has bigger precedence than both parenthesis groups). \$\endgroup\$ Jan 4, 2014 at 18:48
  • 1
    \$\begingroup\$ @xfix Fine, you win, but may the records show that I still conscientiously object to the use of JavaScript as a serious programming languages. \$\endgroup\$
    – IQAndreas
    Jan 4, 2014 at 19:23
0
\$\begingroup\$

GTB, 17

With 1/0

`Ar?A>1:A/2→A~A=1

With YES/NO (31)

`Ar?A>1:A/2→A@A=1$~"YES"#~"NO"&
\$\endgroup\$
0
\$\begingroup\$

Scheme 40

(display(=(mod(/(log(read))(log 2))1)0))

It displays #t for true and #f for false (the booleans in Scheme).

For true compatibility you need to add (import(rnrs)) or (import(scheme)) (for r7rs) but it works without that in ikarus and in most REPLs.

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

Perl 53

perl -pe '$_=unpack"b*",pack"L",$_;s!0!!g;s!111*!no!;s!1!yes!'

I can shave off 1 character if i use + in the re, not used for adding.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Use the y/// operator for shorter code: say unpack('b*',pack'l',$_)=~y/1//==1 \$\endgroup\$
    – nwellnhof
    Jan 5, 2014 at 11:43
0
\$\begingroup\$

Golfscript (17 14)

Works from input, using the base builtin for binary conversion and counting ones;

~2base{1=},,1=

Old version, 17 chars, without builtin conversions and without using the decrement operator as a substitute for -;

~2*:a 1{2*.a<}do=
  • ~ lifts the input to an integer on the stack
  • 2* multiplies by 2 to solve 2^0 problem
  • :a sets the variable a to the number to search for and leaves it on stack
  • 1{2*.a<}do sets start value 1 and doubles as long as number<a
  • = compares the number to search for with the number generated
\$\endgroup\$
0
\$\begingroup\$

J - 17 15 bytes - not . ceiling (0==) . mod 1 . log2 . to_i . read keyboard

Result is 1 for True and 0 for False

0=1|2^.".1!:1,1

Yes/No version

(0=1|2^.".1!:1,1){'No',:'Yes'
\$\endgroup\$
1
  • \$\begingroup\$ Something weird seems to have happened to the title of your answer. You might want to fix it. \$\endgroup\$ Jan 7, 2014 at 2:30
0
\$\begingroup\$

D (83 chars with boilerplate, 17 chars to get the solution)

import std.stdio;
void main(){
    int i;
    readf("%d", &i);
    while(!(i%2))i/2;
    writeln(i==1);
}

while the number is even divide by 2, when the result is 2 then it was a power of 2

\$\endgroup\$
2
  • \$\begingroup\$ Um, It says no - operation. I see one. \$\endgroup\$ Jan 4, 2014 at 22:47
  • 1
    \$\begingroup\$ @Tim not anymore you don't :P \$\endgroup\$ Jan 4, 2014 at 23:13
0
\$\begingroup\$

Perl 5 (36 or 29 bytes)

say sprintf('%b',<>)=~/^10*$/?Yes:No

If we don't want to strictly output "Yes" or "No", then we can go shorter:

say sprintf('%b',<>)=~/^10*$/

This second version outputs "1" for true, and "" for false.

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

autohotkey -45bytes in txt file and 48 bytes with editor and lang.

MsgBox % mod(log(k)/log(2), 1) ? "no" : "yes"
\$\endgroup\$
5
  • \$\begingroup\$ Can't you remove the whitespace? this is code-golf after all... \$\endgroup\$
    – mniip
    Jan 5, 2014 at 5:07
  • \$\begingroup\$ code golf? it is not. it is autohotkey. thanks for commenting in btw. \$\endgroup\$
    – user13542
    Jan 5, 2014 at 5:11
  • 1
    \$\begingroup\$ I mean the question is tagged with code-golf, which means that the entries need to be as short as possible \$\endgroup\$
    – mniip
    Jan 5, 2014 at 5:14
  • \$\begingroup\$ You should add a count of the bytes, and use \n=\n to make the language and count be bold. \$\endgroup\$ Jan 5, 2014 at 6:04
  • \$\begingroup\$ if i remove spaces the code will break. \$\endgroup\$
    – user13542
    Jan 5, 2014 at 6:27
0
\$\begingroup\$

C99 94 92 71

int main(){int a,i=1;scanf("%d",&a);while(i){if(a==i)return 1;i<<=1;}}

readable

#include <stdio.h>

int main() {
    int a, i=1;
    scanf("%d",&a);
    while(i){
        if(a==i) return 1;
        i<<=1;
    }
}

What it does

It XORs the input value with a power of 2, until the bit of variable i is shifted out and the value becomes 0. Only if the input value is also a power of 2 (with other words, only one bit in the input was set) the XOR resolves to zero.

The input will be compared with a power of 2 value, that is left shifted in every iteration (in other words multiplied by 2) and returns if both are equal, thus the input is also a power of 2.

On success 1 is returned, 0 otherwise.

Why C99?

Because the return value of a C program is implicitly defined as 0, if not specified, since C99. Compile with: gcc -std=c99 ...

\$\endgroup\$
2
  • \$\begingroup\$ !(a^i) instead of (a^i)==0 \$\endgroup\$
    – Kevin
    Jan 5, 2014 at 3:08
  • 1
    \$\begingroup\$ Actually, I believe you can just do if(a==i) \$\endgroup\$
    – Kevin
    Jan 5, 2014 at 3:10
0
\$\begingroup\$

JavaScript (43 characters when compacted, 35 for some browsers)

Readable version:

var r = Math.log(prompt()) / Math.LN2;
alert( (r > 0) && (~~r == r) );

Compacted version (credit goes to FireFly for helping me shave off even more characters):

r=Math.log(prompt())/Math.LN2;alert(~~r==r)

JS Fiddle: http://jsfiddle.net/IQAndreas/LFYg7/2/

EDIT: On the off chance that you use FireFox 25+ or any other browser with Math.log2(), only 35 characters are required (thanks to xfix for this suggestion):

r=Math.log2(prompt());alert(~~r==r)
\$\endgroup\$
10
  • \$\begingroup\$ You can remove the final semicolon and var. Also, JavaScript has Math.log2() function. \$\endgroup\$ Jan 4, 2014 at 19:23
  • \$\begingroup\$ @xfix Nice, I also used several of your suggestions from the other answer. Thanks! \$\endgroup\$
    – IQAndreas
    Jan 4, 2014 at 19:25
  • \$\begingroup\$ I save two characters by removing the >0, in which case the function will return 0 or false, but my soul is tormented enough by the shortcuts taken in this code anyway. \$\endgroup\$
    – IQAndreas
    Jan 4, 2014 at 19:27
  • \$\begingroup\$ @xfix Regarding your edit, there is no Math.log2() function yet (or at least it's not standard across all browsers), it's still in the draft stage: developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/… \$\endgroup\$
    – IQAndreas
    Jan 4, 2014 at 19:31
  • \$\begingroup\$ Oh, yeah, my mistake. I just prefer to use EcmaScript 6 for my code golf in JavaScript. But yeah, that makes sense - sometimes I mistake ES5 and ES6 stuff. \$\endgroup\$ Jan 4, 2014 at 19:33
0
\$\begingroup\$

Python (40 char)

p=lambda n:n>0and(n<2or n%2<1and p(n/2))

Works for negative number also (returning False)

C (39 chars)

p(n){return n>0&&(n<2||n%2<1&&p(n/2));}

or with trick, (work on old compilers without optimizing, withoput return operator returns last evaluated expression value) (32 chars)

p(n){n>0&&(n<2||n%2<1&&p(n/2));}
\$\endgroup\$
0
\$\begingroup\$

PHP, 55

<? if(fmod(log($argv[1],2),1)==0) echo 1; else echo 0;

Eg:

# php pow2.php 8
1
# php pow2.php 9
0

PHP w/ interactive I/O, 107

<? $h=fopen('php://stdin','r');$n=trim(fgets($h));fclose($h);if(fmod(log($n,2),1)==0) echo 1; else echo 0;
\$\endgroup\$
2
  • 1
    \$\begingroup\$ the OP didn't ask you to output "yes" or "no" so you can shave your code down to: <? echo fmod(log($argv[1],2),1)==0 \$\endgroup\$ Jan 7, 2014 at 13:21
  • \$\begingroup\$ @serakfalcon shaved. Thanks for the suggestion. \$\endgroup\$
    – Sammitch
    Jan 7, 2014 at 17:26
0
\$\begingroup\$

BASH, 48

x=`echo "obase=2;$1"|bc|rev|bc`;echo "$x==1"|bc

Takes input as a command line argument and returns 1 for true and 0 for false. You can easily modify it to echo Yes/No, but the bash if-construct makes it much longer.

\$\endgroup\$
2
  • \$\begingroup\$ 39 characters: x=`bc<<<"obase=2;$1"|rev|bc`;bc<<<$x==1 \$\endgroup\$
    – alexia
    Jul 4, 2014 at 20:43
  • \$\begingroup\$ No need for x at all - 37 bytes: echo `bc<<<"obase=2;$1"|rev|bc`==1|bc \$\endgroup\$ Mar 17, 2015 at 4:18
0
\$\begingroup\$

~-~! - 37

'=|*;~~==%['&*/~~]*|:'&^==~[@|1|]@|0|

I had to improvise with the number input...it's the Unicode value of the character you enter. Teehee.

This uses a recursive /2 solution.

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

Java 143

Thinking binary ( a power of 2 has always only one bit set so the compare with the integer with ionly highest bit set can only return true on powers of 2 (including the ominous 0 :P)

Update: shaved 2 bytes off due to a derp

enum P{public static void main(String[]a){int i=new java.util.Scanner(System.in).nextInt();System.out.print(i==(Integer.highestOneBit(i)*1));}}

Ungolfed

enum P;
{
    public static void main(String[]a)
    {
        int i = new java.util.Scanner(System.in).nextInt();
        System.out.print(i==(Integer.highestOneBit(i)*1));
    }
}
\$\endgroup\$
0
\$\begingroup\$

JavaScript (EcmaScript 6) - 13 Characters

f=x=>!(x&x/3)

Creates a function f that takes a value and returns true (or false) if it is a power of 2 (or not) and will output the answer to the console.

Based on Ilmari Karonen's answer (so I included a few others of my own, below).

EcmaScript 6 can be run on FireFox or SpiderMonkey - no other browser/JavaScript engine yet supports EcmaScript 6 arrow functions. If you want to prompt for input then you can call it as an anonymous function (23 characters):

(x=>!(x&x/3))(prompt())

But it's less characters skip the function bit and just do:

JavaScript - 19 Characters

!((a=prompt())&a/3)

Will do the same as above but should run in all browsers and will prompt for input and output to the console (or in SpiderMonkey, you can replace prompt() [which doesn't exist as SpiderMonkey is command-line based] with readline()).

JavaScript (EcmaScript 6) - 20 Characters

f=x=>x>1?f(x/2):x==1

Creates a function f and, when called, will output the answer to the console.

JavaScript - 29 Characters

for(a=prompt();a>1;)a/=2;a==1

Same as above but will prompt the user for input and output to the console.

JavaScript - 32 Characters

for(a=prompt();!(a%2);)a/=2;a==1

JavaScript - 34 Characters

for(a=prompt();a==(a|0);)a/=2;a==1
\$\endgroup\$
0
\$\begingroup\$

dc, 13 bytes

?[2~0=m]dsmxp

Reads input from STDIN. Input is not explicitly stored in a variable, though it is stored on the stack - not sure if this too much rule-bending.

Successively divides by 2 until a 1 remainder is found. Since dc doesn't have any native concept of truthy/falsey, I'm taking the liberty of defining my own here. 0 means true, any +ve integer means false:

$ for i in 1 2 3 15 16 17 65535 65536; do dc pow2.dc <<< $i; done
0
0
1
7
0
8
32767
0
$ 
\$\endgroup\$
0
\$\begingroup\$

Batch - 24 bytes

Stealing Ilmari's winning GolfScript answer...

@cmd/c"set/a!(%1/3^&%1)"

See explanation here.

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

Note: This question is older than Pyth, so this answer is not eligible to win.

Pyth, 5 bytes

!%lQ1

This is essentially identical to @marinus's APL answer. We take the log base 2 of the input, take it mod 1, and take the logical not.


Pyth, 6 bytes

!stjQ2

This answer converts the input to base 2, removes the first digit, sums the remainder, and takes the logical not.

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

Python (23)

int(bin(input())[3:])<1
\$\endgroup\$
1
  • 2
    \$\begingroup\$ You need a print statement in there... \$\endgroup\$
    – FlipTack
    Feb 9, 2017 at 7:33

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