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)
{
// Test Cases
}
}``````

#### 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()
{
// Test Cases
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)
{
// Test Cases
}
}``````

#### 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()
{
// Test Cases
}
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()
{
// Test Cases
}
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() :
#  Test Cases

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()
#  Test Cases
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
}
}``````

#### 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()
{
// Test Cases
}
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
{
// Test Cases
}``````

#### 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.

Categories
Relative Post