Toggle The First And Last Bits Of A Number In C++

Given an integer n, rearrange its binary representation so that the first and last bits are identical by flipping the necessary bits while keeping the middle bits unchanged. Utilize bitwise operators to manipulate individual bits in binary numbers effectively.

For Example:

Input = 12

Output = 3

Explanation:

12 -> Binary Expansion of input 12 is 1100

When the initial and final bits of the binary representation of the number 12 are switched, the resulting binary number is 0011.

0011 à 3

Therefore, by switching the initial and final bits of the provided input, the result will be 3.

Input = 30

Output = 15

Explanation:

30 -> Binary Expansion of input 30 is 11110.

After switching the initial and final bits of the binary representation of the decimal number 30, it transforms into 01111.

01111à 15

Therefore, by switching the initial and final bits in the provided input, the result will be 15.

Input = 145

Output = 16

Explanation:

145 -> Binary Expansion of input 145 10010001

After switching the initial and final bits of the binary representation of the number 145, it transforms into 00010000.

00010000 à 16

Therefore, by switching the initial and final bits of the provided input, the result will be 16.

Approach:

This technique involves employing the leftward shift operator in combination with bitwise XOR. The bitwise XOR operator returns 1 when the respective bits of the two operands differ, and 0 otherwise. We will leverage the bit-flipping capability of the bitwise XOR operator. For instance, if the integer n's first bit is 1, performing n ^ 1 will change the first bit to 0. Moreover, executing the operation n ^ 1 will switch the original bit of the number from 0 to 1 if it is currently 0.

We calculate n ^ 1 to toggle the initial bit of the number n. To change the value, it performs an exclusive OR operation between the Least Significant Bit and the first bit of n with 1. A new number, k, is generated where only the least significant bit is activated, serving the purpose of flipping the final bit. The resulting bit, r, is positioned at a value equivalent to the logarithm base 2 of n. This correlation is due to the fact that the binary representation of n consists of log2(n) bits.

Algorithm:

• ✅ First, read the input value, n.
• ✅ Apply XOR to toggle the first bit of n: n = n XOR 1.
• ✅ Put the value 0 in the counter variable pos.
• ✅ Assign the value of n to the temporary variable temp.
• ✅ When the temperature is not zero: Move the temperature to the right by 1%. - Increase pos by 1.
• ✅ Apply the XOR operation with a mask to toggle the final bit of n: n = n XOR (1 \\ (pos - 1)).
• ✅ Give the resultant number, n, out.

Example 1:

Let's consider a C++ code snippet to invert the first and last bits of a number using the XOR operation:

#include <iostream>
using namespace std;
// Function to toggle the first bit of a number using XOR
void toggle_first_bit(int& n) {
    n ^= 1;  // Toggle the first bit
}
// Function to toggle the last bit of a number using XOR
void toggle_last_bit(int& n) {
    // Find the position of the last bit
    int pos = 0;
    int temp = n;
    while (temp) {
        temp >>= 1;
        pos++;
    }
    // Toggle the last bit
    n ^= 1 << (pos - 1);
}
int main() {
    int n;
    cout << "Enter a number: ";
    cin >> n;
    cout << "Input number: " << n << endl;
    // Toggling the first bit
    toggle_first_bit(n);
    // Toggling the last bit
    toggle_last_bit(n);
    cout << "Decimal value after toggling first and last bits: " << n << endl;
    return 0;
}

Output:

Explanation:

• ✅ The togglefirstbit function toggles the first bit of the number using the XOR operation.
• ✅ togglelastbit function finds the last digit position and toggles it using XOR.
• ✅ In the 'main' function, we will call both the functions togglefirstbit and togglefirstbit functions to toggle the first and last bits of the input number respectively.
• ✅ Finally, we will print the decimal value of the modified number as an output.

Complexity Analysis:

Time Complexity:

Its time efficiency is O(1) as the function executes in a constant duration irrespective of the number of inputs provided.

Space Complexity:

Its space complexity is O(1) as it does not require any additional space in its execution.