Wednesday, July 23, 2008

When bitmasking, do as the ...

int flags = 830;
if ( flags & mask == mask ) { doSomething(); }

If you're reading the value of bits from a bit-wise flags variable, please don't acquire your mask like this:
int mask = Math.pow(2, p);

Especially if you're doing this for every row in a table...

Instead, do this:
int mask = 1 << p;

Yay, bit shifting. --Saved a few billion operations...

Actually, I should add, a lot of the time you need a mask that is r-wide with 1's, shifted m to the left.
Example (for r = 7, m = 9, 32 bit int): 00000000 00000000 11111110 00000000

To achieve this, there is a simple algorithm that is brilliantly efficient. (~ is NOT operation, << is left shift operation)

1: int mask = ~0;
2: mask = mask << r;
3: mask = ~mask;
4: mask = mask << m;

This works as follows: (--Assuming system zero-fills on shift left; this is typical.)
Example: (r = 5, m = 12, 32-bit int)

1: mask = 11111111 11111111 11111111 11111111
2: mask = 11111111 11111111 11111111 11100000
3: mask = 00000000 00000000 00000000 00011111
4: mask = 00000000 00000001 11110000 00000000

Voila. As you can see, this is a 5-wide bit mask shifted 12 bits. This is equivalent to the mask number: 2^17 - 2^12 = 131072 - 4096 = 126976.

So, have fun with that. Make your code more efficient. =)
(Also, It seems blogger.com doesn't play well with angle brackets... I had to create this post in HTML.)

No comments: