Can You find whether a given number is a power of 2?
If Yes, then how you do it?
Common Approach(Ineffecient):
while(num%2 != 0)
{
num/=2;
if(num==2)
{
//Your Number is power of 2
return "YES";
}
}
return "NO";
But For a number 2563254127898, is your code efficient?
No.
Right Approach:
Here is a way to write effecient code in 1 statement:
if(num>1 && num&(num-1)) == 0))
{
//Your number is power of 2
}
Why? And how does the code work?
Check the binary series:
1 : 0000 0001
2 : 0000 0010
3 : 0000 0011
4 : 0000 0100
5 : 0000 0101
6 : 0000 0110
7 : 0000 0111
8 : 0000 1000
If You see here, the numbers which are power of 2 will have only single "1" in binary format. This "1" goes on shifting to left as power increases. A number just prior to such "2-powered" number will have a "0"(zero) above that "1". In this case only, the bitwise AND operation between 2-powered number and just prior number results in "0"(zero).
Example 1:
0000 0111(num: 7)
& 0000 1000(num: 8)
-----------------------------------
0000 0000
-----------------------------------
Example 2:
0000 0011(num: 3)
& 0000 0100(num: 4)
-----------------------------------
0000 0000
-----------------------------------
Happy learning...