Find nearest power of 2 less than or equal to a number

The given problem is to find the nearest power of 2 that is less than or equal to a given number. In other words, we need to find the largest power of 2 that does not exceed the given number. For example, if the input number is 10, the nearest power of 2 less than or equal to 10 is 8. Similarly, for 31, the nearest power of 2 is 16, and for 64, it is 64 itself.

Explanation with suitable examples

Let's understand the process with the example of finding the nearest power of 2 less than or equal to 43.

1. Binary Representation of 43: The binary representation of 43 is 101011.
2. Set all Bits: We start by setting all bits to the right of the most significant bit (MSB) to 1. The new binary number after this operation is 111111.
3. Get Final Result: After getting all bits set, we perform an XOR operation with the number obtained in step 2. The result is 010000, which is 16 in decimal.

Standard Pseudocode

Function nearestPower2(num):
    n = num
    n = n | n >> 1
    n = n | n >> 2
    n = n | n >> 4
    n = n | n >> 8
    n = n | n >> 16
    n = n ^ (n >> 1)
    return n

Algorithm with proper explanation

1. Start by initializing a variable n with the input number num.
2. Perform bitwise OR operation with right-shifted versions of n. This step is used to set all the bits to the right of the most significant bit (MSB). The idea behind this step is to create a binary number with all bits set from the MSB to the least significant bit (LSB). For example, if num is 43 (101011 in binary), after this operation, n becomes 63 (111111 in binary).
3. Perform an XOR operation with the number obtained in step 2 and its right-shifted version. This step will result in a binary number with only the bit at the MSB set and all other bits set to 0. The MSB represents the nearest power of 2. For example, if n is 63 (111111 in binary), after this operation, n becomes 16 (010000 in binary), which corresponds to the nearest power of 2 less than or equal to 43.

Code Solution

Here given code implementation process.

• C
• Java
• C++
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4
• Kotlin

// C program 
// Find nearest power of 2 less than or equal to a number
#include <stdio.h>

// Find nearest power of given number
void nearestPower2(int num)
{
	int n = num;
	// First set all bits
	n = n | n >> 1;
	n = n | n >> 2;
	n = n | n >> 4;
	n = n | n >> 8;
	n = n | n >> 16;
	// Get final result
	// n are indicates all active bits of given a number
	// So shift n one by left and perform xor operation
	n = n ^ (n >> 1);
	// Display calculated result
	printf("\n Number :  %d", num);
	printf("\n Power  :  %d\n", n);
}
int main(int argc, char
	const *argv[])
{
	// Test Cases
	nearestPower2(10);
	nearestPower2(31);
	nearestPower2(64);
	nearestPower2(43);
	return 0;
}

 Number :  10
 Power  :  8

 Number :  31
 Power  :  16

 Number :  64
 Power  :  64

 Number :  43
 Power  :  32

/*
  Java program
  Find nearest power of 2 less than or equal to a number
*/
public class Power
{
   
    // Find nearest power of given number
    public void nearestPower2(int num)
    {
        int n = num;
        // First set all bits
        n = n | n >> 1;
        n = n | n >> 2;
        n = n | n >> 4;
        n = n | n >> 8;
        n = n | n >> 16;
        // Get final result
        // n are indicates all active bits of given a number
        // So shift n one by left and perform xor operation
        n = n ^ (n >> 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.nearestPower2(10);
        task.nearestPower2(31);
        task.nearestPower2(64);
        task.nearestPower2(43);
    }
}

 Number : 10
 Power : 8

 Number : 31
 Power : 16

 Number : 64
 Power : 64

 Number : 43
 Power : 32

// Include header file
#include <iostream>
using namespace std;

/*
  C++ program
  Find nearest power of 2 less than or equal to a number
*/

class Power
{
	public:
		// Find nearest power of given number
		void nearestPower2(int num)
		{
			int n = num;
			// First set all bits
			n = n | n >> 1;
			n = n | n >> 2;
			n = n | n >> 4;
			n = n | n >> 8;
			n = n | n >> 16;
			// Get final result
			// n are indicates all active bits of given a number
			// So shift n one by left and perform xor operation
			n = n ^ (n >> 1);
			// Display calculated result
			cout << "\n Number : " << num;
			cout << "\n Power : " << n << "\n";
		}
};
int main()
{
	Power task = Power();
	// Test Cases
	task.nearestPower2(10);
	task.nearestPower2(31);
	task.nearestPower2(64);
	task.nearestPower2(43);
	return 0;
}

 Number : 10
 Power : 8

 Number : 31
 Power : 16

 Number : 64
 Power : 64

 Number : 43
 Power : 32

// Include namespace system
using System;
/*
  C# program
  Find nearest power of 2 less than or equal to a number
*/
public class Power
{
	// Find nearest power of given number
	public void nearestPower2(int num)
	{
		int n = num;
		// First set all bits
		n = n | n >> 1;
		n = n | n >> 2;
		n = n | n >> 4;
		n = n | n >> 8;
		n = n | n >> 16;
		// Get final result
		// n are indicates all active bits of given a number
		// So shift n one by left and perform xor operation
		n = n ^ (n >> 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.nearestPower2(10);
		task.nearestPower2(31);
		task.nearestPower2(64);
		task.nearestPower2(43);
	}
}

 Number : 10
 Power : 8

 Number : 31
 Power : 16

 Number : 64
 Power : 64

 Number : 43
 Power : 32

<?php
/*
  Php program
  Find nearest power of 2 less than or equal to a number
*/
class Power
{
	// Find nearest power of given number
	public	function nearestPower2($num)
	{
		$n = $num;
		// First set all bits
		$n = $n | $n >> 1;
		$n = $n | $n >> 2;
		$n = $n | $n >> 4;
		$n = $n | $n >> 8;
		$n = $n | $n >> 16;
		// Get final result
		// n are indicates all active bits of given a number
		// So shift n one by left and perform xor operation
		$n = $n ^ ($n >> 1);
		// Display calculated result
		echo "\n Number : ". $num;
		echo "\n Power : ". $n ."\n";
	}
}

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

 Number : 10
 Power : 8

 Number : 31
 Power : 16

 Number : 64
 Power : 64

 Number : 43
 Power : 32

/*
  Node Js program
  Find nearest power of 2 less than or equal to a number
*/
class Power
{
	// Find nearest power of given number
	nearestPower2(num)
	{
		var n = num;
		// First set all bits
		n = n | n >> 1;
		n = n | n >> 2;
		n = n | n >> 4;
		n = n | n >> 8;
		n = n | n >> 16;
		// Get final result
		// n are indicates all active bits of given a number
		// So shift n one by left and perform xor operation
		n = n ^ (n >> 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.nearestPower2(10);
	task.nearestPower2(31);
	task.nearestPower2(64);
	task.nearestPower2(43);
}
main();

 Number : 10
 Power : 8

 Number : 31
 Power : 16

 Number : 64
 Power : 64

 Number : 43
 Power : 32

#   Python 3 program
#   Find nearest power of 2 less than or equal to a number

class Power :
	#  Find nearest power of given number
	def nearestPower2(self, num) :
		n = num
		#  First set all bits
		n = n | n >> 1
		n = n | n >> 2
		n = n | n >> 4
		n = n | n >> 8
		n = n | n >> 16
		#  Get final result
		#  n are indicates all active bits of given a number
		#  So shift n one by left and perform xor operation
		n = n ^ (n >> 1)
		#  Display calculated result
		print("\n Number : ", num, end = "")
		print("\n Power : ", n )
	

def main() :
	task = Power()
	#  Test Cases
	task.nearestPower2(10)
	task.nearestPower2(31)
	task.nearestPower2(64)
	task.nearestPower2(43)

if __name__ == "__main__": main()

 Number :  10
 Power :  8

 Number :  31
 Power :  16

 Number :  64
 Power :  64

 Number :  43
 Power :  32

#   Ruby program
#   Find nearest power of 2 less than or equal to a number

class Power 
	#  Find nearest power of given number
	def nearestPower2(num) 
		n = num
		#  First set all bits
		n = n | n >> 1
		n = n | n >> 2
		n = n | n >> 4
		n = n | n >> 8
		n = n | n >> 16
		#  Get final result
		#  n are indicates all active bits of given a number
		#  So shift n one by left and perform xor operation
		n = n ^ (n >> 1)
		#  Display calculated result
		print("\n Number : ", num)
		print("\n Power : ", n ,"\n")
	end

end

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

main()

 Number : 10
 Power : 8

 Number : 31
 Power : 16

 Number : 64
 Power : 64

 Number : 43
 Power : 32

/*
  Scala program
  Find nearest power of 2 less than or equal to a number
*/
class Power
{
	// Find nearest power of given number
	def nearestPower2(num: Int): Unit = {
		var n: Int = num;
		// First set all bits
		n = n | n >> 1;
		n = n | n >> 2;
		n = n | n >> 4;
		n = n | n >> 8;
		n = n | n >> 16;
		// Get final result
		// n are indicates all active bits of given a number
		// So shift n one by left and perform xor operation
		n = n ^ (n >> 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.nearestPower2(10);
		task.nearestPower2(31);
		task.nearestPower2(64);
		task.nearestPower2(43);
	}
}

 Number : 10
 Power : 8

 Number : 31
 Power : 16

 Number : 64
 Power : 64

 Number : 43
 Power : 32

/*
  Swift 4 program
  Find nearest power of 2 less than or equal to a number
*/
class Power
{
	// Find nearest power of given number
	func nearestPower2(_ num: Int)
	{
		var n: Int = num;
		// First set all bits
		n = n | n >> 1;
		n = n | n >> 2;
		n = n | n >> 4;
		n = n | n >> 8;
		n = n | n >> 16;
		// Get final result
		// n are indicates all active bits of given a number
		// So shift n one by left and perform xor operation
		n = n ^ (n >> 1);
		// Display calculated result
		print("\n Number : ", num, terminator: "");
		print("\n Power : ", n );
	}
}
func main()
{
	let task: Power = Power();
	// Test Cases
	task.nearestPower2(10);
	task.nearestPower2(31);
	task.nearestPower2(64);
	task.nearestPower2(43);
}
main();

 Number :  10
 Power :  8

 Number :  31
 Power :  16

 Number :  64
 Power :  64

 Number :  43
 Power :  32

/*
  Kotlin program
  Find nearest power of 2 less than or equal to a number
*/
class Power
{
	// Find nearest power of given number
	fun nearestPower2(num: Int): Unit
	{
		var n: Int = num;
		// First set all bits
		n = n or (n shr 1);
		n = n or (n shr 2);
		n = n or (n shr 4);
		n = n or (n shr 8);
		n = n or (n shr 16);
		// Get final result
		// n are indicates all active bits of given a number
		// So shift n one by left and perform xor operation
		n = n xor (n shr 1);
		// 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.nearestPower2(10);
	task.nearestPower2(31);
	task.nearestPower2(64);
	task.nearestPower2(43);
}

 Number : 10
 Power : 8

 Number : 31
 Power : 16

 Number : 64
 Power : 64

 Number : 43
 Power : 32

Resultant output explanation by statement

1. nearestPower2(10); Output: Number: 10, Power: 8 The nearest power of 2 less than or equal to 10 is 8.

2. nearestPower2(31); Output: Number: 31, Power: 16 The nearest power of 2 less than or equal to 31 is 16.

3. nearestPower2(64); Output: Number: 64, Power: 64 The nearest power of 2 less than or equal to 64 is 64 itself, as it is already a power of 2.

4. nearestPower2(43); Output: Number: 43, Power: 32 The nearest power of 2 less than or equal to 43 is 32.

Time Complexity of the code

The time complexity of the given code is O(1). It doesn't depend on the value of the input number num but instead performs a fixed number of bitwise operations (shift and OR) and one XOR operation. The number of operations remains constant regardless of the size of the input, resulting in a constant time complexity.