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"? Commented Jan 4, 2014 at 14:38
• Yes, you can use any positive/negative response. Question is updated. Commented Jan 4, 2014 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? Commented Jan 4, 2014 at 15:35
• @Wayne just like golfscript's ), or most c-based languages' --. Commented Jan 4, 2014 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. Commented Sep 12, 2017 at 22:57

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


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 Commented Apr 7, 2017 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? Commented Apr 7, 2017 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. – null Commented Jan 4, 2014 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 Commented Apr 7, 2014 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. Commented Jan 4, 2014 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.
– null
Commented Jan 4, 2014 at 18:43
• @xfix No! I refuse to support the use of an un-typed and classless language! Bah, humbug! Commented Jan 4, 2014 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).
– null
Commented Jan 4, 2014 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. Commented Jan 4, 2014 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 Commented Jan 5, 2014 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. Commented Jan 7, 2014 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. Commented Jan 4, 2014 at 22:47
• @Tim not anymore you don't :P Commented Jan 4, 2014 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... Commented Jan 5, 2014 at 5:07
• code golf? it is not. it is autohotkey. thanks for commenting in btw. Commented Jan 5, 2014 at 5:11
• I mean the question is tagged with code-golf, which means that the entries need to be as short as possible Commented Jan 5, 2014 at 5:14
• You should add a count of the bytes, and use \n=\n to make the language and count be bold. Commented Jan 5, 2014 at 6:04
• if i remove spaces the code will break. Commented Jan 5, 2014 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 Commented Jan 5, 2014 at 3:08
• Actually, I believe you can just do if(a==i) Commented Jan 5, 2014 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.
– null
Commented Jan 4, 2014 at 19:23
• @xfix Nice, I also used several of your suggestions from the other answer. Thanks! Commented Jan 4, 2014 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. Commented Jan 4, 2014 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/… Commented Jan 4, 2014 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.
– null
Commented Jan 4, 2014 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

Stealing Ilmari's winning GolfScript answer...

@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... Commented Feb 9, 2017 at 7:33