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

• 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

# OCaml - 43 or 45

Since no-one has submitted an OCaml solution, I submit one inspired by nightcrackers C solution.

There is some debate as to whether the operator - includes unary negation. Other entries have managed to sidestep the issue by finding a solution that is equally short without unary negation. I instead give two answers:

let x=read_int()in 0=x land lnot(x*(-1));;

and

let x=read_int()in 0=x land lnot(x*lnot 0);;

the ;; ends a group of statements in the Ocaml interpreter and causes the result to be printed as - : bool = false or - : bool = true, which are clear negative/positive answers as required by the question.

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

# 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
main=interact$show.f.read  Returns 1 for powers of 2, and 0 otherwise. • 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.) – xnor Apr 7 '17 at 1:03 • @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? – Opportunist Apr 7 '17 at 1:11 # 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! # 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. • 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. – Konrad Borowski Jan 4 '14 at 15:36 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. • 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 – dkasipovic Apr 7 '14 at 21:19

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

• I'm also going to assume that the user didn't enter something funny like NaN. – IQAndreas Jan 4 '14 at 18:02
• In my opinion, using functions that don't exist is cheating. Just change this into JavaScript code, and replace int(r) with ~~r. – Konrad Borowski Jan 4 '14 at 18:43
• @xfix No! I refuse to support the use of an un-typed and classless language! Bah, humbug! – IQAndreas Jan 4 '14 at 18:46
• 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). – Konrad Borowski Jan 4 '14 at 18:48
• @xfix Fine, you win, but may the records show that I still conscientiously object to the use of JavaScript as a serious programming languages. – IQAndreas Jan 4 '14 at 19:23

## 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"&  # 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. ## 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. • Use the y/// operator for shorter code: say unpack('b*',pack'l',$_)=~y/1//==1 – nwellnhof Jan 5 '14 at 11:43

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

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

• Something weird seems to have happened to the title of your answer. You might want to fix it. – Ilmari Karonen Jan 7 '14 at 2:30

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

import std.stdio;
void main(){
int 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

• Um, It says no - operation. I see one. – Tim Seguine Jan 4 '14 at 22:47
• @Tim not anymore you don't :P – ratchet freak Jan 4 '14 at 23:13

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

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

MsgBox % mod(log(k)/log(2), 1) ? "no" : "yes"

• Can't you remove the whitespace? this is code-golf after all... – mniip Jan 5 '14 at 5:07
• code golf? it is not. it is autohotkey. thanks for commenting in btw. – user13542 Jan 5 '14 at 5:11
• I mean the question is tagged with code-golf, which means that the entries need to be as short as possible – mniip Jan 5 '14 at 5:14
• You should add a count of the bytes, and use \n=\n to make the language and count be bold. – luser droog Jan 5 '14 at 6:04
• if i remove spaces the code will break. – user13542 Jan 5 '14 at 6:27

## C99 9492 71

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


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

• !(a^i) instead of (a^i)==0 – Kevin Jan 5 '14 at 3:08
• Actually, I believe you can just do if(a==i) – Kevin Jan 5 '14 at 3:10

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

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)

• You can remove the final semicolon and var. Also, JavaScript has Math.log2() function. – Konrad Borowski Jan 4 '14 at 19:23
• @xfix Nice, I also used several of your suggestions from the other answer. Thanks! – IQAndreas Jan 4 '14 at 19:25
• 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. – IQAndreas Jan 4 '14 at 19:27
• @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/… – IQAndreas Jan 4 '14 at 19:31
• 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. – Konrad Borowski Jan 4 '14 at 19:33

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


<? 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;


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

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


# 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


# 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
\$


## Batch - 24 bytes

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


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

# Python (23)

int(bin(input())[3:])<1

• You need a print` statement in there... – FlipTack Feb 9 '17 at 7:33