Binary Arithmetic and Shifts

Multiplication by a Power of 2

X * 2^n = X << n

Do this because it is must faster than multiplication. Multiplication is a very slow operation. Expect compiler to do this shift for you.

Example

3 * 4
3 * 2^2
0011 << 2
1100
12

Division by a Power of 2

X / 2^n = X >> n when X >= 0

Example

12 / 4
12 / 2^2
1100 >> 2
0011
3

Negative Values

Correct

(-17) * 4
1110 1111 * 2^2
1110 1111 << 2
1011 1110
-68

Incorrect

(-17) * 4
1110 1111 * 2^2
1110 1111 >> 2
1111 1011
-5

This truncates towards negative infinity, therefore it is incorrect.

Special Caveats

• C Standard 2011
  • When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded. This is often called "truncation toward zero".
  • The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a non-negative value, the value of the result is the integral part of the quotient of E1 / 2^E2. If E1 has a signed type and a negative value, the value of the result is the integral quotient of E1 / 2^E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.