Check if a number is power of 8 or not
In this article, we will explore how to determine whether a given number is a power of 8 or not. A number is said to be a power of 8 if it can be expressed as 8^k, where k is a positive integer (k = 1, 2, 3, ...). We will provide an efficient algorithm to check this condition using bitwise operations and explain the rationale behind it.
Problem Statement
Given an integer 'num', the task is to determine whether 'num' is a power of 8 or not. If 'num' is a power of 8, the program should output that it is, and if it is not, it should indicate so.
Example
Let's take an example to understand the problem better.
- For 'num' = 8, it is a power of 8 as 8^1 = 8.
- For 'num' = 64, it is a power of 8 as 8^2 = 64.
- For 'num' = 128, it is not a power of 8.
- For 'num' = 512, it is a power of 8 as 8^3 = 512.
- For 'num' = 32, it is not a power of 8.
- For 'num' = 4096, it is a power of 8 as 8^4 = 4096.
Pseudocode and Algorithm
// Function to check if a number is a power of 8
function powerOf8(num):
// Check if 'num' is non-zero and has only one bit set
if num is 0 or (num & (num - 1)) is not 0:
return false
// Check if any bit at positions not multiple of 3 is set
if num & 3067833782 is not 0:
return false
return true
The algorithm to determine whether a number is a power of 8 or not will be based on the following steps:
- Create a function 'powerOf8(num)' that takes the input number 'num'.
- Use bitwise operations to check if the number satisfies the power of 8 condition.
- In binary representation of powers of 8 (8^k), the only active bits will be at positions multiple of 3
(counting from the right, starting with position 0). For example:
- 8^0 = 1 (binary: 0001)
- 8^1 = 8 (binary: 1000)
- 8^2 = 64 (binary: 1000000)
- 8^3 = 512 (binary: 1000000000)
- And so on...
- To check if 'num' is a power of 8, we can apply the following bitwise operation:
(num && !(num & 3067833782) && !(num & (num - 1))) == 1
- The first part
num &&
ensures 'num' is non-zero, as 0 is not a power of 8. - The second part
!(num & 3067833782)
checks if any bit at positions not multiple of 3 is set. If any such bit is set, 'num' is not a power of 8. - The third part
!(num & (num - 1))
checks if 'num' has only one bit set. This condition ensures 'num' is a power of 2 (which is a necessary condition for it to be a power of 8).
- The first part
- If the above conditions are met, then 'num' is a power of 8, and the function should print this information.
Code Solution
Here given code implementation process.
// C Program
// Check if a number is power of 8 or not
#include <stdio.h>
// Determine whether given number is power of 8 or not
// 8¹,8²,8³,8⁴,8⁵,8⁶,8⁷,8⁸,8⁹ ...
void powerof8(int num)
{
// 3067833782 (32 bit) = 10110110110110110110110110110110
// position % 3 bit are inactive
if ((num && !(num & 3067833782) && !(num & (num - 1))) == 1)
{
printf(" %d is power of 8\n", num);
}
else
{
printf(" %d is not power of 8\n", num);
}
}
int main(int argc, char
const *argv[])
{
// Test Case
powerof8(8);
powerof8(64);
powerof8(128);
powerof8(512);
powerof8(32);
powerof8(4096);
return 0;
}
Output
8 is power of 8
64 is power of 8
128 is not power of 8
512 is power of 8
32 is not power of 8
4096 is power of 8
/*
Java Program
Check if a number is power of 8 or not
*/
public class Power
{
// Determine whether given number is power of 8 or not
// 8¹,8²,8³,8⁴,8⁵,8⁶,8⁷,8⁸,8⁹ ...
public void powerof8(int num)
{
// 3067833782 (32 bit) = 10110110110110110110110110110110
// position % 3 bit are inactive
if ( num != 0 && ((num & 3067833782L) == 0) && ((num & (num -1)) == 0) )
{
System.out.print(" " + num + " is power of 8\n");
}
else
{
System.out.print(" " + num + " is not power of 8\n");
}
}
public static void main(String[] args)
{
Power task = new Power();
// Test Case
task.powerof8(8);
task.powerof8(64);
task.powerof8(128);
task.powerof8(512);
task.powerof8(32);
task.powerof8(4096);
}
}
Output
8 is power of 8
64 is power of 8
128 is not power of 8
512 is power of 8
32 is not power of 8
4096 is power of 8
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Check if a number is power of 8 or not
*/
class Power
{
public:
// Determine whether given number is power of 8 or not
// 8¹,8²,8³,8⁴,8⁵,8⁶,8⁷,8⁸,8⁹ ...
void powerof8(int num)
{
// 3067833782 (32 bit) = 10110110110110110110110110110110
// position % 3 bit are inactive
if (num != 0 && ((num &3067833782) == 0) && ((num &(num - 1)) == 0))
{
cout << " " << num << " is power of 8\n";
}
else
{
cout << " " << num << " is not power of 8\n";
}
}
};
int main()
{
Power task = Power();
// Test Case
task.powerof8(8);
task.powerof8(64);
task.powerof8(128);
task.powerof8(512);
task.powerof8(32);
task.powerof8(4096);
return 0;
}
Output
8 is power of 8
64 is power of 8
128 is not power of 8
512 is power of 8
32 is not power of 8
4096 is power of 8
// Include namespace system
using System;
/*
C# Program
Check if a number is power of 8 or not
*/
public class Power
{
// Determine whether given number is power of 8 or not
// 8¹,8²,8³,8⁴,8⁵,8⁶,8⁷,8⁸,8⁹ ...
public void powerof8(int num)
{
// 3067833782 (32 bit) = 10110110110110110110110110110110
// position % 3 bit are inactive
if (num != 0 && ((num & 3067833782) == 0) && ((num & (num - 1)) == 0))
{
Console.Write(" " + num + " is power of 8\n");
}
else
{
Console.Write(" " + num + " is not power of 8\n");
}
}
public static void Main(String[] args)
{
Power task = new Power();
// Test Case
task.powerof8(8);
task.powerof8(64);
task.powerof8(128);
task.powerof8(512);
task.powerof8(32);
task.powerof8(4096);
}
}
Output
8 is power of 8
64 is power of 8
128 is not power of 8
512 is power of 8
32 is not power of 8
4096 is power of 8
<?php
/*
Php Program
Check if a number is power of 8 or not
*/
class Power
{
// Determine whether given number is power of 8 or not
// 8¹,8²,8³,8⁴,8⁵,8⁶,8⁷,8⁸,8⁹ ...
public function powerof8($num)
{
// 3067833782 (32 bit) = 10110110110110110110110110110110
// position % 3 bit are inactive
if ($num != 0 && (($num & 3067833782) == 0) && (($num & ($num - 1)) == 0))
{
echo " ". $num ." is power of 8\n";
}
else
{
echo " ". $num ." is not power of 8\n";
}
}
}
function main()
{
$task = new Power();
// Test Case
$task->powerof8(8);
$task->powerof8(64);
$task->powerof8(128);
$task->powerof8(512);
$task->powerof8(32);
$task->powerof8(4096);
}
main();
Output
8 is power of 8
64 is power of 8
128 is not power of 8
512 is power of 8
32 is not power of 8
4096 is power of 8
/*
Node Js Program
Check if a number is power of 8 or not
*/
class Power
{
// Determine whether given number is power of 8 or not
// 8¹,8²,8³,8⁴,8⁵,8⁶,8⁷,8⁸,8⁹ ...
powerof8(num)
{
// 3067833782 (32 bit) = 10110110110110110110110110110110
// position % 3 bit are inactive
if (num != 0 && ((num & 3067833782) == 0) && ((num & (num - 1)) == 0))
{
process.stdout.write(" " + num + " is power of 8\n");
}
else
{
process.stdout.write(" " + num + " is not power of 8\n");
}
}
}
function main()
{
var task = new Power();
// Test Case
task.powerof8(8);
task.powerof8(64);
task.powerof8(128);
task.powerof8(512);
task.powerof8(32);
task.powerof8(4096);
}
main();
Output
8 is power of 8
64 is power of 8
128 is not power of 8
512 is power of 8
32 is not power of 8
4096 is power of 8
# Python 3 Program
# Check if a number is power of 8 or not
class Power :
# Determine whether given number is power of 8 or not
# 8¹,8²,8³,8⁴,8⁵,8⁶,8⁷,8⁸,8⁹ ...
def powerof8(self, num) :
# 3067833782 (32 bit) = 10110110110110110110110110110110
# position % 3 bit are inactive
if (num != 0 and((num & 3067833782) == 0) and((num & (num - 1)) == 0)) :
print("", num ,"is power of 8")
else :
print("", num ,"is not power of 8")
def main() :
task = Power()
# Test Case
task.powerof8(8)
task.powerof8(64)
task.powerof8(128)
task.powerof8(512)
task.powerof8(32)
task.powerof8(4096)
if __name__ == "__main__": main()
Output
8 is power of 8
64 is power of 8
128 is not power of 8
512 is power of 8
32 is not power of 8
4096 is power of 8
# Ruby Program
# Check if a number is power of 8 or not
class Power
# Determine whether given number is power of 8 or not
# 8¹,8²,8³,8⁴,8⁵,8⁶,8⁷,8⁸,8⁹ ...
def powerof8(num)
# 3067833782 (32 bit) = 10110110110110110110110110110110
# position % 3 bit are inactive
if (num != 0 && ((num & 3067833782) == 0) && ((num & (num - 1)) == 0))
print(" ", num ," is power of 8\n")
else
print(" ", num ," is not power of 8\n")
end
end
end
def main()
task = Power.new()
# Test Case
task.powerof8(8)
task.powerof8(64)
task.powerof8(128)
task.powerof8(512)
task.powerof8(32)
task.powerof8(4096)
end
main()
Output
8 is power of 8
64 is power of 8
128 is not power of 8
512 is power of 8
32 is not power of 8
4096 is power of 8
/*
Scala Program
Check if a number is power of 8 or not
*/
class Power
{
// Determine whether given number is power of 8 or not
// 8¹,8²,8³,8⁴,8⁵,8⁶,8⁷,8⁸,8⁹ ...
def powerof8(num: Int): Unit = {
// 3067833782 (32 bit) = 10110110110110110110110110110110
// position % 3 bit are inactive
if (num != 0 && ((num & 3067833782L) == 0) && ((num & (num - 1)) == 0))
{
print(" " + num + " is power of 8\n");
}
else
{
print(" " + num + " is not power of 8\n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Power = new Power();
// Test Case
task.powerof8(8);
task.powerof8(64);
task.powerof8(128);
task.powerof8(512);
task.powerof8(32);
task.powerof8(4096);
}
}
Output
8 is power of 8
64 is power of 8
128 is not power of 8
512 is power of 8
32 is not power of 8
4096 is power of 8
/*
Swift 4 Program
Check if a number is power of 8 or not
*/
class Power
{
// Determine whether given number is power of 8 or not
// 8¹,8²,8³,8⁴,8⁵,8⁶,8⁷,8⁸,8⁹ ...
func powerof8(_ num: Int)
{
// 3067833782 (32 bit) = 10110110110110110110110110110110
// position % 3 bit are inactive
if (num != 0 && ((num & 3067833782) == 0) && ((num & (num - 1)) == 0))
{
print(" ", num ," is power of 8");
}
else
{
print(" ", num ," is not power of 8");
}
}
}
func main()
{
let task: Power = Power();
// Test Case
task.powerof8(8);
task.powerof8(64);
task.powerof8(128);
task.powerof8(512);
task.powerof8(32);
task.powerof8(4096);
}
main();
Output
8 is power of 8
64 is power of 8
128 is not power of 8
512 is power of 8
32 is not power of 8
4096 is power of 8
/*
Kotlin Program
Check if a number is power of 8 or not
*/
class Power
{
// Determine whether given number is power of 8 or not
// 8¹,8²,8³,8⁴,8⁵,8⁶,8⁷,8⁸,8⁹ ...
fun powerof8(num: Int): Unit
{
// 3067833782 (32 bit) = 10110110110110110110110110110110
// position % 3 bit are inactive
if (num != 0 && ((num.toLong() and 3067833782L).toInt() == 0) && ((num and(num - 1)) == 0))
{
print(" " + num + " is power of 8\n");
}
else
{
print(" " + num + " is not power of 8\n");
}
}
}
fun main(args: Array < String > ): Unit
{
var task: Power = Power();
// Test Case
task.powerof8(8);
task.powerof8(64);
task.powerof8(128);
task.powerof8(512);
task.powerof8(32);
task.powerof8(4096);
}
Output
8 is power of 8
64 is power of 8
128 is not power of 8
512 is power of 8
32 is not power of 8
4096 is power of 8
// Rust Program
// Check if a number is power of 8 or not
fn main()
{
// Test Case
powerof8(8);
powerof8(64);
powerof8(128);
powerof8(512);
powerof8(32);
powerof8(4096);
}
fn powerof8(num: i64)
{
// 3067833782 (32 bit) = 10110110110110110110110110110110
// position % 3 bit are inactive
if num != 0 && ((num & 3067833782) == 0) && ((num & (num -1)) == 0)
{
print!(" {} is power of 8\n", num);
}
else
{
print!(" {} is not power of 8\n", num);
}
}
Output
8 is power of 8
64 is power of 8
128 is not power of 8
512 is power of 8
32 is not power of 8
4096 is power of 8
Time Complexity
The time complexity of the algorithm is O(1) because we perform a fixed number of bitwise operations, regardless of the input size.
Resultant Output Explanation
The provided C code contains the implementation of the above algorithm. The 'powerof8' function is called for different test cases, and the output indicates whether each number is a power of 8 or not.
Output
- 8 is a power of 8: 8^1 = 8
- 64 is a power of 8: 8^2 = 64
- 128 is not a power of 8.
- 512 is a power of 8: 8^3 = 512
- 32 is not a power of 8.
- 4096 is a power of 8: 8^4 = 4096
The program correctly identifies which numbers are powers of 8 and which are not, based on the algorithm explained earlier. The output demonstrates that the code is functioning as intended.
In conclusion, the code provides an efficient solution to determine if a number is a power of 8 using bitwise operations. It is a concise and effective way to solve the problem with a time complexity of O(1).
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment