views:

234

answers:

5

I have five colors stored in the format #AARRGGBB as unsigned ints, and I need to take the average of all five. Obviously I can't simply divide each int by five and just add them, and the only way I thought of so far is to bitmask them, do each channel separately, and then OR them together again. Is there a clever or concise way of averaging all five of them?

A: 

EDIT I'll leave this attempt for posterity, but please note that it is incorrect and will not work.

One "clever" way you could do it would be to insert zeros between the components, parse into an unsigned long, average the numbers, convert back to a hex string, remove the zeros and finally parse into an unsigned int.

i.e. convert #AARRGGBB to #AA00RR00GG00BB

This method involves parsing and string manipulations, so will undoubtedly be slower than the method you proposed.

If you were to factor your own solution carefully, it might actually look quite clever itself.

Patrick McDonald
I'm pretty certain that wouldn't work. Consider four blacks (#0..0) and a red (#00010000). Add and divide by five, and the remainder from the red (1/5) will spill into both green and blue fields.
chrispy
oops, you're right
Patrick McDonald
+2  A: 

Half way between your (OP) proposed solution and Patrick's solution looks quite neat:

Color colors[5]={ 0xAARRGGBB,...};

unsigned long sum1=0,sum2=0;
for (int i=0;i<5;i++)
{
  sum1+= colors[i]    &0x00FF00FF; // 0x00RR00BB
  sum2+=(colors[i]>>8)&0x00FF00FF; // 0x00AA00GG
}
unsigned long output=0;
output|=(((sum1&0xFFFF)/5)&0xFF);
output|=(((sum2&0xFFFF)/5)&0xFF)<<8;
sum1>>=16;sum2>>=16; // and now the top halves
output|=(((sum1&0xFFFF)/5)&0xFF)<<16;
output|=(((sum2&0xFFFF)/5)&0xFF)<<24;

I don't think you could really divide sum1/sum2 by 5, because the bits from the top half would spill down...

If an approximation would be valid, you could try a multiplication by something like, 0.1875 (0.125+0.0625), (this means: multiply by 3 and shift down by 4 places. This you could do with bitmasking and care.) The problem is, 0.2 has a crappy binary representation, so multiplying by it is an ass.

As ever, accuracy or speed. Your choice.

Dave Gamble
+2  A: 

When using x86 machines with at least SSE, and if you need to approximate only, you could use the assembly instruction PAVGB (Packed Average Byte), which averages bytes. See http://www.tommesani.com/SSEPrimer.html for explanation.

Since you've got 5 values, you would need to be creative in calling PAVGB, since PAVGB will only do two values at a time.

Rutger Nijlunsing
A: 

How about a pixel shader to do the work on the GPU?

fortran
+1  A: 

I found smart solution of your problem, sadly it is only applicable if number of colors is power of 2. I'll show it in case of two colors:

mask = 01010101

pom = ~(a^b & mask) # ^ means xor here, ~ negation

a = a & pom
b = b & pom

avg = (a+b) >> 1

The trick of this method is — when you count average, LSB of sum (in case of two numbers) has no meaning, as it will be dropped in division (we're talking integers here, of course). In your problem, LSB of partial sums is at the same moment carry bit of sum of adjacent color. Provided, that LSB of every color sum will be 0 you can safely add those two integers — additions won't interfere with each other. Bit shift divides every color by two.

This method can be used with 4 colors as well, but you have to implement finding out the carry flag of sum of numbers made of two last bits of every color. It is also possible to omit this part and just zero last two bits of every color — biggest mistake made with this omission is 1 for every component.

samuil