11 ms·
The "SWAR" approach `(a & b) + (a ^ b) / 2` looks bizarre but can be understood. Adding two bits produces a sum and a carry: 0 + 0 = 0, carry 0 1 + 0
by ridiculous_fish 5y ago
The "SWAR" approach `(a & b) + (a ^ b) / 2` looks bizarre but can be understood.
Adding two bits produces a sum and a carry:
0 + 0 = 0, carry 0
1 + 0 = 1, carry 0
0 + 1 = 1, carry 0
1 + 1 = 0, carry 1
So the sum is XOR, and the carry is bitwise AND. We can rewrite x + y as (x ^ y) + (x & y)*2
Distribute the divide, and you get (x ^ y)/2 + (x & y) which is the mystery expression.
(Note this distribution is safe only because (x & y)*2 is even.)
- justinpombrio 5y agoAlternatively, a direct explanation: a & b is the bits they have in common. If they both have a bit x, you should keep it, because the average of x and x is x. a ^ b is the bits that only one of them have. You should halve these bits, because the average of x and 0 is x/2.
- ziml77 5y agoThis explanation makes a ton more sense!
- wildmanx 5y agoBut it has lots of assumptions/prerequisites about taking the mean baked-in. It happens to work for this particular case, but in general you don't get far with such hand-wavy reasoning since you just get confused with which assumptions hold and which don't. The original explanation was the actual SIMD approach, which is really cool. You can extend it right away to other problems.
- ggrrhh_ta 5y agoThe explanation seems to work even in base 10. Let's do the average of 85 and 95. The leftmost digit of both is equal, so we leave it: X5 The "xor"/2 is the sum of the non equal digits divided by 2 (respecting their powers): (8+9)10 = (17)10 = 85 Now, we add them: 5 + 85 = 90 (which is the average of 85 and 95). Let's take now 87 and 89: The rightmost digits are equal: 8X We do the 'xor'/2 for the left most: (7+9)/2 = 8 8X + 8 = 88 Let me know if there are some examples for which it would fail (I only spent a minute to test if the explanation extends to other bases).
- remram 5y agoThe average of 15 and 30 is not 22. The average of 51 and 03 is not 22.
- AnotherGoodName 5y agoSorry i'm confused and i asked elsewhere. How is the above SWAR? It looks like a regular set of instructions.
- deleted 5y ago[deleted]
- eru 5y agoWikipedia says: "It also refers to the use of SIMD with general-purpose registers and instructions that were not meant to do it at the time, by way of various novel software tricks." https://en.wikipedia.org/wiki/SWAR https://en.wikipedia.org/wiki/SWAR Maybe that's the way it's meant? Compilers might be smart enough to pick up the idiom used in the example and compile them to something done in parallel?
- rustybolt 5y agoIf you, for example, want to do addition of four 8-bit integers within a 32-bit register, you have to use similar techniques to stop the carry from propagating. For example, when x and y are 32-bit integers holding 4 8-bit integers, you can do z = (x ^ y) + (x & y) & 0x7f7f7f7f; Now z holds four 8-bit integers which hold the sum (modulo 256) of the integers of x and y. The bit mask is to stop the carry from propagating.
- sgtnoodle 5y agoThat's pretty neat. Is it actually any faster than just doing four 8-bit adds, though? Presumably it would take 4 logical instructions to do the vectored math, vs. 4 logical instructions to do the scalar additions. I suppose you're looking at a minimum of two registers for the vectored approach, vs. 8 for the scalar approach. Having the result available in separate registers makes them immediately available for use, though. There's also the overhead of getting the numbers in and out of memory. Loading and storing one word is obviously going to be way better than loading 4 bytes individually. It seems to me like the vectored approach would be better for algorithms that require iterating through a large dataset in memory. The scalar approach would be better for algorithms that have a bunch of dependent calculations. Perhaps that's an obvious conclusion! That's pretty neat though. For the large dataset scenario, perhaps you could get a significant speedup on relatively simple architectures such as cortex-m microcontrollers. I suspect that sufficiently modern high end CPUs/compilers wouldn't benefit so much from it, though? All the pipelining, superscaling and caching and whatnot could sufficiently mask the latencies of the memory accesses to the point of being irrelevant. Also, a sufficiently clever compiler could implement the loop with actual SIMD instructions and achieve significantly higher performance than the manual in-register optimization. This would be a fun way to compute a basic 8-bit checksum on a binary blob in a microcontroller... Not that it would be practically useful because any non-trivially sized blob would be better served with at least a Fletcher checksum if not a full CRC, both of which seemingly lack the necessary associativity.
- paulsmith 5y agoIt's a half-adder in software!
- dheera 5y agoWhy not just (a >> 1) + (b >> 1) + (a & 1) & (b & 1)
- dreamcompiler 5y agoThat's the "patented solution" referred to in the article.
- Dylan16807 5y ago"just"? That's 2 additions, 2 shifts, and 2-3 bitwise operations, while the other method is 1 addition, 1 shift, and 2 bitwise operations.
- rustybolt 5y agoI would think optimizing compilers can optimize this expression to the one in the article, but I tried it on godbolt and they don't.
- wildmanx 5y agoThanks for this explanation. What sets this post apart from the rest is that it actually provides useful information for everybody, after all those other posts of type "but that's obvious, I looked at it for 1 minute, saw half the solution, was too lazy for the rest and in hindsight it's all obvious. What a ridiculous patent system." Not to say that the patent system is problematic...