After writing the power of 4 into binary form, it is easy to find that there is a feature:There is only one 1 in the binary system (1 is in an odd position), and 1 is followed by an even number of 0s; therefore the problem can be translated into determining whether 1 is followed by an even number of 0s.
The binary numbers of integer powers of 4 are (4)100, (16)10000, (64)1000000...
In addition, the power of 4 4^n can also be written as 2^(2*n), that is, it can also be written as a power of 2. Of course, the condition of power of 2 is satisfied, that is, num & num-1==0.
Idea: First, use the condition num & num-1==0 to determine whether it is a power of 2. If it is not satisfied, it is not. If it is satisfied, use the condition num & 0x55555555 to judge. If it is true, then the integer is power of 4, otherwise it is not.
The code that is implemented using recursion is as follows:
#include ""
#include ""
bool fn(unsigned int x) //Judge whether x is the power of 4
{
if ( x & (x - 1) ) //Judge whether x is a power of 2
return false;
return x & 0x55555555; //Judge whether 1 is in an odd position
}
int log4(int value) //Recursively determines how many times a number is 4
{
if (value == 1)
return 0;
else
{
value>>=1; //Transfer to the right
return 1+log4(value>>1); //Transfer to the right
}
}
int main(void)
{
int num;
printf("Please enter an integer:");
scanf("%d",&num);
if(fn(num)) //Use and operation to determine whether a number is a power of 2
printf("%d is 4 to the power of %d!\n",num,log4(num));
else
printf("%d is not the power of 4!\n",num);
system("pause");
return 0;
}
The code that is implemented using non-recursion is as follows:
#include ""
#include ""
bool fn(unsigned int x) //Judge whether x is the power of 4
{
if ( x & (x - 1) ) //Judge whether x is a power of 2
return false;
return x & 0x55555555; //Judge whether 1 is in an odd position
}
int log4(int value) //Not recursively determines how much power a number is 4
{
int x=0;
while(value>1)
{
value>>=1; //Transfer to the right
value>>=1;
x++;
}
return x;
}
int main(void)
{
int num;
printf("Please enter an integer:");
scanf("%d",&num);
if(fn(num)) //Use and operation to determine whether a number is a power of 2
printf("%d is 4 to the power of %d!\n",num,log4(num));
else
printf("%d is not the power of 4!\n",num);
system("pause");
return 0;
}
The binary numbers of integer powers of 4 are (4)100, (16)10000, (64)1000000...
In addition, the power of 4 4^n can also be written as 2^(2*n), that is, it can also be written as a power of 2. Of course, the condition of power of 2 is satisfied, that is, num & num-1==0.
Idea: First, use the condition num & num-1==0 to determine whether it is a power of 2. If it is not satisfied, it is not. If it is satisfied, use the condition num & 0x55555555 to judge. If it is true, then the integer is power of 4, otherwise it is not.
The code that is implemented using recursion is as follows:
Copy the codeThe code is as follows:
#include ""
#include ""
bool fn(unsigned int x) //Judge whether x is the power of 4
{
if ( x & (x - 1) ) //Judge whether x is a power of 2
return false;
return x & 0x55555555; //Judge whether 1 is in an odd position
}
int log4(int value) //Recursively determines how many times a number is 4
{
if (value == 1)
return 0;
else
{
value>>=1; //Transfer to the right
return 1+log4(value>>1); //Transfer to the right
}
}
int main(void)
{
int num;
printf("Please enter an integer:");
scanf("%d",&num);
if(fn(num)) //Use and operation to determine whether a number is a power of 2
printf("%d is 4 to the power of %d!\n",num,log4(num));
else
printf("%d is not the power of 4!\n",num);
system("pause");
return 0;
}
The code that is implemented using non-recursion is as follows:
Copy the codeThe code is as follows:
#include ""
#include ""
bool fn(unsigned int x) //Judge whether x is the power of 4
{
if ( x & (x - 1) ) //Judge whether x is a power of 2
return false;
return x & 0x55555555; //Judge whether 1 is in an odd position
}
int log4(int value) //Not recursively determines how much power a number is 4
{
int x=0;
while(value>1)
{
value>>=1; //Transfer to the right
value>>=1;
x++;
}
return x;
}
int main(void)
{
int num;
printf("Please enter an integer:");
scanf("%d",&num);
if(fn(num)) //Use and operation to determine whether a number is a power of 2
printf("%d is 4 to the power of %d!\n",num,log4(num));
else
printf("%d is not the power of 4!\n",num);
system("pause");
return 0;
}