30
\$\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\$
  • 1
    \$\begingroup\$ Is it also allowed to output "true" instead of "yes" and "false" instead of "no"? \$\endgroup\$ – ProgramFOX Jan 4 '14 at 14:38
  • 2
    \$\begingroup\$ Yes, you can use any positive/negative response. Question is updated. \$\endgroup\$ – gthacoder Jan 4 '14 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\$ – Wayne Conrad Jan 4 '14 at 15:35
  • 1
    \$\begingroup\$ @Wayne just like golfscript's ), or most c-based languages' --. \$\endgroup\$ – Doorknob Jan 4 '14 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 '17 at 22:57

69 Answers 69

13
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Tim Seguine Jan 4 '14 at 22:56
  • 1
    \$\begingroup\$ @Tim: OK, here's one without decrements, then. ;) \$\endgroup\$ – Ilmari Karonen Jan 4 '14 at 23:05
  • \$\begingroup\$ how can this work? For example 7/3 = 2 (0010), so 7 & 2 = 0111 & 0010 = 0010 which clearly the last bit is not 1 \$\endgroup\$ – phuclv Jan 5 '14 at 2:06
  • \$\begingroup\$ @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. \$\endgroup\$ – Ilmari Karonen Jan 5 '14 at 2:08
  • \$\begingroup\$ ah I misread this with "divisible by 2" \$\endgroup\$ – phuclv Jan 5 '14 at 2:25
15
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ Just wondering, what happens if you give it 0 or a negative number? \$\endgroup\$ – aditsu Jan 4 '14 at 21:34
  • \$\begingroup\$ @aditsu I don´t know what infinity mod 1 is, but it certainly shouldn't be zero. \$\endgroup\$ – Tim Seguine Jan 4 '14 at 22:45
  • 1
    \$\begingroup\$ @TimSeguine Mathematica gives me Indeterminate when I try that. \$\endgroup\$ – LegionMammal978 Oct 23 '15 at 19:03
7
\$\begingroup\$

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)
\$\endgroup\$
  • 1
    \$\begingroup\$ 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 ~. \$\endgroup\$ – aditsu Jan 4 '14 at 16:04
  • 1
    \$\begingroup\$ Fails on 1, which is 2^0 \$\endgroup\$ – Joachim Isaksson Jan 4 '14 at 21:01
6
\$\begingroup\$

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}

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

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
\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – ProgramFOX Jan 4 '14 at 15:21
  • \$\begingroup\$ @ProgramFOX: I see. Interesting trick. \$\endgroup\$ – Konrad Borowski Jan 4 '14 at 15:27
  • 1
    \$\begingroup\$ @ProgramFOX But x&~(~0*x) still works. That's only 2 characters longer. \$\endgroup\$ – orlp Jan 5 '14 at 12:24
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Works in Matlab also :) \$\endgroup\$ – jub0bs Jan 5 '14 at 1:01
4
\$\begingroup\$

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

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

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

Python, 31

print 3>bin(input()).rfind('1')
\$\endgroup\$
  • \$\begingroup\$ 31 if you do bin(input()).rfind('1')<3 \$\endgroup\$ – Blender Jan 4 '14 at 21:44
  • \$\begingroup\$ @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... \$\endgroup\$ – boothby Jan 4 '14 at 23:39
  • 1
    \$\begingroup\$ +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. \$\endgroup\$ – Steven Rumbalski Jan 7 '14 at 17:39
4
\$\begingroup\$

C, 48

main(x){scanf("%i",&x);puts(x&~(x*~0)?"F":"T");}
\$\endgroup\$
  • \$\begingroup\$ Can be shorter if unary negate is allowed, is longer if negative constants aren't allowed. Assumes two's complement. \$\endgroup\$ – orlp Jan 4 '14 at 21:26
  • \$\begingroup\$ * 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. \$\endgroup\$ – Kevin Jan 4 '14 at 23:36
  • \$\begingroup\$ There is a -: x*-1. \$\endgroup\$ – klingt.net Jan 5 '14 at 0:24
  • \$\begingroup\$ @klingt.net yes, but that's part of a numerical constant. Technically, as it is worded now, only the operator - is forbidden. \$\endgroup\$ – Kevin Jan 5 '14 at 3:14
  • 1
    \$\begingroup\$ @klingt.net Replaced it with a version that uses no signs. \$\endgroup\$ – orlp Jan 5 '14 at 11:18
4
\$\begingroup\$

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 amusing, though it certainly won't win any golfing competition.

J, 14 15 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)
\$\endgroup\$
  • \$\begingroup\$ This uses addition, which is precluded by the challenge. \$\endgroup\$ – FUZxxl Mar 14 '15 at 17:14
  • \$\begingroup\$ Huh. I've no idea what I was thinking when I wrote this... I've fixed it now so it actually follows the rules. \$\endgroup\$ – FireFly Mar 14 '15 at 22:10
4
\$\begingroup\$

Clip, 9 8 7

!%lnxWO

Reads a number from stdin.

Explanation:

To start with, Z = 0, W = 2 and O = 1. This allows placing of W and O next to each other, whereas using 2 and 1 would be interpreted as the number 21 without a separating space (an unwanted extra character). In Clip, the modulo function (%) works on non-integers, so, to work out if some value v is an integer, you check if v mod 1 = 0. Using Clip syntax, this is written as =0%v1. However, as booleans are stored as 1 (or anything else) and 0, checking if something is equal to 0 is just 'not'ing it. For this, Clip has the ! operator. In my code, v is lnx2. x is an input from stdin, n converts a string to a number and lab is log base b of a. The program therefore translates (more readably) to 0 = ((log base 2 of parseInt(readLine)) mod 1).

Examples:

8

outputs

1

and

10

outputs

0

Edit 1: replaced 0, 1 and 2 with Z, O and W.

Edit 2: replaced =Z with !.

Also:

Pyth, 5

Compresses the Clip version even further, as Pyth has Q for already evaluated input and a log2(a) function instead of just general log(a, b).

!%lQ1
\$\endgroup\$
3
\$\begingroup\$

Javascript (37)

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

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

\$\endgroup\$
  • 1
    \$\begingroup\$ same idea with a for loop (also 37 chars) for(i=prompt();i>1;i/=2){}alert(i==1) \$\endgroup\$ – Math chiller Jan 5 '14 at 6:17
3
\$\begingroup\$

Mathematica (21)

IntegerQ@Log2@Input[]

Without input it is a bit shorter

IntegerQ@Log2[8]

True

IntegerQ@Log2[7]

False

\$\endgroup\$
  • \$\begingroup\$ ⌊#⌋==#&@Log2@Input[] \$\endgroup\$ – alephalpha Jan 5 '14 at 5:53
  • 1
    \$\begingroup\$ @alephalpha That ends up using 24 bytes for the UTF-8 characters. Another 21-byte program is Log2@Input[]~Mod~1==0. \$\endgroup\$ – LegionMammal978 Oct 23 '15 at 19:00
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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..." \$\endgroup\$ – apsillers Jan 4 '14 at 15:36
  • \$\begingroup\$ Doesn't it suffer from numerical inaccuracies? \$\endgroup\$ – Mark Jeronimus Apr 11 '14 at 6:42
  • \$\begingroup\$ @MarkJeronimus: I actually don't know. It could be, but I haven't yet encountered an incorrect result. \$\endgroup\$ – ProgramFOX Apr 11 '14 at 8:41
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ What about 0x2ff, which in base 2 is 1111111111? \$\endgroup\$ – Peter Taylor Jan 4 '14 at 18:52
  • \$\begingroup\$ @PeterTaylor You're right, fixed \$\endgroup\$ – copy Jan 4 '14 at 19:19
  • \$\begingroup\$ 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! \$\endgroup\$ – Math chiller Jan 5 '14 at 6:09
  • \$\begingroup\$ This is kinda cheating but another method: alert(!(Number.MAX_VALUE%prompt())) \$\endgroup\$ – Pluto Mar 27 '15 at 22:21
2
\$\begingroup\$

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

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

\$\endgroup\$
  • \$\begingroup\$ Upvoted because this was my solution as well. \$\endgroup\$ – jscs Jan 4 '14 at 22:02
  • 1
    \$\begingroup\$ What if you replace == with &? \$\endgroup\$ – SimonT Jan 4 '14 at 22:09
  • \$\begingroup\$ @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. \$\endgroup\$ – Gari BN Jan 5 '14 at 8:37
2
\$\begingroup\$

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*$/)
\$\endgroup\$
  • \$\begingroup\$ there's still a "+" in your program \$\endgroup\$ – phuclv Jan 5 '14 at 1:21
  • \$\begingroup\$ 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. \$\endgroup\$ – O-I Jan 5 '14 at 1:27
  • \$\begingroup\$ Great improvement. It seems like it's the best Ruby result so far. I updated the leaders table in the question text. \$\endgroup\$ – gthacoder Jan 5 '14 at 22:24
  • \$\begingroup\$ @gthacoder Just combined steenslag's regex with my binary formatting. Definitely can't take all the credit. \$\endgroup\$ – O-I Jan 5 '14 at 22:28
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ @gthacoder: I made the code smaller, hope you can update you main post to reflect this! \$\endgroup\$ – Kyle Kanos Jan 6 '14 at 2:57
  • \$\begingroup\$ Doesn't this use addition? And doesn't the question, err, forbid that? \$\endgroup\$ – zgrep Sep 12 '17 at 20:33
2
\$\begingroup\$

C# (54 characters)

 Math.Log(int.Parse(Console.ReadLine()),2)%1==0?"Y":"N"
\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – mniip Jan 5 '14 at 5:09
  • \$\begingroup\$ I think you just mean Int32, not ToInt32... \$\endgroup\$ – Chris Jan 5 '14 at 22:56
  • \$\begingroup\$ 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 \$\endgroup\$ – Merin Nakarmi Jan 6 '14 at 1:50
  • 2
    \$\begingroup\$ use int instead of Int32 for 2 fewer characters. \$\endgroup\$ – Rik Jan 7 '14 at 11:25
2
\$\begingroup\$

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

GTB, 46 bytes

2→P`N[@N=Pg;1P^2→P@P>1E90g;2]l;2~"NO"&l;1"YES"
\$\endgroup\$
1
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ boothby's answers uses the same idea as my first, but is shorter :( \$\endgroup\$ – Ivan Anishchuk Jan 4 '14 at 18:02
1
\$\begingroup\$

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)

\$\endgroup\$
  • 1
    \$\begingroup\$ not a%2 can be written as a%2==0. Granted, this would be longer in many languages, but not Python. \$\endgroup\$ – Konrad Borowski Jan 4 '14 at 15:11
  • \$\begingroup\$ @xfix Thanks, tested and updated. \$\endgroup\$ – Joachim Isaksson Jan 4 '14 at 15:12
  • 1
    \$\begingroup\$ or even better, a%2<1. \$\endgroup\$ – boothby Jan 4 '14 at 17:18
  • \$\begingroup\$ you have a space after 2. Removing that would save a byte! \$\endgroup\$ – Keerthana Prabhakaran Apr 7 '17 at 3:45
1
\$\begingroup\$

Python (33)

print int(bin(input())[3:]or 0)<1
\$\endgroup\$
  • \$\begingroup\$ int(bin(input()*2)[3:])<1 also works from the python shell with only 25 chars. \$\endgroup\$ – gmatht Apr 6 '14 at 23:28
1
\$\begingroup\$

Ruby, 33, 28, 25

p /.1/!~gets.to_i.to_s(2)
\$\endgroup\$
1
\$\begingroup\$

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.

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

C, 65 bytes

main(k){scanf("%i",&k);while(k&&!(k%2))k/=2;puts(k==1?"T":"F");}
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Kevin Jan 5 '14 at 0:22
1
\$\begingroup\$

Haskell (52 50)

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

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