CareerCup

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

int power_of_two(int x) {
if (x % 2)
return null;

return power_of_two(x/2);
}

int powerOfTwo(int n) {
int count = 0;
while(n) {
n = n&(n-1);
count++;
}
if (count <= 1)
return 1;
else
return 0;
}

int powerOfTwo(int n) {
//If we have have more than 1 bit set return false
if ( n&(n-1) )
return 0;
return 1;
}

int powerOfTwo(int n) {
//If we have have more than 1 bit set return false
return !(n & (n-1) );
}

could somebody explain why only check n&(n-1)is OK?
Thanks.

coz when you do (n & (n-1)), the resulting binary number will have number of 1 bits exactly one less than original number. Try it your self by playing with some numbers. So, If (n & (n-1)) is zero, it means that n has only one 1-bit. Any number that has exactly one 1-bit, is power of two.

Some more bit manipulation

int n;
take input in n;

n <<= 31;
n >>= 31;

if(n&1)
print odd;
else print even;

n&(n-1) logic only works if n > 1.

How about checking the last bit?
(!(n & 1)) ==> Even
else Odd.

A number would be a power of two if there is exactly one bit that is equal to 1 in its bit pattern (even 1 is a power of 2. 2 raised to the power zero is 1). Now we could use the method that we used to count the number of bits that are 1 in a given number and check if it is equal to 1. However that approach needs many steps and hence won’t suffice here.

In a number which is an exact power of 2 only 1 bit is set and all others are zero. Let the position of this 1 bit be MSB. Mathematics rules for binary numbers tells us that if we subtract 1 from this number then the number that we would get would have all its bit starting from the bit position MSB+1 set to 1. For example if the given number num is 8(00001000) then num-1 would be 7 (00000111). Now we notice that these two bit patterns dont have a 1 in the same bit position. Further observation suggests that if we bitwise and (&) both these numbers we would get zero.

bool isPowerOf2(int num)
{
return ((num>0) && (num & (num-1))==0);
}

For a number to be a power of 2, only one of the bits has to be set and others zero. In the below code, you test the last bit if zero, you rotate the bits till you find 1.

bool testpowerof2(int i){
	if (i<=0)
		return false;
	while(i !=0){
		if (i & 1)
			break;
		i = i>>1;
	}
	if (i == 1)
		return true;
	return false;
}

{
if(!(num & (num - 1)) && num) { // Power of 2! }
}

OR

{
if(((~i+1)&i)==i) { //Power of 2! }
}

Method 1:

((x+(x-1))==((x|(x-1))))?printf("\nIt is"):printf("\nIt is Not");

Method 2:

((x&(x-1))==0?printf("\nIt is powers of 2"):printf("\nIt is not a power of 2"));

Method 3:

((x^(x-1))==((x*2)-1)?printf("\t\nIt is powers of 2"):printf("\nIt is not a power of 2"));

public static boolean isPowerOf2(int a){
String binaryNumber = Integer.toBinaryString(a);
return (binaryNumber.length()-binaryNumber.replace("1","").length() ==1);
}

public static boolean isPowerOf2(int a){
		String binaryNumber = Integer.toBinaryString(a);
		return (binaryNumber.length()-binaryNumber.replace("1","").length() ==1);
	}

One of the easiest algorithm for the above problem statement will take the & of the bitwise of the given number and (n - 1) which will result in 0 when the number n is the power of 2 else will result in 1 and then their ! will result in 1 and 0 respectively and && with the number will result in true value if no is power of two else will re turn false:

Implementation:

#include<bits/stdc++.h>
using namespace std;
bool findpoweroftwo(int x){
return x && (!(x & (x - 1)));
}
int main(){
if(findpoweroftwo(5))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}

if (number > 0 && !(number&(number-1)))
                printf("power of 2\n");
        else
                printf("not power of 2\n");