Take the 2-minute tour ×

I need to perform a bitwise equality between two bytes. That means that for instance if I have two bytes: 00011011 and 00011110 the result is 11111010 The only fast way I see is to use the following statement

byte a, b;//set input bytes
byte c = ~(a^b);//output bytes

But I wonder if there is a faster solution for this. After these equality operation I want to mask the bits I need. So I need to use an AND-operation. So the code becomes:

byte a, b;//set input bytes
byte m;//mask, intresting bits are set to 1, others to 0
byte c = (~(a^b))&m;//output bytes

aren't there any faster and more simple methods that don't need to use all those bitwise operations because this part of the code will be called very often.

share|improve this question
I work in Mono/C#.Net, but the syntax of any language in the C-family is equivalent I think, it's not that important. –  CommuSoft Feb 4 '10 at 15:32
faster than bitwise operations? surely you jest? –  Mitch Wheat Feb 4 '10 at 15:32
Wait. You want something "faster" than two bitwise operations, two operations which directly implement the semantics you describe? Huh? –  Jonathan Feinberg Feb 4 '10 at 15:32
Why do you think your language's operator == isn't good enough? –  Ivan Krechetov Feb 4 '10 at 15:33
Bitwise operations like this are typically very, very fast - what evidence do you have that you need to optimise them? –  anon Feb 4 '10 at 15:34

4 Answers 4

up vote 6 down vote accepted

I doubt it can be done in fewer operations. That looks optimal. Perhaps you could store ~(a^b) in a lookup table (256*256 entries)? I doubt you would get much benefit and possibly even make things worse, but you could try it.

share|improve this answer
Did you benchmark that? Theoretically ~(a^b) could be faster it probably executes in two cycles and pipelines well, an index lookup to memory can be expected to take several cycles. –  user159335 Feb 4 '10 at 15:42
The OP should note that the operations the compiler will perform to index the table are likely to be at least as expensive (probably more) as the operations to calculate the result directly. And that doesn't take into account the additional memory access. –  Michael Burr Feb 4 '10 at 15:49
Cache-misses are 2 magnitudes slower than arithmetic ops. –  Viktor Klang Feb 4 '10 at 15:53
When the lookup table and actual input byte array fit in the same cache line, this operation should be pretty quick. However, I expect a ~(a^b) to be as fast (and it's perhaps even optimized by the JIT compiler). –  Steven Feb 4 '10 at 15:55

You are looking in the wrong place for this optimization; you won't end up finding any better bitwise operation here. Even if you did, it's hardly going to speed anything up. The real win will come from processing more than just a byte at a time. The processor is already having to do a bunch of bit shifting and masking operations just so that it can pretend for you that you are working with bytes. Process your arrays of bytes 1 word at a time, or use vector instructions if they are available.

share|improve this answer

These operations seem fast enough to be honest. I think you shouldn't try to optimize them further, but finish your software first, see if you are happy with the overall performance and use a profiler if you are not. I am fairly sure the problem will be elsewhere.

share|improve this answer

What you want is an XNOR operation. Unfortunately this is not supported by C#/Mono. I think your solution is optimal.

share|improve this answer
I wouldn't be surprised if the MS JIT compiler is able to optimize a ~(a^b) to an XNOR. CommuSoft should look at the generated assembly code to see if that's the case. –  Steven Feb 4 '10 at 15:53
That's a good thought. I would be curious to see if that was optimized as well. –  Michael Krauklis Feb 4 '10 at 16:13
I opened the Debug/Windows/Disassembly window in VS2008 to see what assembly gets generated and I see an XOR statement and a NOT statement. This would mean it is not optimized. However, we're talking about just 2 assembly instructions: this is blazingly fast. –  Steven Feb 4 '10 at 16:27
That's too bad. Thanks for looking into it. –  Michael Krauklis Feb 4 '10 at 16:50

Your Answer


