A few days ago, StackExchange member Anto inquired about valid uses for bit-wise operators. I stated that shifting was faster than multiplying and dividing integers by powers of two. StackExchange member Daemin countered by stating that right-shifting presented problems with negative numbers.
At that point, I had never really thought about using the shift operators with signed integers. I primarily used this technique in low-level software development; therefore, I always used unsigned integers. C performs logical shifts on unsigned integers. No attention is paid to the sign bit when performing a logical shift right. Vacated bits are filled with zeros. However, C performs an arithmetic shift operation when shifting a signed integer right. Vacated bits are filled with the sign bit. This difference causes a negative value to be rounded toward infinity instead of being truncated toward zero, which is a different behavior than signed integer division.
A few minutes of thought resulted in a first-order solution. The solution conditionally converts negative values to positive values before shifting. A value is conditionally converted back to its negative form after the shift operation has been performed.
int a = -5; int n = 1; int negative = q < 0; a = negative ? -a : a; a >>= n; a = negative ? -a : a;
The problem with this solution is that conditional assignment statements are usually translated to at least one jump instruction, and jump instructions can be expensive on processors that do not decode both instruction paths. Having to re-prime an instruction pipeline twice makes a good dent in any performance gain obtained by shifting over dividing.
With the above said, I woke up on Saturday with the answer to the conditional assignment problem. The rounding problem that we experience when performing an arithmetic shift operation only occurs when working with two's complement representation. It does not occur with one's complement representation. The solution to the problem involves converting a two's complement value to a one's complement value before performing the shift operation. We then have to convert the one's complement value back to a two's complement value. Surprisingly, we can perform this set of operations without conditionally converting negative values before performing the shift operation.
int a = -5; int n = 1; register int sign = (a >> INT_SIZE_MINUS_1) & 1 a = (a - sign) >> n + sign;
A two's complement negative value is converted to a one's complement negative value by subtracting one. On the flip side, a one's complement negative value is converted to a two's complement negative value by adding one. The code listed above works because the sign bit is used to convert from two's complement to one's complement and vice versa. Only negative values will have their sign bits set; therefore, the variable sign will equal zero when a is positive.
With the above said, can you think of other bit-wise hacks like the one above that have made it into your bag of tricks? What is your favorite bit-wise hack? I am always looking for new performance-oriented bit-wise hacks.