Explain in layman terms, why this midpoint formula works. I understand the LITER
ID: 3876087 • Letter: E
Question
Explain in layman terms, why this midpoint formula works. I understand the LITERAL operations that are occuring (&, ^, >>), I do not need them explained, but what trend does this produce in the numbers that allows this formula to calculate midpoint without overflow and while handling negative operations gracefully?
Again, I understand how & works, how ^ works, how >>1 works, but why do these specific operations produce an accurate midpoint formula? What trend or pattern does this use to be able to produce a midpoint?
Please do not just tell me how &, ^, and >> work. I want to understand how the algorithm itself works.
midpoint(int low, int high) return (low & high) ((low A high) >> 1);Explanation / Answer
/*
Answer :
As you have already mentioned, that you know how the operators &, ^ and >> works, i would like to tell you more about this.
& [BITWISE AND OPERATOR] : Binary AND Operator copies a bit to the result if it exists in both operands.
^ [BITWISE XOR] : Binary XOR Operator copies the bit if it is set in one operand but not both.
>> [RIGHT SHIFT] : The left operands value is moved right by the number of bits specified by the right operand.
The method you have mentioned to calculate the mid-point formula have a very high efifciency as it calculates the result without any overflow problem and handling the signed numbers perfectly.
*/
midpoint(int low, int high) // This method takes two integer values high and low
{
return (low & high) + ((low^high) >> 1);
}
/*
Let Us Understand the whole algorithm.
Assume the values of low and high be 10 and 12 respectively, which are actually : 1010 and 1110 in binary representations.
BITWISE AND OPERATOR [&] copies a bit to the result if it exists in both operands.
So, in our example, we have (10 & 12), that is, (1010 & 1100), so the result will be 1000, which equals to 8 in decimal.
It is equivalent to AND of 1010 and 1100.
BITWISE XOR OPERATOR [^] copies the bit if it is set in one operand but not both.
So, in our example, we have (10 ^ 12), that is, (1010 ^ 1100), so the result will be 0110, which equals to 6 in decimal.
It is equivalent to XOR of 1010 and 1100.
RIGHT SHIFT OPERATOR [>>] moves operands value to right by the number of bits specified by the right operand.
So, in our example, we have ((10 ^ 12) >> 1), that is, ((1010 ^ 1100) >> 1), represents that decimal value 6 or 0110 would be shifted
to right by one place, i.e., 0011.
Now, as we know, binary system follows the rule 32 16 8 4 2 1 , we can observe that each digit moving towards left side is double of
its right digit. So, we can safely say that whatever the value would be, if we right shift any value by one, it would become its half.
Algorithm Exact Working :
This algorithm works due to the related behaviour of BITWISE AND OPERATOR and BITWISE XOR OPERATOR. Whatever result & operator generates,
but ^ operator will always generate a result which when halved and added to '&' result will give midpoint of the numbers. There is no
defined pattern to this.
For example, for the numbers 30 and 40 ;
30 & 40 : 8
30 ^ 40 : 54
When Halved
Result : 8 + 27 = 35
For example, for the numbers 23 and 77 ;
23 & 77 : 5
23 ^ 77 : 90
When Halved
Result : 5 + 45 = 50
This is the reason why XOR and AND gates are used primitively in Half Adders in Full Adders innLogic Gates Designing.
HENCE, it is safe to say that the only reason this algorithm works is because of the inter-related behaviour of XOR and AND oeprators.
*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.