# 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"? Jan 4 '14 at 14:38
• Yes, you can use any positive/negative response. Question is updated. 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? 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. Sep 12 '17 at 22:57

# 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? 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! # OCaml - 42 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. # 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. 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 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. 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. Jan 4 '14 at 18:43
• @xfix No! I refuse to support the use of an un-typed and classless language! Bah, humbug! 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). 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. 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 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. 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. Jan 4 '14 at 22:47
• @Tim not anymore you don't :P 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... Jan 5 '14 at 5:07
• code golf? it is not. it is autohotkey. thanks for commenting in btw. 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 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. Jan 5 '14 at 6:04
• if i remove spaces the code will break. 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 Jan 5 '14 at 3:08
• Actually, I believe you can just do if(a==i) 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. Jan 4 '14 at 19:23
• @xfix Nice, I also used several of your suggestions from the other answer. Thanks! 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. 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/… 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. 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... Feb 9 '17 at 7:33