Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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 (it is supposed to be typed). Input is not supposed to be initially stored in a variable.

  • The shortest code (in bytes) wins.

P.S. You can use any positive/negative response (for instance, true/false). You may assume that input number is greater than 0.


Thanks to you, guys, this question became very popular and got a bunch of different answers with interesting approaches, so I decided to append some info to make this thread readable. Code Golf is not only programming languages battle, it is also a challenge for different approaches within a single language. I decided to sum up interim results and note the leaders for every programming language for better navigation within the thread.

GTB - 17 characters - Timtech

GolfScript - 6 characters - Ilmari Karonen

PHP - 58 - 58 characters - Joachim Isaksson

JavaScript - 35 characters - copy

Python - 31 characters - boothby

Perl 6 - 17 characters - xfix

Perl 5 - 14 characters - Ilmari Karonen

Octave - 23 characters - Joachim Isaksson

APL - 7 characters - marinus

R - 11 characters - Sven Hohenstein

Mathematica - 21 characters - ybeltukov

K - 24 characters - Kyle Kanos

Ruby - 19 characters - O-I

Scheme - 40 characters - Sylwester

C - 48 characters - nightcracker

Haskell - 50 - Zeta

J - 14 characters - FireFly

D - 83 characters - rachet freak

C# - 58 characters - Merin Nakarmi

AutoHotkey - 45 characters - user13542

This table will be updated with new answers posted.

share|improve this question
1  
Is it also allowed to output "true" instead of "yes" and "false" instead of "no"? –  ProgramFOX Jan 4 at 14:38
2  
Yes, you can use any positive/negative response. Question is updated. –  gthacoder Jan 4 at 14:42
1  
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? –  Wayne Conrad Jan 4 at 15:35
1  
@Wayne just like golfscript's ), or most c-based languages' --. –  Doorknob 冰 Jan 4 at 15:38
1  
Can we output 1 or 0? 'T' or 'F'? –  Mark Plotnick Jan 4 at 15:43

59 Answers 59

up vote 7 down vote accepted

GolfScript, 6 chars, no decrements

~.3/&!

Here's a solution that doesn't use the x & (x-1) method in any form. It uses x & (x/3) instead. ;-) Outputs 0 if false, 1 if true.

Explanation:

  • ~ evals the input string to turn it into a number,
  • . duplicates it (for the subsequent &),
  • 3/ divides it by three (truncating down),
  • & computes the bitwise AND of the divided value with the original, which will be zero if and only if the input is zero or a power of two (i.e. has at most one bit set), and
  • ! logically negates this, mapping zero to one and all other values to zero.

Notes:

  • Per the clarified rules, zero is not a valid input, so this code is OK, even though it outputs 1 if the input is zero.

  • If the GolfScript decrement operator ( is allowed, then the 5-character solution ~.(&! posted by aditsu is enough. However, it seems to go against the spirit of the rules, if not the letter.

  • I came up with the x & (x/3) trick years ago on the Fun With Perl mailing list. (I'm sure I'm not the first to discover it, but I did (re)invent it independently.) Here's a link to the original post, including a proof that it actually works.

share|improve this answer
    
I think it is a bit silly really, golfscript allows one to write the exact solution that the OP wanted to exclude without actually breaking the rules. –  Tim Seguine Jan 4 at 22:56
    
@Tim: OK, here's one without decrements, then. ;) –  Ilmari Karonen Jan 4 at 23:05
    
how can this work? For example 7/3 = 2 (0010), so 7 & 2 = 0111 & 0010 = 0010 which clearly the last bit is not 1 –  Lưu Vĩnh Phúc Jan 5 at 2:06
    
@LưuVĩnhPhúc: No, but the second bit is. Try doing long division by 3 in binary and it's pretty obvious why this always happens if the dividend has more than one bit set. –  Ilmari Karonen Jan 5 at 2:08
    
ah I misread this with "divisible by 2" –  Lưu Vĩnh Phúc Jan 5 at 2:25

APL (7)

Yes, that's 7 bytes. Assume for the moment that I'm using IBM codepage 907 instead of Unicode and then each character is a byte :)

0=1|2⍟⎕

i.e. 0 = mod(log(input(),2),1)

share|improve this answer
    
Just wondering, what happens if you give it 0 or a negative number? –  aditsu Jan 4 at 21:34
    
@aditsu I don´t know what infinity mod 1 is, but it certainly shouldn't be zero. –  Tim Seguine Jan 4 at 22:45

GolfScript, 11 (for 1 (true) and 0 (false))

.,{2\?}%?0>

Put the number on the stack and then run.

GolfScript, 22 (for Yes/No)

.,{2\?}%?0>'Yes''No'if

I love how converting 1/0 to Yes/No takes as much code as the challenge itself :D

Warning: EXTREMELY inefficient ;) It does work fine for numbers up to 10000, but once you get that high you start to notice slight lag.

Explanation:

  • .,: turns n into n 0..n (. duplicate, , 0..n range)
  • {2\?}: to the power of 2
  • %: map "power of 2" over "0..n" so it becomes n [1 2 4 8 16 ...]
  • ?0>: checks to see if the array contains the number (0 is greater than index)
share|improve this answer
1  
1 byte shorter for Yes/No: .,{2\?}%?0<'YesNo'3/=; also I think you're cheating by asking to "Put the number on the stack", you should start with a ~. –  aditsu Jan 4 at 16:04
1  
Fails on 1, which is 2^0 –  Joachim Isaksson Jan 4 at 21:01

Mathematica 28

Numerator[Input[]~Log~2]==1

For integer powers of 2, the numerator of the base 2 log will be 1 (meaning that the log is a unit fraction).

Here we modify the function slightly to display the presumed input. We use # in place of Input[] and add & to define a pure function. It returns the same answer that would be returned if the user input the number in the above function.

    Numerator[#~Log~2] == 1 &[1024]
    Numerator[#~Log~2] == 1 &[17]

True
False

Testing several numbers at a time.

    Numerator[#~Log~2] == 1 &&/@{64,8,7,0}

{True, True, False, False}

share|improve this answer

Octave (15 23)

EDIT: Updated due to user input requirement;

~mod(log2(input('')),1)

Lets the user input a value and outputs 1 for true, 0 for false.

Tested in Octave, should work in Matlab also.

share|improve this answer
    
Works in Matlab also :) –  Jubobs Jan 5 at 1:01

R, 13 11

Based on the Perl solution. Returns FALSE or TRUE.

!log2(i)%%1

The parameter i represents the input variable.

An alternative version with user input:

!log2(scan())%%1
share|improve this answer

GolfScript, 5

Outputs 1 for true, 0 for false. Based on user3142747's idea:

~.(&!

Note: ( is decrement, hopefully it doesn't count as - :)
If it does (and the OP's comments suggest that it might), then please refer to Ilmari Karonen's solution instead.
For Y/N output, append 'NY'1/= at the end (7 more bytes).

share|improve this answer

Perl 6 (17 characters)

say get.log(2)%%1

This program gets a line from STDIN get function, calculates logarithm with base 2 on it (log(2)), and checks if the result divides by 1 (%%1, where %% is divides by operator). Not as short as GolfScript solution, but I find this acceptable (GolfScript wins everything anyway), but way faster (even considering that Perl 6 is slow right now).

~ $ perl6 -e 'say get.log(2)%%1'
256
True
~ $ perl6 -e 'say get.log(2)%%1'
255
False
share|improve this answer
2  
The reason that + and - are forbidden for this challenge, is because if x & (x - 1) is equal to 0, then x is a power of 2. –  ProgramFOX Jan 4 at 15:21
    
@ProgramFOX: I see. Interesting trick. –  xfix Jan 4 at 15:27
    
@ProgramFOX But x&~(~0*x) still works. That's only 2 characters longer. –  orlp Jan 5 at 12:24

Python, 31

print 3>bin(input()).rfind('1')
share|improve this answer
    
31 if you do bin(input()).rfind('1')<3 –  Blender Jan 4 at 21:44
    
@Blender Well-spotted. I'd used 2== because I figured it should work for nonpositive numbers too. That's explicitly not required by the rules, so... –  boothby Jan 4 at 23:39
    
+1. I was going to post print bin(input()).count('1')<2 at a total of 31 characters, but it's too similar to yours. –  Steven Rumbalski Jan 7 at 17:39

I decided to to use another approach, based on the population count or sideways sum of the number (the number of 1-bits). The idea is that all powers of two have exactly one 1 bit, and no other number does. I added a JavaScript version because I found it hilarious, though it certainly won't win any golfing competition.

J, 14 chars (outputs 0 or 1)

1=+/#:".1!:1]1

JavaScript, 76 chars (outputs true or false)

alert((~~prompt()).toString(2).split("").map(Number).filter(Boolean).length)
share|improve this answer

JavaScript, 41 40 characters

l=Math.log;alert(l(prompt())/l(2)%1==0);

How this works: you take the logarithm at base 2 using l(prompt()) / l(2), and if that result modulo 1 is equal to zero, then it is a power of 2.

For example: after taking the logarithm of 8 on base 2, you get 3. 3 modulo 1 is equal to 0, so this returns true.

After taking the logarithm of 7 on base 2, you get 2.807354922057604. 2.807354922057604 modulo 1 is equal to 0.807354922057604, so this returns false.

share|improve this answer
    
You don't need to cast the input to a number; Math.log will do that already: "Each of the following Math object functions applies the ToNumber abstract operator to each of its arguments..." –  apsillers Jan 4 at 15:36
    
@apsillers: Thanks! –  ProgramFOX Jan 4 at 15:48
    
Doesn't it suffer from numerical inaccuracies? –  Mark Jeronimus Apr 11 at 6:42
    
@MarkJeronimus: I actually don't know. It could be, but I haven't yet encountered an incorrect result. –  ProgramFOX Apr 11 at 8:41

Javascript (37)

a=prompt();while(a>1)a/=2;alert(a==1)

Simple script that just divides by 2 repeatedly and checks the remainder.

share|improve this answer
    
same idea with a for loop (also 37 chars) for(i=prompt();i>1;i/=2){}alert(i==1) –  tryingToGetProgrammingStraight Jan 5 at 6:17

JavaScript, 35

Works for bytes.

alert((+prompt()).toString(2)%9==1)

46 character version, Works for 16 bit numbers.

x=(+prompt()).toString(2)%99;alert(x==1|x==10)

The trick works in most dynamic languages.

Explanation: Convert the number to base 2, interpret that string as base 10, do modulo 9 to get the digit sum, which must be 1.

share|improve this answer
    
What about 0x2ff, which in base 2 is 1111111111? –  Peter Taylor Jan 4 at 18:52
    
@PeterTaylor You're right, fixed –  copy Jan 4 at 19:19
    
so the real thing your doing is checking for modulo 10 without a remainder, but you used 9 to shave a character of your code, +1! –  tryingToGetProgrammingStraight Jan 5 at 6:09

Mathematica (21)

IntegerQ@Log2@Input[]

Without input it is a bit shorter

IntegerQ@Log2[8]

True

IntegerQ@Log2[7]

False

share|improve this answer
    
⌊#⌋==#&@Log2@Input[] –  alephalpha Jan 5 at 5:53

Perl 5.10+, 13 + 1 = 14 chars

say!($_&$_/3)

Uses the same method from an old FWP thread as my GolfScript entry. Prints 1 if the input is a power of two, and an empty line otherwise.

Needs to be run with perl -nE; the n costs one extra char, for a total of 14 chars. Alternatively, here's an 18-character version that doesn't need the n:

say!(($_=<>)&$_/3)
share|improve this answer

python 3, 38

print(1==bin(int(input())).count('1'))

python, 32

However, the code doesn't work in every version.

print 1==bin(input()).count('1')

Notice that the solution works also for 0 (print False).

share|improve this answer
    
Upvoted because this was my solution as well. –  Josh Caswell Jan 4 at 22:02
1  
What if you replace == with &? –  SimonT Jan 4 at 22:09
    
@SimonT This is not true. Replacing the '==' with '&' will print 1 for every number that has odd number of '1' in its binary representation. Check for example 7=111. There are 3=11 ones. It will return 11&1 = 1. –  Gari BN Jan 5 at 8:37

C, 48

main(x){scanf("%i",&x);puts(x&~(x*~0)?"F":"T");}
share|improve this answer
    
Can be shorter if unary negate is allowed, is longer if negative constants aren't allowed. Assumes two's complement. –  orlp Jan 4 at 21:26
    
* has higher precedence than binary &, you don't need the parens. And if return value is accepted (just asked) exit(x&x*-1) would be much shorter. –  Kevin Jan 4 at 23:36
    
There is a -: x*-1. –  klingt.net Jan 5 at 0:24
    
@klingt.net yes, but that's part of a numerical constant. Technically, as it is worded now, only the operator - is forbidden. –  Kevin Jan 5 at 3:14
1  
@klingt.net Replaced it with a version that uses no signs. –  orlp Jan 5 at 11:18

Ruby — 17 characters (fourth try)

p /.1/!~'%b'%gets

My current best is a fusion of @steenslag's answer with my own. Below are my previous attempts.

Ruby — 19 characters (third try)

p /10*1/!~'%b'%gets

Ruby — 22 characters (second try)

p !('%b'%gets)[/10*1/]

Ruby — 24 characters (first try)

p !!('%b'%gets=~/^10*$/)
share|improve this answer
    
there's still a "+" in your program –  Lưu Vĩnh Phúc Jan 5 at 1:21
    
I know. :-/ I've asked for clarification whether '+' and '-' are strictly forbidden, or whether they can be used in other contexts besides addition and subtraction. I'm in the process of rewriting regardless. –  O-I Jan 5 at 1:27
    
Great improvement. It seems like it's the best Ruby result so far. I updated the leaders table in the question text. –  gthacoder Jan 5 at 22:24
    
@gthacoder Just combined steenslag's regex with my binary formatting. Definitely can't take all the credit. –  O-I Jan 5 at 22:28

K/Kona (24 17)

d:{(+/(2_vs x))~1

Returns 1 if true and 0 if false. Any power of 2 has a single bit equal to 1:

2_vs'_(2^'(!10))
(,1
1 0
1 0 0
1 0 0 0
1 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0)

(this prints out all the powers of 2 (from 0 to 9) in binary)

So I sum up all the components of the binary expression of x and see if it's equal to 1; if yes then x=2^n, otherwise nope.

...knew I could make it smaller

share|improve this answer
    
@gthacoder: I made the code smaller, hope you can update you main post to reflect this! –  Kyle Kanos Jan 6 at 2:57

C# (54 characters)

 Math.Log(int.Parse(Console.ReadLine()),2)%1==0?"Y":"N"
share|improve this answer
    
The task clearly states that input is not stored in a variable, it should be obtained from an input stream of some kind (like stdin), also, this is code-golf, try shortening your code a little, at least by removing whitespace –  mniip Jan 5 at 5:09
    
Thanks mniip, I edited it to meet the requirement. –  Merin Nakarmi Jan 5 at 5:36
    
I think you just mean Int32, not ToInt32... –  Chris Jan 5 at 22:56
    
Ya ya. Thanks for pointing out Chris. Earlier it was Convert.ToInt32 and I wanted to change it to Int32.Parse to shorten it. :D –  Merin Nakarmi Jan 6 at 1:50
2  
use int instead of Int32 for 2 fewer characters. –  Rik Jan 7 at 11:25

Rebmu (9 chars)

z?MOl2A 1

Test

>> rebmu/args [z?MOl2A 1] 7
== false

>> rebmu/args [z?MOl2A 1] 8 
== true

>> rebmu/args [z?MOl2A 1] 9 
== false

Rebmu is a constricted dialect of Rebol. The code is essentially:

z? mo l2 a 1  ; zero? mod log-2 input 1

Alternative

14 chars—Rebmu does not have a 'mushed' bitwise AND~

z?AND~aTIddA 3

In Rebol:

zero? a & to-integer a / 3
share|improve this answer

GTB, 46 bytes

2→P`N[@N=Pg;1P^2→P@P>1E90g;2]l;2~"NO"&l;1"YES"
share|improve this answer

Python, 35

print bin(input()).strip('0')=='b1'

Doesn't use not only +/- operations, but any math operations aside from converting to binary form.

Other stuff (interesting, but not for competition):

I have also a regexp version (61):

import re;print re.match(r'^0b10+$',bin(input())) is not None

(Love the idea, but import and match function make it too long)

And nice, but boring bitwise operations version (31):

x=input();print x and not x&~-x

(yes, it's shorter, but it uses ~-x for decrement which comtains - operation)

share|improve this answer
    
boothby's answers uses the same idea as my first, but is shorter :( –  Ivan Anishchuk Jan 4 at 18:02

Python 2.7 (30 29 39 37)

EDIT: Updated due to user input requirement;

a=input()
while a>1:a/=2.
print a==1

Brute force, try to divide until =1 (success) or <1 (fail)

share|improve this answer
1  
not a%2 can be written as a%2==0. Granted, this would be longer in many languages, but not Python. –  xfix Jan 4 at 15:11
    
@xfix Thanks, tested and updated. –  Joachim Isaksson Jan 4 at 15:12
1  
or even better, a%2<1. –  boothby Jan 4 at 17:18

Python (33)

print int(bin(input())[3:]or 0)<1
share|improve this answer
    
int(bin(input()*2)[3:])<1 also works from the python shell with only 25 chars. –  gmatht Apr 6 at 23:28

Ruby, 33, 28, 25

p /.1/!~gets.to_i.to_s(2)
share|improve this answer

APL (12 for 0/1, 27 for yes/no)

≠/A=2*0,ιA←⍞ 

or, if we must output text:

3↑(3x≠/A=2*0,ιA←⍞)↓'YESNO '

Read in A. Form a vector 0..A, then a vector 20..2A (yes, that's way more than necessary), then a vector comparing A with each of those (resulting in a vector of 0's and at most one 1), then xor that (there's no xor operator in APL, but ≠ applied to booleans will act as one.) We now have 0 or 1.

To get YES or NO: multiply the 0 or 1 by 3, drop this number of characters from 'YESNO ', then take the first 3 characters of this.

share|improve this answer

C, 65 bytes

main(k){scanf("%i",&k);while(k&&!(k%2))k/=2;puts(k==1?"T":"F");}
share|improve this answer
    
You can cut off 5 chars by using main(k){..., relying on the implicit int typing. It might be UB, but this is code golf. NEVER use something like that in production, of course. –  Kevin Jan 5 at 0:22

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
$
share|improve this answer

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.

share|improve this answer
    
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. –  xfix Jan 4 at 15:36

protected by Community Jan 5 at 19:41

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

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