Skip to main content

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:

  1. Create a function 'powerOf8(num)' that takes the input number 'num'.
  2. Use bitwise operations to check if the number satisfies the power of 8 condition.
  3. 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...
  4. 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).
  5. 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).

Last updated on by Kalkicode




Comment

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