How could I implement logical implication with bitwise or other efficient code in C?

c++ c performance logic algebra
alvatar picture alvatar · Mar 21, 2009 · Viewed 10.1k times · Source

I want to implement a logical operation that works as efficient as possible. I need this truth table:

p    q    p → q
T    T      T
T    F      F
F    T      T
F    F      T

This, according to wikipedia is called "logical implication"

I've been long trying to figure out how to make this with bitwise operations in C without using conditionals. Maybe someone has got some thoughts about it.

Thanks

Answer

Chris Dolan picture Chris Dolan · Mar 21, 2009 
~p | q

For visualization:

perl -e'printf "%x\n", (~0x1100 | 0x1010) & 0x1111'
1011

In tight code, this should be faster than "!p || q" because the latter has a branch, which might cause a stall in the CPU due to a branch prediction error. The bitwise version is deterministic and, as a bonus, can do 32 times as much work in a 32-bit integer than the boolean version!

Related questions

Static linking vs dynamic linking

Are there any compelling performance reasons to choose static linking over dynamic linking or vice versa in certain situations? I've heard or read the following, but I don't know enough on the subject to vouch for its veracity. 1) The difference …

Read More
Using scanf() in C++ programs is faster than using cin?

I don't know if this is true, but when I was reading FAQ on one of the problem providing sites, I found something, that poke my attention: Check your input/output methods. In C++, using cin and cout is too …

Read More
How can I measure CPU time and wall clock time on both Linux/Windows?

I mean: how can I measure time my CPU spent on function execution and wall clock time it takes to run my function? (Im interested in Linux/Windows and both x86 and x86_64). See what I want to do (Im …

Read More