두 정수의 평균을 구하는 가장 좋은 방법은 무엇일까요?

물론, 프로그래밍 언어에서 계산하는 경우를 말합니다.

사실
http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
이 글을 읽다가 문득 궁금해진 내용입니다.
양수, 음수 포함하여 모든 정수를 고려할 때, 어떤 방법이 가장 좋을까요?
아래 나열한 방법은 전부 위의 링크에서 가져와서, 제 생각을 덧붙인 것입니다.

가장 무식한 방법은
mid = (low + high) / 2;
입니다.
그런데 이 방법은 overflow의 문제가 있습니다.

그 다음 방법은
mid = low + (high - low) / 2;
입니다.
이 방법은 0 <= low <= high일 때는 잘 작동하지만,
high = 0, low = 1이 되면 (-1) / 2가 계산되면서 문제가 되고,
high = 0, low = INT_MIN이 되면 overflow가 발생합니다.

또 다른 방법은
mid = (((unsigned int) low) + ((unsigned int) high)) / 2;
입니다.
그런데, 이 방법도 문제가 있습니다.
원래 low, high가 음수였을 경우엔 오답이 나옵니다.
그리고 양수로 한정하더라도 INT_MAX * 2 <= UINT_MAX가 보장이 되는지는 의문입니다. (임의의 언어, 임의의 환경을 고려할 때 말입니다.)

또 다른 방법은
mid = (low / 2) + (high / 2) + (((low % 2) + (high % 2)) / 2);
입니다.
아마, X == ((X / 2) * 2) + (X % 2) for all X 정도의 조건이 필요한데, (아마도) 요새 언어에서 대부분 이 조건은 만족하니까 상관 없습니다.
그외에 필요한 조건은 발견하지 못했습니다.
다만, 연산의 수가 너무 많아서 사용하고 싶은 마음이 안 듭니다.
(이론적으로 /와 %는 연산 한 번에 될 듯 싶지만, 그런 명령어가 있는지 모르겠습니다. 그래서 연산이 많습니다.)

또 다른 방법은
mid = (low / 2) + (high / 2) + (low & high & 1);
입니다.
바로 위의 방법과 비슷한 접근입니다.
고민해본 결과, (-3) / 2를 -1로 계산하는 C에서는 오답이 나옵니다. (-3) / 2를 -2로 계산하면 (아마도) 언제나 정답인 것 같습니다.
gcc는 >>를 arithmetic shift로 계산하므로 써 먹을 수 있을 것 같습니다.

또 다른 방법은
mid = (low & high) + (low ^ high) / 2;
입니다.
이건 아무리 생각해도 항상 정답이 나오는 것 같습니다.
(-3) / 2를 -2로 계산하든 -1로 계산하든 상관 없습니다.
(low ^ high)가 음수이고 평균값이 정수가 아닐 때, 정확히 중간에서 0.5만큼 왼쪽을 찍냐 오른쪽을 찍냐 차이입니다.
게다가 정답을 보장하는 방식 중 비교적 연산 횟수도 적어 보입니다.
(코멘트가 없으면 이해하기 어렵다는 것이 단점일까요.)

과연 더 좋은 방법이 있을까요?
마지막 방법은 좋은 코드일까요? 정말 모든 경우에 동작한다고 확신할 수 있을까요?