CareerCup

"Find if a num is a power of 2 as fast as possible"

{
if((num & (num-1))==0)
num is a power of 2
else
num is nota a power of 2
}

@Phenom

the if condition should be:

if(num && (num & (num-1))==0) // to handle the case where input is 0

it will fail when num = 1

if(a&(a-1)==0)
power of 2...

a xor a-1 is not 1.. rather, it is 1111... :)
This implementation leads to more conditional checking.. as the result would be 000..111....

Karthik's answer is incorrect as it will mark 0 as a power of two
So the correct version is

unsigned int v; // we want to see if v is a power of 2
bool f;         // the result goes here 

f = !(v & (v - 1)) && v;

What does it mean power of 2? Does it mean its square root have to be an integer number?

Woudl'nt any number which is a power of 2 have just a single 1 in its bit representation? How about we count the no. of bits set?

<i>How about we count the no. of bits set?</i>

optimal code: (Knuth's algo)

int cnt = 0;

while ( n &= (n-1) && ++cnt );

cout << cnt ;

shift left most bit out, see if it's zero?

i & (--i) != i

first answer (num & (num-1))==0) correct
i & (--i) != i fails.

Guys, why are we ANDing the number ( num ) with ( num -1 ) ? Although it would lead to a correct solution, instead we can check whether the binary representation of the number contains "1" at the MSB and zeroes at all other places

Mandar, you're so fucking dumb. a 1 at the doesn't hold for any powers of two other than 1. what about 4, is there a 0 in MSB?

What you need to check is the following as one of the posts above mentioned.

if(num != 0 && (num & (num - 1) == 0)
  return true;
else
  return false;

May be you need to get fucking conventions and terminology right. Also, learn some English while you are at it. As far conventions go the MSB is the 32nd bit on 32 bit machine, you fag, i.e. highest order bit.

May you should wiki "Most significant bit".

Say, x = number; and power is n

2^n = x <<<we have to find "n" in this.
Take log on both side.
n = log(x)/log(2);

if n is an integer, then x can be expressed as 2^n, otherwise not.

You can check for x=0 explicitly.

// Check no of bits set because in a no which is a power of 2 only the MSB is set.

void check ( int no ) {
int temp = 0x00000001, cnt ;
if ( no ) {
for ( i = 0; i < 32; i++ ) {
temp = temp << i;
if ( temp & no != 0 )
cnt++ ;
}
}
if( cnt == 1 )
printf (" No. is a multiple \n");
else
printf("not a multiple\n");
}

<pre lang="java" line="1" title="CodeMonkey42535" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
java.io.BufferedReader r = new java.io.BufferedReader (new java.io.InputStreamReader (System.in));
String s;
while (!(s=r.readLine()).startsWith("42")) System.out.println(s);
}
}

</pre><pre title="CodeMonkey42535" input="yes">1
2
10
42
11

</pre>

bool TestPowerOfTwo(int n){
if((n&(n-1))==0)return 1;
else return 0;
}

you guys are good. this works perfectly

What a wonderful question!
Bad answers

If a number is 2^n then it's binary form only have one 1
others are all zero!

static boolean isPower2(int number){
		if(number == number - (number & (number - 1)) && number != 1){
			return true;
		}
		else return false;
	}

for both negative and positive integers


static boolean isPower2(int number){
		number = (number < 0)? (0 - number) : number;
		if(number == number - (number & (number - 1)) && number != 1){
			return true;
		}
		else return false;
	}

public static boolean isPowerOfTwo(int num) {
    if (num == 2 || num == 1) return true;
    int i = 2;
    while (i < num) {
      if (i * 2 == num) return true;
      i = i * 2;
    }
    return false;
  }

As has been stated numerous times already, simply &ing the number and the number minus one will get you the correct answer (as long as you also check for the zero case).

The following code also works. It is less elegant, but it more exhaustively goes through the byte without being too cumbersome.

int count = 0;
  for(int i = 0; i<sizeof(aInt); i++){
    
    count+=aInt & 1;
    if(count > 1)
      return false;
    
    aInt>>=1;
  }
  printf("%d\n", count);
  
  return true;

bool isPowOf2(int n)
{
	if(n && !(n & (n-1)))
		return 1;
	return 0;

}

bool is_power_of_2(int n)
{
  if (n < 0) n = -n;
  return (n & -n) == n; // extract the rightmost bit 1
}

for(int v=0;v<2050;v++)
if(Integer.toBinaryString(v-1).matches("1+"))
{
System.out.println(Integer.toBinaryString(v)+" "+v);
}

{{
for(int v=0;v<2050;v++)
if(Integer.toBinaryString(v-1).matches("1+"))
{
System.out.println(Integer.toBinaryString(v)+" "+v);
}
}}

#include <iostream>
#include <math.h>
using namespace std;




int main()
{

    int n;

    cin >> n;

    double resF= log10(n)/log10(2);
    int resI = log10(n)/log10(2);

    double resF2 = (double) resI;

    if (resF == resF2)
    {
        cout << "n is of power 2" << endl;
    }
    else
    {
        cout << "n is NOT of power 2" << endl;
    }

    return 0;
}

#include <iostream>
#include <math.h>
using namespace std;




int main()
{

    int n;

    cin >> n;

    double resF= log10(n)/log10(2);
    int resI = log10(n)/log10(2);

    double resF2 = (double) resI;

    if (resF == resF2)
    {
        cout << "n is of power 2" << endl;
    }
    else
    {
        cout << "n is NOT of power 2" << endl;
    }

    return 0;
}

{{
#include <iostream>
#include <math.h>
using namespace std;

int main()
{

int n;

cin >> n;

double resF= log10(n)/log10(2);
int resI = log10(n)/log10(2);

double resF2 = (double) resI;

if (resF == resF2)
{
cout << "n is of power 2" << endl;
}
else
{
cout << "n is NOT of power 2" << endl;
}

return 0;
}
}}

#include <iostream>
#include <math.h>
using namespace std;

int main()
{

    int n;

    cin >> n;

    double resF= log10(n)/log10(2);
    int resI = log10(n)/log10(2);

    double resF2 = (double) resI;

    if (resF == resF2)
    {
        cout << "n is of power 2" << endl;
    }
    else
    {
        cout << "n is NOT of power 2" << endl;
    }

    return 0;
}

double resF= log10(n)/log10(2);
    int resI = log10(n)/log10(2);

    double resF2 = (double) resI;

    if (resF == resF2)
    {
        cout << "n is of power 2" << endl;
    }

double resF= log10(n)/log10(2);
int resI = log10(n)/log10(2);

double resF2 = (double) resI;

if (resF == resF2)
{
cout << "n is of power 2" << endl;
}

One of the most efficient method to check whether a given number is a power of two or not we will check for the & of the number and the number before itself and then for fulfilling the condition of 0 we have to check for && operation.

Implementation:

#include<bits/stdc++.h>
using namepace std;
bool returnpower(int n){
return n && (!(n & (n - 1)))

}