Curiosities I: Performance, Maths and powers of 2

While programming we usually use the math operators. But if we are using a power of 2 as divider or multiplicand you can use bitwise operatos to speed up the operations.

Multiplication

In the multiplication, you can use the bitwise left shift operator (<<) to "add" n trailing zeroes, where n is the exponent of the power of 2. For example, if we use 8 (2 ^ 3):

500 *  8 -> 4000

500 << 3 -> 4000 /* 8 is 2 to the power of 3 */

This is the same as:

0001 1111 0100 (500) << 3 

    -> 1111 1010 0000 (4000) /* added 3 trailing zeroes */

Division

When dividing, you should use the right shift operator (yes, it's obvious):

4000 /  8 -> 500
4000 >> 3 -> 500 /* 8 is 2 to the power of 3 */

Same as:

1111 1010 0000 (4000) >> 3 
    -> 0001 1111 0100 (500) /* removed 3 trailing zeroes */

Modulo

This works with the modulus operator too, but using the bitwise AND operator and divider-1. With 8 and 7 (8 - 1):

4001 / 8 -> 1
4001 & 7 -> 1 /* 8 - 1 = 7 */

Same as:

  1111 1010 0001 (4001)
&           0111    (7)
----------------
  0000 0000 0001    (1)

Why do you want to know this?

Because bitwise operation are usually faster than other. In C#, Java or Python it could be up to 100% faster. Normally you wont apreciate it, as you need thousand / million operations to notice it, but when you have a very big server, you need to save all the cycles you can.

Note: Care with negative numbers!