title: Why does division by 3 require a rightshift (and other oddities) on x86?
body: <p>I have the following C/C++ function:</p>
  <pre class="lang-cpp prettyprint-override"><code>unsigned div3(unsigned x) {
      return x / 3;
  }
  </code></pre>
  <p><a href="https://godbolt.org/z/7Y8Ebf" rel="noreferrer">When compiled using clang 10</a> at <code>-O3</code>, this results in:</p>
  <pre><code>div3(unsigned int):
          mov     ecx, edi         # tmp = x
          mov     eax, 2863311531  # result = 3^-1
          imul    rax, rcx         # result *= tmp
          shr     rax, 33          # result &gt;&gt;= 33
          ret
  </code></pre>
  <p>What I do understand is: division by 3 is equivalent to multiplying with the multiplicative inverse 3<sup>-1</sup> mod 2<sup>32</sup> which is 2863311531.</p>
  <p>There are some things that I don't understand though:</p>
  <ol>
  <li>Why do we need to use <code>ecx</code>/<code>rcx</code> at all? Can't we multiply <code>rax</code> with <code>edi</code> directly?</li>
  <li>Why do we multiply in 64-bit mode? Wouldn't it be faster to multiply <code>eax</code> and <code>ecx</code>?</li>
  <li>Why are we using <code>imul</code> instead of <code>mul</code>? I thought modular arithmetic would be all unsigned.</li>
  <li>What's up with the 33-bit rightshift at the end? I thought we can just drop the highest 32-bits.</li>
  </ol>
  <h3>Edit 1</h3>
  <p>For those who don't understand what I mean by 3<sup>-1</sup> mod 2<sup>32</sup>, I am talking about the multiplicative inverse here.
  For example:</p>
  <pre class="lang-c prettyprint-override"><code>// multiplying with inverse of 3:
  15 * 2863311531      = 42949672965
  42949672965 mod 2^32 = 5
  
  // using fixed-point multiplication
  15 * 2863311531      = 42949672965
  42949672965 &gt;&gt; 33    = 5
  
  // simply dividing by 3
  15 / 3               = 5
  </code></pre>
  <p>So multiplying with 42949672965 is actually equivalent to dividing by 3. I assumed clang's optimization is based on modular arithmetic, when it's really based on fixed point arithmetic.</p>
  <h3>Edit 2</h3>
  <p>I have now realized that the multiplicative inverse can only be used for divisions without a remainder. For example, multiplying 1 times 3<sup>-1</sup> is equal to 3<sup>-1</sup>, not zero. Only fixed point arithmetic has correct rounding.</p>
  <p>Unfortunately, clang does not make any use of modular arithmetic which would just be a single <code>imul</code> instruction in this case, even when it could. The following function has the same compile output as above.</p>
  <pre class="lang-cpp prettyprint-override"><code>unsigned div3(unsigned x) {
      __builtin_assume(x % 3 == 0);
      return x / 3;
  }
  </code></pre>
  <hr />
  <p>(Canonical Q&amp;A about fixed-point multiplicative inverses for exact division that work for every possible input: <a href="https://stackoverflow.com/questions/41183935/why-does-gcc-use-multiplication-by-a-strange-number-in-implementing-integer-divi">Why does GCC use multiplication by a strange number in implementing integer division?</a> - not quite a duplicate because it only covers the math, not some of the implementation details like register width and imul vs. mul.)</p>