Take the 2-minute tour ×

Using integer math alone, I'd like to "safely" average two unsigned ints in C++.

What I mean by "safely" is avoiding overflows (and anything else that can be thought of).

For instance, averaging 200 and 5000 is easy:

unsigned int a = 200;
unsigned int b = 5000;
unsigned int average = (a + b) / 2; // Equals: 2600 as intended

But in the case of 4294967295 and 5000 then:

unsigned int a = 4294967295;
unsigned int b = 5000;
unsigned int average = (a + b) / 2; // Equals: 2499 instead of 2147486147

The best I've come up with is:

unsigned int a = 4294967295;
unsigned int b = 5000;
unsigned int average = (a / 2) + (b / 2); // Equals: 2147486147 as expected

Are there better ways?

share|improve this question
The third option will give the wrong answer if both a and b are odd (since it will round down both halves). –  Jackson Pope Sep 28 '10 at 19:48
US patent number 6,007,232. Calculating the average of two integer numbers rounded towards zero in a single instruction cycle: google.com/patents?id=eAIYAAAAEBAJ&dq=6007232 essentially uses return (a >> 1) + (b >> 1) + (a & b & 0x1); –  Arun Sep 28 '10 at 20:01
...wow. I'm saving that link for the next time someone complains about software patents. –  Stephen Canon Sep 28 '10 at 20:23
it's interesting how many of the answers below contain this patented solution. I'm sure most/all of them developed it independently, perhaps even on the spot for their answer. That would seem to indicate the patent doesn't meet the standard of non-obviousness. –  rmeador Sep 28 '10 at 21:28
this is a hardware patent (notice that the result is produced in one clock cycle) –  pm100 Sep 28 '10 at 21:31

9 Answers 9

up vote 35 down vote accepted

Your last approach seems promising. You can improve on that by manually considering the lowest bits of a and b:

unsigned int average = (a / 2) + (b / 2) + (a & b & 1);

This gives the correct results in case both a and b are odd.

share|improve this answer
s/agerage/average/g –  Arun Sep 28 '10 at 19:57
Awesome, this is exactly the kind of consideration I was looking for. –  Tim Sep 28 '10 at 19:59
Speaking of software patents it appears that patent application: 20090249356 is trying to patent what is well known folklore in the computer industry. CAS-less single producer single consumer circular queues have been known for almost 30 years. (I wrote my first one in the early 80's) I wrote to complain but they said it was too late. I think the patent office should be inundated with "technical hate emails" on this one. –  nbourbaki Sep 29 '10 at 2:41
There's a slight problem with using this one: Samsung has a patent for it. google.com/patents?id=eAIYAAAAEBAJ&dq=6007232 –  folone Oct 4 '10 at 11:08
unsigned int average = low + ((high - low) / 2);


Here's a related article: http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

share|improve this answer
i like this, but what if there's an error due to integer division? –  ianmac45 Sep 28 '10 at 19:49
Why would there be? You're never dividing by 0, which is the only integer division that'd produce an error. –  cHao Sep 28 '10 at 19:51
This is the classic answer to this problem, especially when you already know which value is high and which is low - choosing a midpoint, for example. –  Mark Ransom Sep 28 '10 at 19:56
@ruslik: unless you know the ordering a priori, as in the linked article (which is probably the single most common use case for integer averaging). –  Stephen Canon Sep 28 '10 at 20:19
@ArunSaha: wrong! the original problem was about overflow. in this case you allow high - low to be signed, so this can easily overlow in the same way as in the original problem. you can avoid it only by considering this difference unsigned, so you have to know which one is larger. –  ruslik Sep 29 '10 at 1:42

Your method is not correct if both numbers are odd eg 5 and 7, average is 6 but your method #3 returns 5.

Try this:

average = (a>>1) + (b>>1) + (a & b & 1)

with math operators only:

average = a/2 + b/2 + (a%2) * (b%2)
share|improve this answer
You need to add some parentheses around your shifts; otherwise, what you get is: (a >> (1 + b) >> (1 + a)) & b & 1. (Your second example is correct, however). –  Stephen Canon Sep 28 '10 at 19:51
Fixed it, thanks :) –  iniju Sep 28 '10 at 19:54
+1 for shift instead of division. –  alxx Sep 28 '10 at 20:07
@alxx: any reasonable compiler will optimize division by two into a shift anyway. –  Stephen Canon Sep 28 '10 at 20:18
Upvoted for awesomeness! –  Tim Sep 29 '10 at 1:52

If you don't mind a little x86 inline assembly, you can do it in three instructions:

unsigned average(unsigned x, unsigned y)
    asm("mov 8(%ebp), %eax");
    asm("add 12(%ebp), %eax");
    asm("rcr %eax");
share|improve this answer
+1: I have never written inline assembly :(, can you please comment and explain the three lines, specially how the values of x and y are picked up. –  Arun Sep 28 '10 at 23:38
I'd also love to know how this works –  Tim Sep 29 '10 at 1:52
Reference: cse.nd.edu/~dthain/courses/cse40243/fall2008/ia32-intro.html (under "Defining Functions"). Also, the calling convention used is cdecl (the default for C and non-member C++ functions), which you might want to look up if you want more information. –  Josh Townzen Sep 29 '10 at 6:15
@Josh @Tomek: There is no such thing as an overflow in unsigned arithmetic, it is called a carry (hence the name carry flag). –  fredoverflow Sep 29 '10 at 11:38
This is not valid inline assembly because it does not code the operand dependency. A compiler might optimize it out or access bogus data when the function gets inlined. –  R.. Sep 7 '11 at 4:26

What you have is fine, with the minor detail that it will claim that the average of 3 and 3 is 2. I'm guessing that you don't want that; fortunately, there's an easy fix:

unsigned int average = a/2 + b/2 + (a & b & 1);

This just bumps the average back up in the case that both divisions were truncated.

share|improve this answer

And the correct answer is...

share|improve this answer
Does this one not have the patent problems as above? –  IdeaHat Jan 15 '14 at 15:43

Use a 64-bit unsigned int as the placeholder for the sum, cast back to int after dividing by 2. Questionable whether this is 'better', but you certainly avoid the overflow issue with minimal effort.

share|improve this answer
I'm doing this on an embedded micro with no 64bit registers ? –  Martin Beckett Sep 28 '10 at 19:54
@Martin - then you are out of luck with my suggestion, sorry –  Steve Townsend Sep 28 '10 at 20:56
I hope you don't suggest to do unsigned a = ..., b = ...; unsigned long long s = a + b; unsigned s2 = (unsigned)(s / 2);. Here a + b can still overflow despite s being large enough to hold the sum. –  Alexey Frunze Mar 12 '12 at 8:04
@Alex - can you provide examples values of a and b that would result in overflow here? I think I must be missing something. –  Steve Townsend Mar 12 '12 at 14:04
a = UINT_MAX and b = 1 will overflow in a + b before being assigned to s. s and s2 will be equal to 0. –  Alexey Frunze Mar 12 '12 at 15:56

If the code is for an embedded micro, and if speed is critical, assembly language may be helpful. On many microcontrollers, the result of the add would naturally go into the carry flag, and instructions exist to shift it back into a register. On an ARM, the average operation (source and dest. in registers) could be done in two instructions; any C-language equivalent would likely yield at least 5, and probably a fair bit more than that.

Incidentally, on machines with shorter word sizes, the differences can be even more substantial. On an 8-bit PIC-18 series, averaging two 32-bit numbers would take twelve instructions. Doing the shifts, add, and correction, would take 5 instructions for each shift, eight for the add, and eight for the correction, so 26 (not quite a 2.5x difference, but probably more significant in absolute terms).

share|improve this answer

(((a&b << 1) + (a^b)) >> 1) is also a nice way.

Courtesy: http://www.ragestorm.net/blogs/?p=29

share|improve this answer
This is wrong because there can be an overflow. Consider 8-bit ints and you want to find the average of 0xff and 0x01. It should be 0x80, right? Calculating: 0xff&0x01=0x01, 0x01<<1=0x02, 0xff^0x01=0xfe, 0x02+0xfe=0x00 (because ints are 8-bit, the 1 in 0x02+0xfe=0x100 is lost), 0x00>>1=0x00. 0x00!=0x80. –  Alexey Frunze Mar 12 '12 at 7:58
This is just wrong, not because of overflow. It will compute that the average of 3 and 7 is 8. It should be (a&b)+((a^b)>>1). –  Joni Oct 3 '13 at 8:26

Your Answer


