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)
{
// (16) 10000 => 00001 (1)
// (45) 101101 => 001100 (12)
// (100) 1100100 => (37)   0100101
}
}``````

#### 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()
{
// (16) 10000 => 00001 (1)
// (45) 101101 => 001100 (12)
// (100) 1100100 => (37)   0100101
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)
{
// (16) 10000 => 00001 (1)
// (45) 101101 => 001100 (12)
// (100) 1100100 => (37)   0100101
}
}``````

#### 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()
{
// (16) 10000 => 00001 (1)
// (45) 101101 => 001100 (12)
// (100) 1100100 => (37)   0100101
}
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()
{
// (16) 10000 => 00001 (1)
// (45) 101101 => 001100 (12)
// (100) 1100100 => (37)   0100101
}
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() :
#  (16) 10000 => 00001 (1)
#  (45) 101101 => 001100 (12)
#  (100) 1100100 => (37)   0100101

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()
#  (16) 10000 => 00001 (1)
#  (45) 101101 => 001100 (12)
#  (100) 1100100 => (37)   0100101
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)
// (45) 101101 => 001100 (12)
// (100) 1100100 => (37)   0100101
}
}``````

#### 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()
{
// (16) 10000 => 00001 (1)
// (45) 101101 => 001100 (12)
// (100) 1100100 => (37)   0100101
}
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
{
// (16) 10000 => 00001 (1)
// (45) 101101 => 001100 (12)
// (100) 1100100 => (37)   0100101
}``````

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

Categories
Relative Post