The magical effect of bit operation-find the average of two integers

The magical effect of bit operation-find the average of two integers

Article outline
  • Common implementation methods and drawbacks

  • Two bit operation implementation methods and differences

  • Digression-find the average of multiple numbers



How to find the average of two integers?

The problem seems simple, but there are many things worth studying if it is implemented in code.


Below we use Java code to achieve.


1 Ordinary realization 1

The easiest way to find the average of two integers is to add the two numbers and divide by two.
private static int mean(int x, int y) {
  return (x + y)/2;
}
 

However, if the two integers passed in are Integer.MAX_VALUE, the following assertion will fail.
Assert.assertEquals(Integer.MAX_VALUE,     
    mean(Integer.MAX_VALUE, Integer.MAX_VALUE)); 

We expect the result to be Integer.MAX_VALUE, but the result actually returned is -1. Because Integer.MAX_VALUE + Integer.MAX_VALUE = -2, the result has overflowed.
java.lang.AssertionError: 
Expected :2147483647
Actual   :-1 


2 Ordinary realization 2

If we use the unsigned right shift operator.
private static int mean1(int x, int y) {
  return (x + y) >>> 1;
} 
Although we can get the result Integer.MAX_VALUE we want in this way, it does not support negative numbers.

For example, we find the average of -9 and -3,
Assert.assertEquals(-6, mean1(-9, -34)); 

The expected result is -6, but it actually returns 2147483642
java.lang.AssertionError: 
Expected :-6
Actual   :2147483642 


3 Ordinary realization 3

So if we don't add two integers directly, but divide them by 2 and add them, will they not overflow?
private static int mean3(int x, int y) {
  return (x >> 1) + (y >> 1);
}
 
If implemented in this way, there will indeed be no overflow, but the accuracy is also lost.
java.lang.AssertionError: 
Expected :2147483647
Actual   :2147483646 
So is there a way to implement it that will not overflow, but can also support positive and negative integers at the same time?

The answer is more than one!

4-bit operation realization 1

Let's take a look at how Google's guava tool class is implemented
/**
 * IntMath#mean
 * @link https://github.com/google/guava/blob/master/guava/src/com/google/common/math/IntMath.java
 */
//   
private static int meanRoundDown(int x, int y) {
  return (x & y) + ((x ^ y) >> 1);
} 

We can understand the above code through collections.


For example, we find the average of the integers 9 and 3.

The binary of 9 is 1001, the binary of 3 is 0011,

Then the intersection of these two numbers is 9&3=0001,

The difference is 1010. 0001+(1010>>1) and the result is 6.


We all know that binary digits are a string of 0s and 1, so the integers x and y can be regarded as a set of many different 0s and 1s.


Then x & y means the intersection of two sets, because 1&1=1;

x ^ y gets the difference of the two sets, because 1^1=0,1^0=1;

The intersection and half of the difference is the binary average of the two numbers.


5-bit operation implementation 2

Let s take a look at the second way of implementing bitwise operations.
//   
private static int meanRoundUp(int x, int y) {
  return (x | y) - ((x ^ y) >> 1);
} 
How to understand this code?
What x | y gets is the deduplication union of the two sets.
By subtracting half of the difference from the union, the binary average of the two numbers is obtained.



6 The difference between the two methods

If the average of two integers is a decimal,
The first way is to round down;
The second way is to round up.
For example, if we find the average of the integers 9 and 4, the average of these two numbers should be 6.5, rounding up is 7, and down is 6.
Assert.assertEquals(6, meanRoundDown(9, 4)); //6
Assert.assertEquals(7, meanRoundUp(9, 4)); //7 


X digression

What I discussed above is just to find the average of two integers, so what are the implementations worth referring to for finding the average of multiple integers?

Similarly, let's take a look at how Google's guava tool class is implemented.

/**
   * Stats#meanOf
   * @link https://github.com/google/guava/blob/master/guava/src/com/google/common/math/Stats.java
   * 
   * Returns the <a href="http://en.wikipedia.org/wiki/Arithmetic_mean">arithmetic mean</a> of the
   * values. The count must be non-zero.
   *
   * <p>The definition of the mean is the same as {@link Stats#mean}.
   *
   * @param values a series of values
   * @throws IllegalArgumentException if the dataset is empty
   */
  public static double meanOf(int... values) {
    checkArgument(values.length > 0);
    double mean = values[0];
    for (int index = 1; index < values.length; index++) {
      double value = values[index];
      if (isFinite(value) && isFinite(mean)) {
        //Art of Computer Programming vol. 2, Knuth, 4.2.2, (15)
        mean += (value - mean)/(index + 1);
      } else {
        mean = calculateNewMeanNonFinite(mean, value);
      }
    }
    return mean;
  } 
Please note this comment:
Art of Computer Programming vol. 2, Knuth, 4.2.2, (15)

The realization of Guava is based on the classic work "The Art of Computer Programming" by Mr. Gartner. This set of books is planned to have 7 volumes, and 4 volumes have been published so far.

Bill Gates evaluation was: If you can finish this book, you definitely have to send me a resume.

End to sprinkle flowers.