Finding the Average of Two Numbers Using Bitwise Operations

Table of Contents#

Introduction
Basics of Bitwise Operations
The Problem: Averaging Two Integers
Naive Approach and Its Shortcomings
Bitwise Approach: Avoiding Overflow
Step-by-Step Explanation with Examples
Best Practices and Common Pitfalls
Performance Considerations
Example Usage in Code
Conclusion
References

Basics of Bitwise Operations#

Bitwise operations manipulate individual bits of a number. Key operations for our use case:

Right Shift (>>): Shifts bits to the right. For positive integers, x >> 1 is equivalent to integer division by 2 (e.g., 5 >> 1 = 2). For negative integers (two’s complement), it performs an arithmetic shift (preserves the sign bit).
Bitwise AND (&): Returns 1 for a bit position if both operands have 1; else 0 (e.g., 5 & 3 = 1 (binary 101 & 011 = 001)).

The Problem: Averaging Two Integers#

Given two integers a and b, compute their average:
$$\text{average} = \frac{a + b}{2}$$

For example:

If ( a = 3 ) and ( b = 5 ), the average is ( \frac{3 + 5}{2} = 4 ).
If ( a = -3 ) and ( b = -5 ), the average is ( \frac{-3 + (-5)}{2} = -4 ).

Naive Approach and Its Shortcomings#

The most straightforward approach is:

int average_naive(int a, int b) {
    return (a + b) / 2;
}

Issues:#

Overflow: For large values (e.g., 32-bit signed integers with ( a = 2^{31} - 1 ) and ( b = 2^{31} - 1 )), ( a + b ) overflows (wraps to a negative value in two’s complement).
- Example: ( a = 2147483647 ) (max 32-bit signed int), ( b = 2147483647 ).
- ( a + b = 4294967294 ), which overflows to ( -2 ) (in 32-bit two’s complement).
- ( (a + b) / 2 = -1 ) (incorrect; the correct average is ( 2147483647 )).
Slow Division: The division operator (/) is slower than bitwise operations, especially in performance-critical code.

Bitwise Approach: Avoiding Overflow#

To avoid overflow, we derive a formula using bitwise operations:

Derivation:#

Let ( a = 2a' + x ) and ( b = 2b' + y ), where ( x, y \in {0, 1} ) (the least significant bits, or parity of ( a ) and ( b )).

( a + b = 2(a' + b') + x + y )
The average is ( \frac{a + b}{2} = (a' + b') + \frac{x + y}{2} ).

Now, ( x ) and ( y ) are 0 (even) or 1 (odd). The term ( \frac{x + y}{2} ) is:

( 0 ) if ( x + y = 0 ) (both even) or ( 1 ) (one even, one odd).
( 1 ) if ( x + y = 2 ) (both odd).

Thus, ( \frac{x + y}{2} = x & y ) (since ( x & y = 1 ) only when ( x = 1 ) and ( y = 1 )).

The Formula (Unsigned Integers):#

$$\text{average} = (a & b) + ((a \oplus b) \gg 1)$$

( (a & b) ) captures the common bits (carries from addition).
( (a \oplus b) \gg 1 ) computes half of the sum of bits where ( a ) and ( b ) differ.
Adding these two components gives the average without overflow.

The Formula (Signed Integers, Same Sign):#

For signed integers with the same sign, the following formula works correctly when a and b have the same parity (both even or both odd, i.e., a + b is even): $$\text{average} = (a \gg 1) + (b \gg 1) + ((a & 1) & (b & 1))$$

( a \gg 1 ) is ( a' ) (arithmetic right shift, floor division by 2).
( b \gg 1 ) is ( b' ) (arithmetic right shift, floor division by 2).
( (a & 1) & (b & 1) ) checks if both ( a ) and ( b ) are odd (adds 1 if true).

For a robust solution that works for all same-sign integers without parity restrictions, cast to unsigned, compute, then cast back: $$\text{average} = (int)((unsigned)(a & b) + ((unsigned)(a \oplus b) \gg 1))$$

Note: When ( a ) and ( b ) have opposite signs, arithmetic right shift (floor) and integer division by 2 (truncation toward zero) differ, causing incorrect results. For mixed-sign integers, use the unsigned formula after casting to unsigned types, or handle sign separately.

Step-by-Step Explanation with Examples#

Let’s verify the formula with examples:

Example 1: ( a = 3 ) (binary `11`), ( b = 5 ) (binary `101`)#

( a \gg 1 = 1 ) (binary 1), ( b \gg 1 = 2 ) (binary 10).
( (a & 1) = 1 ), ( (b & 1) = 1 ) → ( (a & 1) & (b & 1) = 1 ).
Average: ( 1 + 2 + 1 = 4 ) (correct: ( \frac{3 + 5}{2} = 4 )).

Example 2: ( a = 2147483647 ) (max 32-bit signed int), ( b = 2147483647 )#

( a \gg 1 = 1073741823 ), ( b \gg 1 = 1073741823 ).
( (a & 1) = 1 ), ( (b & 1) = 1 ) → ( (a & 1) & (b & 1) = 1 ).
Average: ( 1073741823 + 1073741823 + 1 = 2147483647 ) (correct, avoids overflow).

Example 3: ( a = 2147483647 ) (max 32-bit signed int), ( b = 2147483647 )#

( a \gg 1 = 1073741823 ), ( b \gg 1 = 1073741823 ).
( (a & 1) = 1 ), ( (b & 1) = 1 ) → ( (a & 1) & (b & 1) = 1 ).
Average: ( 1073741823 + 1073741823 + 1 = 2147483647 ) (correct, avoids overflow).

Example 4: ( a = -3 ) (binary `11111101`), ( b = -5 ) (binary `11111011`)#

( a \gg 1 = -2 ) (arithmetic shift: 11111101 >> 1 = 11111110 → -2).
( b \gg 1 = -3 ) (arithmetic shift: 11111011 >> 1 = 11111101 → -3).
( (a & 1) = 1 ), ( (b & 1) = 1 ) → ( (a & 1) & (b & 1) = 1 ).
Average: ( -2 + (-3) + 1 = -4 ) (correct: ( \frac{-3 + (-5)}{2} = -4 )).

Example 5: ( a = -3 ) (binary `11111101`), ( b = -4 ) (binary `11111100`)#

Both negative and have opposite parity (a is odd, b is even).
( a \gg 1 = -2 ), ( b \gg 1 = -2 ).
( (a & 1) = 1 ), ( (b & 1) = 0 ) → ( (a & 1) & (b & 1) = 0 ).
Formula result: ( -2 + (-2) + 0 = -4 ).
Correct average: ( \frac{-3 + (-4)}{2} = \frac{-7}{2} = -3.5 ), truncated to ( -3 ).
Issue: The formula gives -4 because the parity mismatch causes an off-by-one error. This demonstrates why the formula requires a and b to have the same parity (or use the unsigned conversion method for robust same-sign handling).

Example 6: ( a = 1 ) (binary `00000001`), ( b = -2 ) (binary `11111110`)#

( a \gg 1 = 0 ), ( b \gg 1 = -1 ) (arithmetic shift: 11111110 >> 1 = 11111111 → -1).
( (a & 1) = 1 ), ( (b & 1) = 0 ) → ( (a & 1) & (b & 1) = 0 ).
Formula result: ( 0 + (-1) + 0 = -1 ).
Correct average: ( \frac{1 + (-2)}{2} = \frac{-1}{2} = -0.5 ), which truncates toward zero to ( 0 ).
Issue: The formula gives -1 because arithmetic right shift floors -1.5 to -2, while integer division truncates toward zero. This demonstrates why the formula only works reliably for same-sign or unsigned integers.

Best Practices and Common Pitfalls#

Best Practices:#

Use the bitwise formula for performance-critical code (e.g., embedded systems, real-time applications) where division and overflow are costly.
Test edge cases (min/max integers, negative numbers, mixed parity).

Common Pitfalls:#

Signed vs Unsigned Shifts: In languages like C, use signed integers for arithmetic shifts (preserves sign for negative numbers).
Parity Mistakes: Ensure the “odd check” ((a & 1) & (b & 1)) is correct (adds 1 only if both are odd).

Performance Considerations#

Bitwise operations (shifts, AND) are faster than arithmetic operations (addition with overflow checks, division):

A right shift (>> 1) takes 1 clock cycle (on most CPUs).
Division (/ 2) can take 10+ cycles (varies by CPU).

Example Usage in Code#

Here’s the bitwise average function in C:

int average_bitwise(int a, int b) {
    // For unsigned integers or same-sign signed integers:
    // return (a & b) + ((a ^ b) >> 1);
    // For signed integers with same sign only:
    // return (a >> 1) + (b >> 1) + ((a & 1) & (b & 1));
    return (a >> 1) + (b >> 1) + ((a & 1) & (b & 1));
}

Testing:#

#include <stdio.h>
 
int main() {
    // Test case 1: Small positive numbers
    printf("Average of 3 and 5: %d\n", average_bitwise(3, 5)); // Output: 4
 
    // Test case 2: Large positive numbers (32-bit max)
    int a = 2147483647, b = 2147483647;
    printf("Average of %d and %d: %d\n", a, b, average_bitwise(a, b)); // Output: 2147483647
 
    // Test case 3: Negative numbers
    printf("Average of -3 and -5: %d\n", average_bitwise(-3, -5)); // Output: -4
 
    return 0;
}

Conclusion#

Using bitwise operations to compute the average of two integers avoids overflow and improves performance. The formula ( (a \gg 1) + (b \gg 1) + ((a & 1) & (b & 1)) ) splits the problem into safe, fast operations. This method is ideal for low-level programming, embedded systems, or any scenario where speed and overflow safety are critical.