coder . cl

Certainly, bitwise operations are the faster operations that a processor can give us, and comparison operations are in the fact more slow than bitwise operations. If we don’t have access to compiler optimizations, other than GCC or ICC, we can use our own minimizations to gain performance.

some patterns

classical zero negation

On some programs we find a common minimization, the zero negation to test if a variable is zero.

/* comparing code */
if (z == 0) {
    /* some task */
}

/* bitwise code */
if ((bool)!z) {
    /* some task */
}

bitwise or to zero

If we must check many values compared to zero, we can gain performance by using the bitwise or operator to mix the bits on the numbers that we need to compare. We reduce the number of comparing operations from n to two.

/* long code */
if (val1 == 0
    && val2 == 0
    && val3 == 0
    && val4 == 0) {
    /* some task */
}
/* short code */
if ((val1 | val2 | val3 | val4) == 0) {
    /* some task */
}

bitwise and not equal to zero

If we must check many values compared not equal to zero, we can gain performance by using the bitwise and operator to mix the bits on the numbers that we need to compare. We reduce the number of comparing operations from n to two.

/* long code */
if (val1 != 0
    && val2 != 0
    && val3 != 0
    && val4 != 0) {
    /* some task */
}

/* short code */
if ((val1 & val2 & val3 & val4) != 0) {
    /* some task */
}

bitwise xor wizardly

/* the long code 1 */
if ((x == 1 && y == 0) ||
    (x == 0 && y == 1)) {
    /* some task */
}

/* the short code 1 */
if ((bool)(x ^ y)) {
    /* some task */
}

In other special cases, where we are sure on the expression that we are evaluating, we can find, by understanding the bitwise xor operator, some lazy evaluations can be made on.

/* long code 2 */
if ((true_expr1_result && !false_expr2_result) ||
    (!false_expr1_result && true_expr2_result)) {
    /* some task */
}

/* short code 2 */
if ((bool)(expr1_result ^ expr2_result)) {
    /* some task */
}

next and previous odd/even values

The classical O(n) way to search for the next or previous even or odd value of a number can be programmed as follows.

/* similar to this example for even values,
   use == 0 for odd values, and I know, isn't
   working, but just an idea... */
x = ++n;
while ((x % 2) != 0) {
    x++;
}
return x;

Through a mathematical minimization found in the book of Jörg Arndt, we can find a faster — I think a O(log(n)) algorithm — to calculate these values.

/* next even */
int neven = x + 2 - (x & 1);

/* previous even */
int peven = x - 2 + (x & 1);

/* next odd */
int nodd = x + 1 + (x & 1);

/* previous odd */
int podd = x - 1 - (x & 1);

how important are these minimizations

Performance improvement and reduced compile time should be a must on certain conditions, usually high performance computing, device drivers or other kind of software development that requires a well designed and fast algorithm. An optimizing compiler isn’t available every time we work on different platform, and know how to improve our code through certain minimizations can help in our development tasks.

Code readability it’s important too, but you have comments, where these comments can help when you have minimized some expression. Also, when a compiler provides enough optimization facilities, we can omit many of these optimizations, because are made by the compiler.

Now you can contribute with your own ;)

Thanks to Felipe Astroza for commenting this article.