Skip navigation

Its easy to forget all those neat tricks you learn about using bitwise arithmetic for cheap ways to compute practical things:

optimizations,they’re called. yes. or “fun”.

  • if( i & 1 ) // then i is odd Why: Say i is an odd number, like 5. Then in binary, i is 101. 101 & 1 is going to be this operation: 101 & 001 --- 001 So, 101&1 yields 1 (true) when i is odd. What about when i is even? Then the last bit is 0. Say i = 4 100 & 001 --- 000 So this tip takes advantage of the fact that for odd numbers, the last bit is always 1.
  • x >> 1 // divides x by 2 Why? Say i = 5 again. Then 101 >> 1 shifts to the right 1 bit. The last 1 is lost, and we end up with 102 Which is 210 which is (in base 10 math) 5 / 2 = 2 (integer division) take 410 1002 shift right 1 bit 102 which is 210 in base 10: 4 / 2 = 2 (integer division)
  • x << 1 // multiplies x by 2 Why: say x = 5. Then 101 << 1 shifts to the left 1 bit 1010 (a zero is inserted) which is 10102 == 1010 say we have 4: 100 << 1 shifts to the left 1 bit 1000 which is 8 in base 10

bitwise and modulus

to accomplish a modulus operation on a number of the form 2n, simply mask off the lowest n bits using a bitwise AND

x = y % 8;   ===    x = y & 7;

x = y % 32;   ===   x = y & 31;

x = y % 256;   ===   x = y & 255;

enums

Often times you see people creating enums like:

// C#
[Flags]
public enum Properties
{
  
  Heavy = 1,    // bit pattern  000001
  Blue  = 1 << 1,   // 0000010
  Orange = 1 << 2, // 0000100
  Smelly = 1 << 3, // 0001000
  Stinky = 1 << 4, // 0010000
  Fat = 1 << 5,    // 0100000
  Delicious = 1 << 6 // 1000000
  
}

So that they can create variables like:

Properties you = Properties.Fat | Properties.Heavy | Properties.Blue ;

So that you are Fat, and blue, and heavy. The bitwise OR operator is used to combine the flags. Pay attention to the fact that fields are powers of 2.

Now say you’re no longer blue – you’ve changed your color to orange. Then you can UNDO the Properties.Blue bit in one of 2 ways:

you ^= Properties.Blue ;

OR

you &= ~Properties.Blue ;

I MUCH PREFER the second way (using &). The reason is ^= is like a toggle. If the property is on, it switches it off, but if the property is already off, it switches it back on. &= ~(bitwise complement) switches the property off for sure.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: