Posted on by Kalkicode
Code Bit Logic

Change first and last bits of a number

In computer science, bitwise manipulation is a fundamental operation that involves manipulating individual bits of a binary number. The given problem revolves around the concept of changing the first and last bits of a given number using bitwise operations. The goal is to convert the first and last set bits of the number to 1, while keeping the rest of the bits unchanged.

Problem Statement

Given an integer number, the task is to change the first and last set bits of the number and return the modified result. To achieve this, we will define a function called changeFirstLast(num) that will perform the necessary bitwise operations to modify the number.

Explanation with Suitable Example

Let's take the example of the number 45. In binary representation, 45 is 101101. The first set bit is at position 6 (from the right, starting from 0) and the last set bit is at position 0.

We can observe that by setting the first and last bits of the number to 1, the number will change from 101101 to 001100, which is the binary representation of the decimal number 12.

Pseudocode

activeAllBits(num):
    n = num
    n = n | n >> 1
    n = n | n >> 2
    n = n | n >> 4
    n = n | n >> 8
    n = n | n >> 16
    return n

changeFirstLast(num):
    n = 0
    if num > 1:
        n = activeAllBits(num)
        n = num ^ ((n + 1) >> 1) + 1
    return n

Algorithm Explanation

  1. The activeAllBits(num) function sets all the bits of the given number to 1 from the first set bit to the last set bit using bitwise OR operations.
  2. In the changeFirstLast(num) function, we first initialize a variable n to 0.
  3. If the given num is greater than 1, we call the activeAllBits(num) function to activate all the bits from the first to the last set bit.
  4. Next, we perform the following bitwise operations:
    • We add 1 to n, right-shift the result by 1, and then perform a bitwise XOR operation with the original num. This sets the first set bit of num to 1.
    • Finally, we add 1 to the modified num, which sets the last set bit of num to 1.
  5. The modified num is then returned.

Code Solution

Here given code implementation process.

// C Program 
// Change first and last bits of a number
#include <stdio.h>

// Active all the bits of present in a number
int activeAllBits(int num)
{
	int n = num;
	n = n | n >> 1;
	n = n | n >> 2;
	n = n | n >> 4;
	n = n | n >> 8;
	n = n | n >> 16;
	return n;
}
// Change the first and last bits of given number
void changeFirstLast(int num)
{
	int n = 0;
	if (num > 1)
	{
		n = activeAllBits(num);
		// Change first and last bits
		n = num ^ ((n + 1) >> 1) + 1;
	}
	// Display calculated result
	printf(" Number : %d", num);
	printf("\n After Active : %d\n", n);
}
int main()
{
	// (16) 10000 => 00001 (1)
	changeFirstLast(16);
	// (45) 101101 => 001100 (12) 
	changeFirstLast(45);
	// (100) 1100100 => (37)   0100101
	changeFirstLast(100);
	return 0;
}

Output

 Number : 16
 After Active : 1
 Number : 45
 After Active : 12
 Number : 100
 After Active : 37
/*
  Java Program for
  Change first and last bits of a number
*/
public class SwitchBits
{
	// Active all the bits of present in a number
	public int activeAllBits(int num)
	{
		int n = num;
		n = n | n >> 1;
		n = n | n >> 2;
		n = n | n >> 4;
		n = n | n >> 8;
		n = n | n >> 16;
		return n;
	}
	// Change the first and last bits of given number
	public void changeFirstLast(int num)
	{
		int n = 0;
		if (num > 1)
		{
			n = activeAllBits(num);
			// Change first and last bits
			n = num ^ ((n + 1) >> 1) + 1;
		}
		// Display calculated result
		System.out.print(" Number : " + num);
		System.out.print("\n After Active : " + n + "\n");
	}
	public static void main(String[] args)
	{
		SwitchBits task = new SwitchBits();
		// (16) 10000 => 00001 (1)
		task.changeFirstLast(16);
		// (45) 101101 => 001100 (12) 
		task.changeFirstLast(45);
		// (100) 1100100 => (37)   0100101
		task.changeFirstLast(100);
	}
}

Output

 Number : 16
 After Active : 1
 Number : 45
 After Active : 12
 Number : 100
 After Active : 37
// Include header file
#include <iostream>

using namespace std;
/*
  C++ Program for
  Change first and last bits of a number
*/
class SwitchBits
{
	public:
		// Active all the bits of present in a number
		int activeAllBits(int num)
		{
			int n = num;
			n = n | n >> 1;
			n = n | n >> 2;
			n = n | n >> 4;
			n = n | n >> 8;
			n = n | n >> 16;
			return n;
		}
	// Change the first and last bits of given number
	void changeFirstLast(int num)
	{
		int n = 0;
		if (num > 1)
		{
			n = this->activeAllBits(num);
			// Change first and last bits
			n = num ^ ((n + 1) >> 1) + 1;
		}
		// Display calculated result
		cout << " Number : " << num;
		cout << "\n After Active : " << n << "\n";
	}
};
int main()
{
	SwitchBits task = SwitchBits();
	// (16) 10000 => 00001 (1)
	task.changeFirstLast(16);
	// (45) 101101 => 001100 (12)
	task.changeFirstLast(45);
	// (100) 1100100 => (37)   0100101
	task.changeFirstLast(100);
	return 0;
}

Output

 Number : 16
 After Active : 1
 Number : 45
 After Active : 12
 Number : 100
 After Active : 37
// Include namespace system
using System;
/*
  C# Program for
  Change first and last bits of a number
*/
public class SwitchBits
{
	// Active all the bits of present in a number
	public int activeAllBits(int num)
	{
		int n = num;
		n = n | n >> 1;
		n = n | n >> 2;
		n = n | n >> 4;
		n = n | n >> 8;
		n = n | n >> 16;
		return n;
	}
	// Change the first and last bits of given number
	public void changeFirstLast(int num)
	{
		int n = 0;
		if (num > 1)
		{
			n = activeAllBits(num);
			// Change first and last bits
			n = num ^ ((n + 1) >> 1) + 1;
		}
		// Display calculated result
		Console.Write(" Number : " + num);
		Console.Write("\n After Active : " + n + "\n");
	}
	public static void Main(String[] args)
	{
		SwitchBits task = new SwitchBits();
		// (16) 10000 => 00001 (1)
		task.changeFirstLast(16);
		// (45) 101101 => 001100 (12)
		task.changeFirstLast(45);
		// (100) 1100100 => (37)   0100101
		task.changeFirstLast(100);
	}
}

Output

 Number : 16
 After Active : 1
 Number : 45
 After Active : 12
 Number : 100
 After Active : 37
<?php
/*
  Php Program for
  Change first and last bits of a number
*/
class SwitchBits
{
	// Active all the bits of present in a number
	public	function activeAllBits($num)
	{
		$n = $num;
		$n = $n | $n >> 1;
		$n = $n | $n >> 2;
		$n = $n | $n >> 4;
		$n = $n | $n >> 8;
		$n = $n | $n >> 16;
		return $n;
	}
	// Change the first and last bits of given number
	public	function changeFirstLast($num)
	{
		$n = 0;
		if ($num > 1)
		{
			$n = $this->activeAllBits($num);
			// Change first and last bits
			$n = $num ^ (($n + 1) >> 1) + 1;
		}
		// Display calculated result
		echo " Number : ". $num;
		echo "\n After Active : ". $n ."\n";
	}
}

function main()
{
	$task = new SwitchBits();
	// (16) 10000 => 00001 (1)
	$task->changeFirstLast(16);
	// (45) 101101 => 001100 (12)
	$task->changeFirstLast(45);
	// (100) 1100100 => (37)   0100101
	$task->changeFirstLast(100);
}
main();

Output

 Number : 16
 After Active : 1
 Number : 45
 After Active : 12
 Number : 100
 After Active : 37
/*
  Node Js Program for
  Change first and last bits of a number
*/
class SwitchBits
{
	// Active all the bits of present in a number
	activeAllBits(num)
	{
		var n = num;
		n = n | n >> 1;
		n = n | n >> 2;
		n = n | n >> 4;
		n = n | n >> 8;
		n = n | n >> 16;
		return n;
	}
	// Change the first and last bits of given number
	changeFirstLast(num)
	{
		var n = 0;
		if (num > 1)
		{
			n = this.activeAllBits(num);
			// Change first and last bits
			n = num ^ ((n + 1) >> 1) + 1;
		}
		// Display calculated result
		process.stdout.write(" Number : " + num);
		process.stdout.write("\n After Active : " + n + "\n");
	}
}

function main()
{
	var task = new SwitchBits();
	// (16) 10000 => 00001 (1)
	task.changeFirstLast(16);
	// (45) 101101 => 001100 (12)
	task.changeFirstLast(45);
	// (100) 1100100 => (37)   0100101
	task.changeFirstLast(100);
}
main();

Output

 Number : 16
 After Active : 1
 Number : 45
 After Active : 12
 Number : 100
 After Active : 37
#   Python 3 Program for
#   Change first and last bits of a number

class SwitchBits :
	#  Active all the bits of present in a number
	def activeAllBits(self, num) :
		n = num
		n = n | n >> 1
		n = n | n >> 2
		n = n | n >> 4
		n = n | n >> 8
		n = n | n >> 16
		return n
	
	#  Change the first and last bits of given number
	def changeFirstLast(self, num) :
		n = 0
		if (num > 1) :
			n = self.activeAllBits(num)
			#  Change first and last bits
			n = num ^ ((n + 1) >> 1) + 1
		
		#  Display calculated result
		print(" Number : ", num, end = "")
		print("\n After Active : ", n )
	

def main() :
	task = SwitchBits()
	#  (16) 10000 => 00001 (1)
	task.changeFirstLast(16)
	#  (45) 101101 => 001100 (12) 
	task.changeFirstLast(45)
	#  (100) 1100100 => (37)   0100101
	task.changeFirstLast(100)

if __name__ == "__main__": main()

Output

 Number :  16
 After Active :  1
 Number :  45
 After Active :  12
 Number :  100
 After Active :  37
#   Ruby Program for
#   Change first and last bits of a number

class SwitchBits 
	#  Active all the bits of present in a number
	def activeAllBits(num) 
		n = num
		n = n | n >> 1
		n = n | n >> 2
		n = n | n >> 4
		n = n | n >> 8
		n = n | n >> 16
		return n
	end

	#  Change the first and last bits of given number
	def changeFirstLast(num) 
		n = 0
		if (num > 1) 
			n = self.activeAllBits(num)
			#  Change first and last bits
			n = num ^ ((n + 1) >> 1) + 1
		end

		#  Display calculated result
		print(" Number : ", num)
		print("\n After Active : ", n ,"\n")
	end

end

def main() 
	task = SwitchBits.new()
	#  (16) 10000 => 00001 (1)
	task.changeFirstLast(16)
	#  (45) 101101 => 001100 (12) 
	task.changeFirstLast(45)
	#  (100) 1100100 => (37)   0100101
	task.changeFirstLast(100)
end

main()

Output

 Number : 16
 After Active : 1
 Number : 45
 After Active : 12
 Number : 100
 After Active : 37
/*
  Scala Program for
  Change first and last bits of a number
*/
class SwitchBits
{
	// Active all the bits of present in a number
	def activeAllBits(num: Int): Int = {
		var n: Int = num;
		n = n | n >> 1;
		n = n | n >> 2;
		n = n | n >> 4;
		n = n | n >> 8;
		n = n | n >> 16;
		return n;
	}
	// Change the first and last bits of given number
	def changeFirstLast(num: Int): Unit = {
		var n: Int = 0;
		if (num > 1)
		{
			n = this.activeAllBits(num);
			// Change first and last bits
			n = num ^ ((n + 1) >> 1) + 1;
		}
		// Display calculated result
		print(" Number : " + num);
		print("\n After Active : " + n + "\n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: SwitchBits = new SwitchBits();
		// (16) 10000 => 00001 (1)
		task.changeFirstLast(16);
		// (45) 101101 => 001100 (12)
		task.changeFirstLast(45);
		// (100) 1100100 => (37)   0100101
		task.changeFirstLast(100);
	}
}

Output

 Number : 16
 After Active : 1
 Number : 45
 After Active : 12
 Number : 100
 After Active : 37
/*
  Swift 4 Program for
  Change first and last bits of a number
*/
class SwitchBits
{
	// Active all the bits of present in a number
	func activeAllBits(_ num: Int)->Int
	{
		var n: Int = num;
		n = n | n >> 1;
		n = n | n >> 2;
		n = n | n >> 4;
		n = n | n >> 8;
		n = n | n >> 16;
		return n;
	}
	// Change the first and last bits of given number
	func changeFirstLast(_ num: Int)
	{
		var n: Int = 0;
		if (num > 1)
		{
			n = self.activeAllBits(num);
			// Change first and last bits
			n = num ^ ((n + 1) >> 1) + 1;
		}
		// Display calculated result
		print(" Number : ", num, terminator: "");
		print("\n After Active : ", n );
	}
}
func main()
{
	let task: SwitchBits = SwitchBits();
	// (16) 10000 => 00001 (1)
	task.changeFirstLast(16);
	// (45) 101101 => 001100 (12)
	task.changeFirstLast(45);
	// (100) 1100100 => (37)   0100101
	task.changeFirstLast(100);
}
main();

Output

 Number :  16
 After Active :  1
 Number :  45
 After Active :  14
 Number :  100
 After Active :  37
/*
  Kotlin Program for
  Change first and last bits of a number
*/
class SwitchBits
{
	// Active all the bits of present in a number
	fun activeAllBits(num: Int): Int
	{
		var n: Int = num;
		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);
		return n;
	}
	// Change the first and last bits of given number
	fun changeFirstLast(num: Int): Unit
	{
		var n: Int = 0;
		if (num > 1)
		{
			n = this.activeAllBits(num);
			// Change first and last bits
			n = num xor((n + 1) shr 1) + 1;
		}
		// Display calculated result
		print(" Number : " + num);
		print("\n After Active : " + n + "\n");
	}
}
fun main(args: Array < String > ): Unit
{
	var task: SwitchBits = SwitchBits();
	// (16) 10000 => 00001 (1)
	task.changeFirstLast(16);
	// (45) 101101 => 001100 (12)
	task.changeFirstLast(45);
	// (100) 1100100 => (37)   0100101
	task.changeFirstLast(100);
}

Output

 Number : 16
 After Active : 1
 Number : 45
 After Active : 12
 Number : 100
 After Active : 37

Resultant Output Explanation

  1. For the input number 16 (binary 10000), the first set bit is at position 4 and the last set bit is at position 0. After applying the changeFirstLast(num) function, the output is 1 (binary 00001), where the first and last bits have been changed as required.

  2. For the input number 45 (binary 101101), the first set bit is at position 6 and the last set bit is at position 0. After applying the changeFirstLast(num) function, the output is 12 (binary 001100), where the first and last bits have been changed as required.

  3. For the input number 100 (binary 1100100), the first set bit is at position 6 and the last set bit is at position 2. After applying the changeFirstLast(num) function, the output is 37 (binary 0100101), where the first and last bits have been changed as required.

Time Complexity Analysis

The time complexity of the given algorithm mainly depends on the number of bits in the input number num. Let's denote the number of bits in num as n.

  1. The activeAllBits(num) function takes O(n) time to activate all the bits from the first to the last set bit using bitwise OR operations.
  2. The changeFirstLast(num) function performs bitwise operations in constant time, i.e., 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