Skip to content

Instantly share code, notes, and snippets.

@Robbepop
Created October 24, 2017 21:18
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save Robbepop/ff9bcbd530d90f26f504bb69f952177d to your computer and use it in GitHub Desktop.
How to replace multiplication by a constant with shift and add operations.
// Multiplication by a constant can be replaced by multiple shift and addition operations:
// The following table shows that for constants from 1 to 36.
//
// ============================================================================
// N | Factorized | # Ops | Ops with x as input
// ----------------------------------------------------------------------------
// 1 | 1 | 0 | x
// 2 | 2 | 1 | x << 1
// 3 | 2 + 1 | 2 | x << 1 + x
// 4 | 4 | 1 | x << 2
// 5 | 4 + 1 | 2 | x << 2 + x
// 6 | 4 + 2 | 3 | x << 2 + x << 1
// 7 | 4 + 2 + 1 | 4 | x << 2 + x << 1 + x
// 8 | 8 | 1 | x << 3
// 9 | 8 + 1 | 2 | x << 3 + x
// 10 | 8 + 2 | 3 | x << 3 + x << 1
// 11 | 8 + 2 + 1 | 4 | x << 3 + x << 1 + x
// 12 | 8 + 4 | 3 | x << 3 + x << 2
// 13 | 8 + 4 + 1 | 4 | x << 3 + x << 2 + x
// 14 | 8 + 4 + 2 | 5 | x << 3 + x << 2 + x << 1
// 15 | 8 + 4 + 2 + 1 | 6 | x << 3 + x << 2 + x << 1 + x
// 16 | 16 | 1 | x << 4
// 17 | 16 + 1 | 2 | x << 4 + x
// 18 | 16 + 2 | 3 | x << 4 + x << 1
// 19 | 16 + 2 + 1 | 4 | x << 4 + x << 1 + x
// 20 | 16 + 4 | 3 | x << 4 + x << 2
// 21 | 16 + 4 + 1 | 4 | x << 4 + x << 2 + x
// 22 | 16 + 4 + 2 | 5 | x << 4 + x << 2 + x << 1
// 23 | 16 + 4 + 2 + 1 | 6 | x << 4 + x << 2 + x << 1 + x
// 24 | 16 + 8 | 3 | x << 4 + x << 3
// 25 | 16 + 8 + 1 | 4 | x << 4 + x << 3 + x
// 26 | 16 + 8 + 2 | 5 | x << 4 + x << 3 + x << 1
// 27 | 16 + 8 + 2 + 1 | 6 | x << 4 + x << 3 + x << 1 + x
// 28 | 16 + 8 + 4 | 5 | x << 4 + x << 3 + x << 2
// 29 | 16 + 8 + 4 + 1 | 6 | x << 4 + x << 3 + x << 2 + x
// 30 | 16 + 8 + 4 + 2 | 7 | x << 4 + x << 3 + x << 2 + x << 1
// 31 | 16 + 8 + 4 + 2 + 1 | 8 | x << 4 + x << 3 + x << 2 + x << 1 + x
// 32 | 32 | 1 | x << 5
// 33 | 32 + 1 | 2 | x << 5 + x
// 34 | 32 + 2 | 3 | x << 5 + x << 1
// 35 | 32 + 2 + 1 | 4 | x << 5 + x << 1 + x
// 36 | 32 + 4 | 3 | x << 5 + x << 2
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment