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.
- Start the function power2Divisible(num).
- 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.
- 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).
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