A CRC computation is as follows. You have a data polynomial
$d(x) = \sum_{i=0}^{n-1} d_ix^i$ where the $d_i \in \{0, 1\}$ are
$n$ bits to
be transmitted (or recorded). What is actually transmitted (or
recorded) is
$$t(x) = x^{16}d(x) + p(x)$$
where $p(x)$ is the ${\textit remainder~polynomial}$
when $x^{16}d(x)$ is divided by the CRC polynomial
$C(x) = x^{16} + x^{12} + x^5 + 1$. Note that polynomial division yields
$$
x^{16}d(x) = q(x)C(x) + p(x)
$$
where the quotient $q(x)$ is discarded. But the above equation
can be re-arranged as
$$
q(x)C(x) = x^{16}d(x) - p(x) = x^{16}d(x) + p(x) = t(x)
$$
(because arithmetic on the polynomial coefficients is done modulo $2$
and subtraction is thus the same as addition),
and thus $t(x)$ is a multiple of the CRC polynomial $C(x)$.
Since $p(x)$ is of degree $15$ or less, the
high-order coefficients of the polynomial $t(x)$ are the data bits
while the low-order coefficients are the so-called CRC bits or parity
bits, that is
$$
t(x) = d_{n-1}x^{n-1 + 16} + d_{n-2}x^{n-2+16}
+ \cdots d_0x^{16} + p_{15}x^{15} + p_{14}x^{14} + \cdots + p_0.
$$
In computing $p(x)$ via polynomial long division using paper and pencil,
you need to remember that
(i) $\quad \quad$ $d(x)$ is multiplied by $x^{16}$ before
beginning the long division
(ii) $\quad \quad$ the subtractions of polynomial coefficients that occur in
the long division process are all done modulo $2$ and thus are the same as additions modulo $2$ (that is, the XOR operation)
(iii) $\quad \quad$ the long division continues till $x^{16}d_0$ is processed
and the remainder is a polynomial of degree $15$ or less.
Practical CRC systems often have bells-and-whistles (such as the high-order
bits $8$ bits in $x^{16}d(x)$ are complemented before the division process
begins etc.) which I have not included above because these are likely
not of interest in this forum. However, ignoring such details in your
paper-and-pencil computations will make your results differ
from the ones your machine is giving you.
At the receiving (or reading) end, what you have is a polynomial
$r(x)$ which might be $\textit slightly$ different from $t(x)$
if transmission (or read) errors changed some of the bits. The
CRC error detection process merely divides $r(x)$ by $C(x)$; no
need to multiply $r(x)$ by $x^{16}$ first. If
the remainder is nonzero, then $r(x)$ is $\textit not$ a multiple
of $C(x)$ and so the receiver knows that transmission (or read) errors
have occurred. But if the remainder is $0$, then $r(x)$ is a
multiple of $C(x)$, and
with high probability, is the same as $t(x)$. The low-order
$16$ bits in $r(x)$ are discarded and the high-order $n$ bits
are accepted as error-free data. When the remainder is $0$, there
is a small probability that the difference between $r(x)$ and $t(x)$
is a multiple of $C(x)$. Such errors are referred to as undetected
errors. The probability of undetected error decreases as the degree
of $C(x)$ increases. For this reason, many modern systems use
CRC polynomials of degree 32.
Basically, it looks like this:
(Image rendered in POV-Ray by the author, using a recursively constructed mesh, some area lights and lots of anti-aliasing.)
In the picture, the blue square on the $x$-$y$ plane represents the unit square $[0,1]^2$, and the yellow shape is the graph $z = x \oplus y$ over this square, where $\oplus$ denotes bitwise $\rm xor$.
Note that this graph is discontinuous at a dense subset of the plane. In the 3D rendering above, no attempt has been made to accurately portray the precise value of $x \oplus y$ at the points of discontinuity, and indeed, it is not generally uniquely defined. That is because the discontinuities occur at points where $x$ or $y$ is a dyadic fraction, and therefore has two possible binary expansions (e.g. $\frac12 = 0.100000\dots_2 = 0.011111\dots_2$).
As can be seen from the picture, the graph is self-similar, in the sense that the full graph over $[0,1]^2$ consists of four scaled-down and translated copies of itself. Indeed, this self-similarity is evident from the properties of the $\oplus$ operation, namely that:
- $\displaystyle \frac x2 \oplus \frac y2 = \frac{x \oplus y}2$, and
- $\displaystyle x \oplus \left(y \oplus \frac12\right) = \left(x \oplus \frac12\right) \oplus y = (x \oplus y) \oplus \frac12$.
The first property implies that the graph of $x \oplus y$ over the bottom left quarter $[0,1/2]^2$ of the square $[0,1]^2$ is a scaled-down copy of the full graph, while the second property implies that the graphs of $x \oplus y$ in the other quarters are identical to the first quarter, except that the lower right and upper left ones are translated up by $\frac12$.
The resulting fractal shape is also known as the Tetrix or the Sierpinski tetrahedron, and is a 3D analogue of the 2-dimensional Sierpinski triangle, which is also closely linked with the $\rm xor$ operation — one way to construct approximations of the Sierpinski triangle is to compute $2^n$ rows of Pascal's triangle using integer addition modulo $2$, which is equivalent to logical $\rm xor$.
It may be surprising to observe that this fully 3-dimensional fractal shape is indeed (at least approximately, ignoring the pesky multivaluedness issues at the discontinuities) the graph of a function in the $x$-$y$ plane. Yet, when viewed from above, each of the four sub-tetrahedra indeed precisely covers one quarter of the full unit square (and each of the 16 sub-sub-tetrahedra covers one quarter of a quarter, and so on...).
Best Answer
I looked at the link, but couldn't find where it says the text you have quoted. Regardless, with what it says & for what you're asking for, i.e., multiplying by using just the shift operator, I believe it means that it works only for multiplying each power of $2$ by left shifting by that power value. You can then use the procedures & code in the link to add the numbers without using arithmetic operators, but with this also using bitwise XOR and AND.
With your example, note that $7 = 2^2 + 2^1 + 2^0$ and $3 = 2^1 + 2^0$. Let's say we start with $7$. Note that $7 \times 3$ is $7 \times \left(2^1 + 2^0\right)$. We use the distribution property to get that $7 \times 3 = 7 \times 2^1 + 7 \times 2^0$. For the first term, we can do a left-shift by $1$ bit, the add this to the original value as the second term is already $7$. As such, we get the result to be $\left(2^3 + 2^2 + 2^1\right) + \left(2^2 + 2^1 + 2^0\right)$, with this in decimal being $14 + 7 = 21$.
Alternatively, if we started with $3 = 2^1 + 2^0$, we would use that $7 = 2^2 + 2^1 + 2^0$ to do the multiplications & addition to get that $7 \times 3 = \left(2^3 + 2^2\right) + \left(2^2 + 2^1\right) + \left(2^1 + 2^0\right) = 21$. In this case, the terms are different, and there are $3$ instead of $2$, but the sum is still the same of course.