# Check whether an integer is a power of 2 without using +,- operations [closed]

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.

## closed as unclear what you're asking by Wheat Wizard, 0 ', ATaco, Stephen, SteadyboxSep 13 '17 at 1:18

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• Is it also allowed to output "true" instead of "yes" and "false" instead of "no"? – ProgramFOX Jan 4 '14 at 14:38
• Yes, you can use any positive/negative response. Question is updated. – gthacoder Jan 4 '14 at 14:42
• 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 '14 at 15:35
• @Wayne just like golfscript's ), or most c-based languages' --. – Doorknob Jan 4 '14 at 15:38
• I know we're 3 years in the future now, but "+/- operators" is non-observable, or at the very least weakly defined. – ATaco Sep 12 '17 at 22:57

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

• 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 '14 at 22:56
• @Tim: OK, here's one without decrements, then. ;) – Ilmari Karonen Jan 4 '14 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 – phuclv Jan 5 '14 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 '14 at 2:08
• ah I misread this with "divisible by 2" – phuclv Jan 5 '14 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)

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

# 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)
• 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 '14 at 16:04
• Fails on 1, which is 2^0 – Joachim Isaksson Jan 4 '14 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}

# 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

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

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.

• Works in Matlab also :) – jub0bs Jan 5 '14 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


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

## Python, 31

print 3>bin(input()).rfind('1')

• 31 if you do bin(input()).rfind('1')<3 – Blender Jan 4 '14 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 '14 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 '14 at 17:39

# C, 48

main(x){scanf("%i",&x);puts(x&~(x*~0)?"F":"T");}

• Can be shorter if unary negate is allowed, is longer if negative constants aren't allowed. Assumes two's complement. – orlp Jan 4 '14 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 '14 at 23:36
• There is a -: x*-1. – klingt.net Jan 5 '14 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 '14 at 3:14
• @klingt.net Replaced it with a version that uses no signs. – orlp Jan 5 '14 at 11:18

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)

• This uses addition, which is precluded by the challenge. – FUZxxl Mar 14 '15 at 17:14
• Huh. I've no idea what I was thinking when I wrote this... I've fixed it now so it actually follows the rules. – FireFly Mar 14 '15 at 22:10

# Clip, 98 7

!%lnxWO


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


Javascript (37)

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


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

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

# Mathematica (21)

IntegerQ@Log2@Input[]


Without input it is a bit shorter

IntegerQ@Log2[8]


True

IntegerQ@Log2[7]


False

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

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

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

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

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

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


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

• Upvoted because this was my solution as well. – Josh Caswell Jan 4 '14 at 22:02
• What if you replace == with &? – SimonT Jan 4 '14 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 '14 at 8:37

### 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/]


p !!('%b'%gets=~/^10*$/)  • there's still a "+" in your program – phuclv Jan 5 '14 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 '14 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 '14 at 22:24 • @gthacoder Just combined steenslag's regex with my binary formatting. Definitely can't take all the credit. – O-I Jan 5 '14 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 • @gthacoder: I made the code smaller, hope you can update you main post to reflect this! – Kyle Kanos Jan 6 '14 at 2:57 • Doesn't this use addition? And doesn't the question, err, forbid that? – zgrep Sep 12 '17 at 20:33 C# (54 characters)  Math.Log(int.Parse(Console.ReadLine()),2)%1==0?"Y":"N"  • 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 '14 at 5:09 • I think you just mean Int32, not ToInt32... – Chris Jan 5 '14 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 '14 at 1:50 • use int instead of Int32 for 2 fewer characters. – Rik Jan 7 '14 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  ## GTB, 46 bytes 2→PN[@N=Pg;1P^2→P@P>1E90g;2]l;2~"NO"&l;1"YES"  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)

• boothby's answers uses the same idea as my first, but is shorter :( – Ivan Anishchuk Jan 4 '14 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)

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

# Python (33)

print int(bin(input())[3:]or 0)<1

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

# Ruby, 33, 28, 25

p /.1/!~gets.to_i.to_s(2)


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

C, 65 bytes

main(k){scanf("%i",&k);while(k&&!(k%2))k/=2;puts(k==1?"T":"F");}

• 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 '14 at 0:22

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