Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
3  
This question & your account name - the world makes sense again... –  Jonathan Khoo Apr 11 '11 at 4:28
    
+1 Interesting question as a follow up to mine and otherwise as well ;) –  Anto Apr 11 '11 at 5:08
    
I also did some fast parity calculations once. Parity is a bit of a pain because traditionally it involves loops and counting if a bit is set, all of which requires lots of jumps. Parity can be calculated using shift and XOR, then a bunch of those done one after another avoids the loops and jumps. –  quickly_now Apr 11 '11 at 7:19
2  
Are you aware that there's a whole book about these techniques? - Hackers Delight amazon.com/Hackers-Delight-Henry-S-Warren/dp/0201914654 –  nikie Apr 11 '11 at 7:51
    
Yeah, there's a web site devoted to bit operations as well. I forget the URL but google will turn it up soon enough. –  quickly_now Apr 11 '11 at 9:21
show 2 more comments

closed as not constructive by Thomas Owens Jan 14 '13 at 19:04

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance.If this question can be reworded to fit the rules in the help center, please edit the question.

4 Answers

up vote 23 down vote accepted

I love Gosper's hack (HAKMEM #175), a very cunning way of taking a number and getting the next number with the same number of bits set. It's useful, for example, in generating combinations of k items from n thusly:

int set = (1 << k) - 1;
int limit = (1 << n);
while (set < limit) {
    doStuff(set);

    // Gosper's hack:
    int c = set & -set;
    int r = set + c;
    set = (((r^set) >>> 2) / c) | r;
}
share|improve this answer
7  
+1. But from now on, I'll have nightmares about finding this one during a debugging session without the comment. –  nikie Apr 11 '11 at 7:49
    
@nikie, muahahahaha! (I tend to use this for things like Project Euler problems - my day job doesn't involve much combinatorics). –  Peter Taylor Apr 11 '11 at 8:56
add comment

The Fast inverse square root method uses the most bizarre bit-level techniques to computing the inverse of a square root that I've ever seen:

float Q_rsqrt( float number )
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;                       // evil floating point bit level hacking [sic]
    i  = 0x5f3759df - ( i >> 1 );               // what the fuck? [sic]
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
    //    y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

    return y;
}
share|improve this answer
    
Fast sqrt is also amazing. Carmack looks to be one of the greatest coder. –  Ubiquité Apr 11 '11 at 10:10
    
Wikipedia has even older sources, e.g. beyond3d.com/content/articles/15 –  MSalters Apr 12 '11 at 6:57
add comment

Division by 3 - without resorting to a run-time library call.

It turns out that division by 3 (thanks to a hint on Stack Overflow) can be approximated as:

X/3 = [ (x/4) + (x/12) ]

And X/12 is (x/4) / 3. There is an element of recursion suddenly appearing here.

It also turns out that if you limit the range of the numbers you are playing in, you can limit the number of iterations needed.

And thus, for unsigned integers < 2000, the following is a fast and simple /3 algorithm. (For bigger numbers, just add more steps). Compilers optimise the heck out of this so it ends up being fast and small:

static unsigned short FastDivide3(const unsigned short arg)
{
  unsigned short RunningSum;
  unsigned short FractionalTwelth;

  RunningSum = arg >> 2;

  FractionalTwelth = RunningSum >> 2;
  RunningSum += FractionalTwelth;

  FractionalTwelth >>= 2;
  RunningSum += FractionalTwelth;

  FractionalTwelth >>= 2;
  RunningSum += FractionalTwelth;

  FractionalTwelth >>= 2;
  RunningSum += FractionalTwelth;

  // More repeats of the above 2 lines for more precision

  return RunningSum;
}
share|improve this answer
1  
Of course, this is only relevant on very obscure microcontrollers. Any real CPU made in the last two decades doesn't need a run-time library for integer division. –  MSalters Apr 11 '11 at 7:59
1  
Oh sure, but small micros without a hardware multiplier are actually very common. And if you work in embedded land and want to save $0.10 on each of a million products sold then you better know some dirty tricks. That money saved = extra profit which makes your boss very happy. –  quickly_now Apr 11 '11 at 9:19
    
Well, dirty... it's just multiplying by .0101010101 (approx. 1/3). Pro tip: you can also multiply by .000100010001 and 101 (which takes just 3 bitshifts, yet has the better approximation .010101010101 –  MSalters Apr 11 '11 at 9:34
    
How might I do that with only integers and no floating point? –  quickly_now Apr 11 '11 at 23:10
1  
Bitwise, x*101 = x + x << 2. Similarly, x * 0.000100010001 is x >> 4 + x >> 8 + x >> 12. –  MSalters Apr 12 '11 at 6:52
show 2 more comments

If you look in Erlang there is an entire DSL for doing bit operations. SO you can just break up a datastructure by bits by saying something like this:

<> = <<1,17,42:16>>.

Full details here: http://www.erlang.org/doc/reference_manual/expressions.html#id75782

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.