The register holds r bits

Last time the shift made one bit past degree $r$, and a single XOR with $G$ cleared it. That extra bit is $1$, and the leading coefficient of $G$ is $1$, so their sum is $0$. I know the result before I store the bit.

The bit that cancels itself

Take $G=10011$, so $r=4$, and a remainder $1011$ with the next bit $0$. This is the first of the four zeros after $101101$. Last time’s step shifts, sees bit $4$, and XORs the whole generator:

  10110
^ 10011
-------
  00101

Split off the top bit. The generator is $x^{4}+g(x)$ with $g=0011$:

  1 0110
^ 1 0011
--------
  0 0101

The top line is $1+1=0$. The register only has to keep the low $r$ bits and, when that cancelled bit was going to be $1$, XOR $g$.

Whether the shift produces $x^{r}$ is decided by the MSB already in the register. The register is $r$ bits wide, so

$t_{k}$ may be $0$. It is the coefficient of $x^{r-1}$ in that fixed width, which is what msb reads. The leading coefficient of $R_{k}$ is the highest power that is actually present, and that power may sit lower than $x^{r-1}$. One shift moves the coefficient of $x^{r-1}$ onto $x^{r}$.

Replace the leading power

Since $G\equiv 0$,

and moving $g(x)$ across the congruence changes its sign:

In $\mathbb{F}_2$ that minus sign does nothing. The addition table says $1+1=0$, so $-1=1$, and the same holds coefficient by coefficient: $-g(x)=g(x)$. Therefore

For this generator, $x^{4}\equiv -(x+1)$ and then $x^{4}\equiv x+1$. The two sides differ by $G$:

10000
^00011
------
10011

So the update never builds the bit at $x^{r}$. The incoming bit is $b_{k+1}$. Reducing modulo $x^{r}$ drops every power of degree $r$ or more, and that is a different operation from $\operatorname{rem}_{G}$. With this same $G$ and $P=x^{4}+x^{2}$,

If $t_{k}=0$, then $(x R_{k}+b_{k+1})\bmod x^{r}$ is already $\operatorname{rem}_{G}(x R_{k}+b_{k+1})$. If $t_{k}=1$, add $g$:

On the same step, $t_{k}=1$ because $1011$ starts with $1$. The shift’s low four bits are $0110$, and

0110
^0011
-----
0101

Same remainder as the five-bit XOR.

The program drops the leading $1$ of the generator with a mask, appends the $r$ zero bits as before, and keeps the register inside those $r$ bits:

// Fixed-width register. `truncated_generator` is `generator` without its
// leading 1, which already sits at bit `width`.
[[nodiscard]] uint32_t register_crc(const std::vector<int>& message_bits,
                                    uint32_t generator) {
  const int width = polynomial_degree(generator);
  uint32_t crc_register = 0;
  std::vector<int> augmented = message_bits;
  augmented.resize(augmented.size() + static_cast<size_t>(width), 0);
  const uint32_t register_mask = (1U << width) - 1;
  const uint32_t truncated_generator = generator & register_mask;

  for (const int bit : augmented) {
    const uint32_t msb = (crc_register >> (width - 1)) & 1U;
    crc_register =
        ((crc_register << 1) | static_cast<uint32_t>(bit)) & register_mask;
    if (msb == 1) {
      crc_register ^= truncated_generator;
    }
  }

  return crc_register;
}

msb is $[x^{r-1}]R_{k}$. truncated_generator is $g$. (crc_register << 1) & register_mask, with the new bit in the low place, is $(x R_{k}+b_{k+1})\bmod x^{r}$. The mask is what makes $\deg R_{k}<r$ true at every step, not only after a reduction. The value is still $\operatorname{rem}_{G}$ of the bits read so far, so the message $101101$ followed by four zeros still ends at $1110$.

A generator of degree $32$ is $33$ bits long, since the coefficient of $x^{32}$ is $1$. The familiar constant 0x04C11DB7 is that polynomial with $x^{32}$ removed: it is $g$, which is all the register stores.

The zeros are still written out at the end of the message. The next step is to fold each message bit into the top of the register and stop appending them.