Check if given two numbers can be made equal by changing 1 or 2 bits in C++

In the field of computer programming, many operations revolve around numerical values. In some cases, we may need to determine whether two numbers can be made equal by modifying a few bits. While this problem can present challenges, the right strategy will lead to a successful solution.

grammar

In order to build a solid foundation for a deep understanding of the algorithm, let us first familiarize ourselves with the syntax used in subsequent coding by using this specific method.

bool checkEquality(int num1, int num2);

Generate a boolean response by using the checkEquality function to determine whether the given two integers num1 and num2 can be made equal by changing only one or two bits.

algorithm

Here is a step-by-step breakdown of our algorithm:

• Determine the XOR result of num1 and num2 and assign the output to a new variable xorResult.

• Use an algorithm to calculate the number of set bits in xorResult and assign the result to a variable named setBitCount.

• In order for the operation to be successful, setBitCount cannot exceed 2. In this case, our function will return a true result. If this specified threshold is exceeded, we can conclude that our output must be false.

• Now that we have the algorithm, let's dive into at least two different ways to solve this problem.

Method 1: Bit Operation

In this method we will use bit operations to check if the numbers can be made equal.

Example

#include <iostream>

bool checkEquality(int num1, int num2) {
   int xorResult = num1 ^ num2;
   int bitCheck = xorResult & (xorResult - 1);
   return (bitCheck == 0);
}

int main() {
   int number1, number2;
   std::cout << "Enter the first number: ";
   std::cin >> number1;
   std::cout << "Enter the second number: ";
   std::cin >> number2;
    
   bool result = checkEquality(number1, number2);
   if (result) {
      std::cout << "It is possible to make the numbers equal by changing only one or two bits." << std::endl;
   } else {
      std::cout << "It is not possible to make the numbers equal by changing only one or two bits." << std::endl;
   }  
   return 0;
}

Output

Enter the first number: Enter the second number: It is not possible to make the numbers equal by changing only one or two bits.

explain

By modifying the value of one or two of the bits, the C code performs a simple check to determine whether perfect alignment between the two supplied values ​​can be established during processing. To achieve this goal, an important part of the code is to define a special function called "checkEquality". Using this custom function requires providing two integer variables as input. The output type of this particular function uses Boolean logic so that the user can easily obtain a result indicating whether the arguments provided to the function at runtime are sufficient for perfect numerical alignment.

For calculation purposes, this program uses the XOR algorithm to compare the above integer inputs via the checkEquality method. Afterwards, the automatically stored result is captured in the variable "xorResult". The key element in the next step is to calculate the bitwise AND intermediate result between xorResult and XORResult - 1. At this stage, when the return value is "0", the assumption of the bitCheck variable becomes necessary. Because it indicates that a necessary condition is met, we can assume that one or two bits in the integer input need to change to satisfy the request made by the checkEquality function. Once completed, the program prompts the user for input, before passing the parameters into the checkEquality method as the final calculation stage. After the process ends, an output message shows the presence/absence of the required bit-level changes and a corresponding message is displayed in the console output. This implementation shows an excellent example of bitwise manipulation and XOR exploits, from C.

Method 2: Hamming distance method

In this method, we will use the concept of Hamming distance to solve the problem.

Example

#include <iostream>

int countSetBits(int num) {
   int count = 0;
   while (num) {
      num &= (num - 1);
      count++;
   }
   return count;
}

bool checkEquality(int num1, int num2) {
   int xorResult = num1 ^ num2;
   int setBitCount = countSetBits(xorResult);
   return (setBitCount <= 2);
}

int main() {
   int number1, number2;
   std::cout << "Enter the first number: ";
   std::cin >> number1;
   std::cout << "Enter the second number: ";
   std::cin >> number2;
    
   bool result = checkEquality(number1, number2);
   if (result) {
      std::cout << "It is possible to make the numbers equal by changing only one or two bits." << std::endl;
   } else {
      std::cout << "It is not possible to make the numbers equal by changing only one or two bits." << std::endl;
   }   
   return 0;
}

Output

Enter the first number: Enter the second number: It is not possible to make the numbers equal by changing only one or two bits.

explain

In this example we provide a C program designed to determine whether we can make changes to one or possibly two bits to make two different numbers equivalent. Additionally, there is a function called "countSetBits" which utilizes Kemighan's algorithm to determine how many set bits are present in an integer value.

In the checkEquality function, the code calculates the exclusive OR of the two input numbers and stores the result in xorResult. The previous statement triggers the countSetBits function to determine the number of bits set in xorResult, which is then accumulated in setBitCount. Whenever setBitCount is determined to be two or less, it means that only one or two bits need to be modified to achieve balance, causing the function to return true. Otherwise, return false.

In the main function, the program prompts the user to enter two numbers. It then calls the checkEquality function using the user-supplied number and stores the result. Finally, depending on the value of the result, the program prints an appropriate message indicating whether it is possible to make the numbers equal by changing one or two bits.

This code provides a clear implementation of the problem, utilizing XOR operations and Kernighan's algorithm to efficiently calculate the set bits.

in conclusion

Our article delves into the problem of determining whether two given numbers can be equal while changing only one or two bits. To solve this problem, we propose two effective methods - bit operation method and Hamming distance method. Both methods provide efficient solutions. We also provide real executable code examples based on these methods. By understanding and implementing these methods, you can effectively check whether two numbers can be made equal by changing a few bits.

The above is the detailed content of Check if given two numbers can be made equal by changing 1 or 2 bits in C++. For more information, please follow other related articles on the PHP Chinese website!