Which algorithm is faster for checking if a bit is set?

Question

I am making a game in which I am storing a lot of data in one integer or long, because I will have a massive amount of data. I don't want to use whole classes for performance reasons, and they are not needed. I found two methods to retrieve one bit from an integer. I was wondering if anyone knows which one I should use or which one is faster.

The methods:

return (integer & (1 << bit)) != 0;

return (integer >> bit& 0x1) == 1;

Answer 1

Chances are the bit you're testing is "more constant" than the int you are testing against. Therefore, you can make constants for the bit, which means you only have to do the shift once. For instance:

static final int LEFT_WALL = 1 << 1;
static final int RIGHT_WALL = 1 << 2;
static final int BOTTOM_WALL = 1 << 3;
static final int TOP_WALL = 1 << 4;

Then in your loop, you're just checking

if ((integer & LEFT_WALL) != 0)
  // left wall collision
if ((integer & RIGHT_WALL) != 0)
  // right wall collision
...

So you're only doing two operations (bitwise AND and compare) in the loop, not three (shift, AND and compare).

And more importantly (as pointed out in the comments) than the speed gain, it also makes it much more clear what you're using each bit for, so the code is easier to read.

Answer 2

This is implementation dependent and depends on your hardware and compiler. Without actually running any time trials, I don't think anyone can say which will be better.

Moreover, I wouldn't worry about something like this unless you have tangible evidence that this code is so time-critical that you must optimize it. Spending time microoptimizing code like this is not likely to be productive unless you know it's a performance bottleneck, and I would be extremely surprised if you couldn't get even more bonus performance by optimizing other parts of the code. Try profiling the code to see what the real bottlenecks are, then go optimize those parts.

Answer 3

There's almost certainly no difference.

But the only way to be sure, for your platform, is to profile them both. You'll need to measure the time for a large number in a loop though (like 100e6), in order to minimise measurement error.