Posted on by Kalkicode
Code Bit Logic

Highest power of two that divides a given number

The given problem is to find the highest power of two that divides a given number. In other words, we need to find the largest power of 2 that is a divisor of the input number.

Problem Statement with Example

Let's understand the problem with an example. Consider the number 40. We need to find the highest power of 2 that divides 40. The divisors of 40 are 1, 2, 4, 5, 8, 10, 20, and 40. The highest power of 2 that divides 40 is 8 (2^3). So, the answer for 40 is 8.

Pseudocode

function power2Divisible(num):
    // Step 1: Find the rightmost set bit
    rightmost_set_bit = num & (~(num - 1))
    
    // Step 2: Calculate the highest power of 2 that divides the number
    highest_power = log2(rightmost_set_bit)

    // Step 3: Print the result
    print("Number:", num)
    print("Power:", highest_power)
    
end function

Note: In the above pseudocode, the log2() function is used to calculate the logarithm base 2. However, it's important to mention that most programming languages do not have a built-in log2 function. In practice, you can either implement your own log2 function using logarithmic properties or use other methods to find the highest power of 2.

Algorithm

The algorithm uses bitwise operations to find the highest power of 2 that divides the given number.

  1. Start the function power2Divisible(num).
  2. Calculate the value of n as (num & (~(num - 1))).
    • The expression (num - 1) will have all the bits after the rightmost set bit in num set to 1, and all the bits before the rightmost set bit unchanged.
    • When we take the bitwise complement of (num - 1), all the bits before the rightmost set bit will become 0, and the rightmost set bit will become 1.
    • When we perform the bitwise AND operation with num, we get the rightmost set bit of num.
  3. Print the calculated value n.

Code Solution

Here given code implementation process.

// C program 
// Highest power of two that divides a given number
#include <stdio.h>

// Find higher power 2 number which is divisible by given number
void power2Divisible(int num)
{
	// Find highest divide number
	int n = (num & (~(num - 1)));
	// Display calculated result
	printf("\n Number : %d", num);
	printf("\n Power  : %d\n", n);
}
int main(int argc, char
	const *argv[])
{
	// Test Cases
	power2Divisible(10);
	power2Divisible(40);
	power2Divisible(64);
	power2Divisible(43);
	return 0;
}

Output

 Number : 10
 Power  : 2

 Number : 40
 Power  : 8

 Number : 64
 Power  : 64

 Number : 43
 Power  : 1
/*
  Java program
  Highest power of two that divides a given number
*/
public class Power
{
	// Find higher power 2 number which is divisible by given number
	public void power2Divisible(int num)
	{
		// Find highest divide number
		int n = (num & (~(num - 1)));
		// Display calculated result
		System.out.print("\n Number : " + num);
		System.out.print("\n Power  : " + n + "\n");
	}
	public static void main(String[] args)
	{
		Power task = new Power();
		// Test Cases
		task.power2Divisible(10);
		task.power2Divisible(40);
		task.power2Divisible(64);
		task.power2Divisible(43);
	}
}

Output

 Number : 10
 Power  : 2

 Number : 40
 Power  : 8

 Number : 64
 Power  : 64

 Number : 43
 Power  : 1
// Include header file
#include <iostream>

using namespace std;
/*
  C++ program
  Highest power of two that divides a given number
*/
class Power
{
	public:
		// Find higher power 2 number which is divisible by given number
		void power2Divisible(int num)
		{
			// Find highest divide number
			int n = (num &(~(num - 1)));
			// Display calculated result
			cout << "\n Number : " << num;
			cout << "\n Power  : " << n << "\n";
		}
};
int main()
{
	Power task = Power();
	// Test Cases
	task.power2Divisible(10);
	task.power2Divisible(40);
	task.power2Divisible(64);
	task.power2Divisible(43);
	return 0;
}

Output

 Number : 10
 Power  : 2

 Number : 40
 Power  : 8

 Number : 64
 Power  : 64

 Number : 43
 Power  : 1
// Include namespace system
using System;
/*
  C# program
  Highest power of two that divides a given number
*/
public class Power
{
	// Find higher power 2 number which is divisible by given number
	public void power2Divisible(int num)
	{
		// Find highest divide number
		int n = (num & (~(num - 1)));
		// Display calculated result
		Console.Write("\n Number : " + num);
		Console.Write("\n Power  : " + n + "\n");
	}
	public static void Main(String[] args)
	{
		Power task = new Power();
		// Test Cases
		task.power2Divisible(10);
		task.power2Divisible(40);
		task.power2Divisible(64);
		task.power2Divisible(43);
	}
}

Output

 Number : 10
 Power  : 2

 Number : 40
 Power  : 8

 Number : 64
 Power  : 64

 Number : 43
 Power  : 1
<?php
/*
  Php program
  Highest power of two that divides a given number
*/
class Power
{
	// Find higher power 2 number which is divisible by given number
	public	function power2Divisible($num)
	{
		// Find highest divide number
		$n = ($num & (~($num - 1)));
		// Display calculated result
		echo "\n Number : ". $num;
		echo "\n Power  : ". $n ."\n";
	}
}

function main()
{
	$task = new Power();
	// Test Cases
	$task->power2Divisible(10);
	$task->power2Divisible(40);
	$task->power2Divisible(64);
	$task->power2Divisible(43);
}
main();

Output

 Number : 10
 Power  : 2

 Number : 40
 Power  : 8

 Number : 64
 Power  : 64

 Number : 43
 Power  : 1
/*
  Node Js program
  Highest power of two that divides a given number
*/
class Power
{
	// Find higher power 2 number which is divisible by given number
	power2Divisible(num)
	{
		// Find highest divide number
		var n = (num & (~(num - 1)));
		// Display calculated result
		process.stdout.write("\n Number : " + num);
		process.stdout.write("\n Power  : " + n + "\n");
	}
}

function main()
{
	var task = new Power();
	// Test Cases
	task.power2Divisible(10);
	task.power2Divisible(40);
	task.power2Divisible(64);
	task.power2Divisible(43);
}
main();

Output

 Number : 10
 Power  : 2

 Number : 40
 Power  : 8

 Number : 64
 Power  : 64

 Number : 43
 Power  : 1
#   Python 3 program
#   Highest power of two that divides a given number

class Power :
	#  Find higher power 2 number which is divisible by given number
	def power2Divisible(self, num) :
		#  Find highest divide number
		n = (num & (~(num - 1)))
		#  Display calculated result
		print("\n Number : ", num, end = "")
		print("\n Power  : ", n )
	

def main() :
	task = Power()
	#  Test Cases
	task.power2Divisible(10)
	task.power2Divisible(40)
	task.power2Divisible(64)
	task.power2Divisible(43)

if __name__ == "__main__": main()

Output

 Number :  10
 Power  :  2

 Number :  40
 Power  :  8

 Number :  64
 Power  :  64

 Number :  43
 Power  :  1
#   Ruby program
#   Highest power of two that divides a given number

class Power 
	#  Find higher power 2 number which is divisible by given number
	def power2Divisible(num) 
		#  Find highest divide number
		n = (num & (~(num - 1)))
		#  Display calculated result
		print("\n Number : ", num)
		print("\n Power  : ", n ,"\n")
	end

end

def main() 
	task = Power.new()
	#  Test Cases
	task.power2Divisible(10)
	task.power2Divisible(40)
	task.power2Divisible(64)
	task.power2Divisible(43)
end

main()

Output

 Number : 10
 Power  : 2

 Number : 40
 Power  : 8

 Number : 64
 Power  : 64

 Number : 43
 Power  : 1

/*
  Scala program
  Highest power of two that divides a given number
*/
class Power
{
	// Find higher power 2 number which is divisible by given number
	def power2Divisible(num: Int): Unit = {
		// Find highest divide number
		var n: Int = (num & (~(num - 1)));
		// Display calculated result
		print("\n Number : " + num);
		print("\n Power  : " + n + "\n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Power = new Power();
		// Test Cases
		task.power2Divisible(10);
		task.power2Divisible(40);
		task.power2Divisible(64);
		task.power2Divisible(43);
	}
}

Output

 Number : 10
 Power  : 2

 Number : 40
 Power  : 8

 Number : 64
 Power  : 64

 Number : 43
 Power  : 1
/*
  Swift 4 program
  Highest power of two that divides a given number
*/
class Power
{
	// Find higher power 2 number which is divisible by given number
	func power2Divisible(_ num: Int)
	{
		// Find highest divide number
		let n: Int = (num & (~(num - 1)));
		// Display calculated result
		print("\n Number : ", num, terminator: "");
		print("\n Power  : ", n );
	}
}
func main()
{
	let task: Power = Power();
	// Test Cases
	task.power2Divisible(10);
	task.power2Divisible(40);
	task.power2Divisible(64);
	task.power2Divisible(43);
}
main();

Output

 Number :  10
 Power  :  2

 Number :  40
 Power  :  8

 Number :  64
 Power  :  64

 Number :  43
 Power  :  1
/*
  Kotlin program
  Highest power of two that divides a given number
*/
class Power
{
	// Find higher power 2 number which is divisible by given number
	fun power2Divisible(num: Int): Unit
	{
		// Find highest divide number
		var n: Int = (num and((num - 1).inv()));
		// Display calculated result
		print("\n Number : " + num);
		print("\n Power  : " + n + "\n");
	}
}
fun main(args: Array < String > ): Unit
{
	var task: Power = Power();
	// Test Cases
	task.power2Divisible(10);
	task.power2Divisible(40);
	task.power2Divisible(64);
	task.power2Divisible(43);
}

Output

 Number : 10
 Power  : 2

 Number : 40
 Power  : 8

 Number : 64
 Power  : 64

 Number : 43
 Power  : 1

Explanation

Let's analyze the given code and its output for different test cases:

Test Case 1: power2Divisible(10)

  • num = 10
  • The binary representation of 10 is 1010.
  • The rightmost set bit is at position 1 (from the right).
  • The value of n = 2^1 = 2.
  • Output: Number: 10, Power: 2

Test Case 2: power2Divisible(40)

  • num = 40
  • The binary representation of 40 is 101000.
  • The rightmost set bit is at position 4 (from the right).
  • The value of n = 2^4 = 16.
  • Output: Number: 40, Power: 16

Test Case 3: power2Divisible(64)

  • num = 64
  • The binary representation of 64 is 1000000.
  • The rightmost set bit is at position 7 (from the right).
  • The value of n = 2^7 = 128.
  • Output: Number: 64, Power: 128

Test Case 4: power2Divisible(43)

  • num = 43
  • The binary representation of 43 is 101011.
  • The rightmost set bit is at position 0 (from the right).
  • The value of n = 2^0 = 1.
  • Output: Number: 43, Power: 1

Time Complexity: The time complexity of the algorithm is O(1) since the calculation of the highest power of 2 that divides the number involves a constant number of bitwise operations, irrespective of the input size.

In conclusion, the provided code successfully finds the highest power of two that divides a given number using bitwise operations. It is a simple and efficient algorithm with a time complexity of O(1).

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





Categories
Relative Post