Google Interview Question
Site Reliability EngineersTeam: Site reliabilty
Country: United States
Interview Type: Phone Interview
It obviously won't work for 0. You can raise 2 to the power of any integer, the answer will never be 0.
How about if number is 9 (3 ^ 2)
Binary of 9 : 1001
Binary of 8 : 1000
1001 & 1000 = 1000 (bin) which is 8
> How about if number is 9 (3 ^ 2)
The ret val will be false, as 9 is not a power of 2 (but a power of 3)
We are looking for numbers in the form 2^x (x: any unsigned int)
> This function won't work for num=0.
Why not?
0 == 00...00b
0-1 ==-1 == 11...11b
00..00b & 11..11b == 0 => return true
All integers that is power of 2, contains only one set bit in its bit-representation.
So idea is to check, only one bit is set or not in bit representation of a number.
Below is the code:
int isPowerOf2(int n){
return n && !(n&(n-1));
}
this function will return 1, if number n is power of 2.
Else it will return 0;
Except for bit operation, a naive idea:
#include <stdio.h>
#include <stdlib.h>
bool is_power_of_2(int n)
{
if (n == 0) return false;
if (n < 0) n = -n;
int q, m;
do {
q = n / 2;
m = n % 2;
n = q;
} while (m == 0 && q > 0);
return n == 0;
}
int main(int argc, char *argv[])
{
(void)argc;
int n = atoi(argv[1]);
if (is_power_of_2(n)) {
printf("%d is power of 2\n", n);
} else {
printf("%d is not power of 2\n", n);
}
return 0;
}
When using the logarithm on the equation num=2^x it is: log(num)=log(2)*x
After rewriting the equation it is: x=log(num)/log(2)
We want to know only num=2^x when x is an integer, so we just need to check for it.
public boolean is_power_of_2 (int num) {
double x=Math.log10(num)/Math.log10(2);
if (x==Math.floor(x)) {
return(true);
} else {
return(false);
}
}
When using the logarithm on the equation num=2^x it is: log(num)=log(2)*x
After rewriting the equation it is: x=log(num)/log(2)
We want to know only num=2^x when x is an integer, so we just need to check for it.
public boolean is_power_of_2 (int num) {
double x=Math.log10(num)/Math.log10(2);
if (x==Math.floor(x)) {
return(true);
} else {
return(false);
}
}
When using the logarithm on the equation num=2^x it is: log(num)=log(2)*x
After rewriting the equation it is: x=log(num)/log(2)
We want to know only num=2^x when x is an integer, so we just need to check for it.
public boolean is_power_of_2 (int num) {
double x=Math.log10(num)/Math.log10(2);
if (x==Math.floor(x)) {
return(true);
} else {
return(false);
}
}
Let's try this:
public class IsPowerOf2 {
public static void main(String[] args) {
System.out.println(isPowerOf2(16384));
System.out.println(isPowerOf2(16382));
}
private static boolean isPowerOf2(int i) {
if (i < 2) {
return false;
}
int a = 2;
while (a < i) {
a = 2 * a;
if (i == a) {
return true;
}
}
return false;
}
}
If a number is a power of 2, then the least significant bit isn't set, so...
bool isPowerTwo(int n)
{
return ( ( n & 1 ) == 0 );
}
//How to check if a number is power of 2
public class PowerOfTwo {
public static void main (String [] args) {
int num = 2;
int check = 2;
int powerOf = 0;
int two = 2;
while (true) {
if(num == check ) {
powerOf++;
System.out.println(" " + num + " is 2^" + powerOf);
break;
} else if(num < check) {
System.out.println("Num is not a power of 2");
break;
} else {
check = check * 2;
powerOf++;
}
}
}
}
//How to check if a number is power of 2
public class PowerOfTwo {
public static void main (String [] args) {
int num = 2;
int check = 2;
int powerOf = 0;
int two = 2;
while (true) {
if(num == check ) {
powerOf++;
System.out.println(" " + num + " is 2^" + powerOf);
break;
} else if(num < check) {
System.out.println("Num is not a power of 2");
break;
} else {
check = check * 2;
powerOf++;
}
}
}
}
e.g 4 in binary is 100
- sahaj September 27, 20123 in binary is 011
4&3 000