AES Mix columns bit example I have been given a 4x4 matrix and each entry is an 8-bit long byte. I have been given the 4x4 matrix that I need to multiply each column by of the first matrix by.

$$\begin{pmatrix}2 &amp; 3 &amp; 1 &amp; 1\\\ 1 &amp; 2 &amp; 3 &amp; 1\\ 1 &amp; 1 &amp; 2 &amp; 3\\ 3 &amp; 1 &amp; 1 &amp; 2\end{pmatrix}$$

The method that I have been told to use seems confusing. I have searched around the internet and found many examples with polynomials but I'm not supposed to use this method. 

All I have been told is: 

Multiplying by 01 does nothing
 Multiplying by 02 corresponds to multiplying the byte by 10 (because 2 is 10 in binary). This
is simply a left shift by one place. If the left-hand bit of the original byte was 1, then XOR the
answer with 100011011.
 Multiplying by 03 corresponds to multiplying the byte by 11 (because 3 is 11 in binary). This is
a left shift, followed by an XOR with the original byte. Again, if the left-hand bit of the original
byte was 1, then XOR the answer with 100011011.

I find the XOR bit strange as well - because that is a string of 9 bits and the bytes are only 8.

Can anyone make sense of this or point me in the direction of a good example?
If you look at the code in the Wikipedia we will see this part of the code;


h = (unsigned char)((signed char)r[c] &gt;&gt; 7);
b[c] = r[c] &lt;&lt; 1;
[c] ^= 0x1B &amp; h;


h stores the leftmost bit of c

c is x-or'ed with 0x1b but not with 0x11b  why?

When shifting r left by one, the MSB value is discarded. Before discarding, we hold this value with h. 


If h==0 than modulus operation is not required. The 0x1B &amp; h = 0x0 so there is no x-or with 0x1b
If h=1 than modulus operation is required. The 0x1B &amp; h = 0x1B. The x-or with 0x1b is performed.
Note that: it is not x-or with 0x11b it is with 0x1b since we discarded the MSB 1 while shifting. Therefore, there is no need to x-or with 0x11b, x-oring with 0x1b is enough. Now, it is clear that everthing is in Bytes.


A small example;

Here [ ] represents 8-bit.

Let multiply $a = (x^7+x^6+x^3+x)$ by $\{2\}$


binary representation of  $a = [11001010]$
$h = 1 = [00000001]$
$b = a \ll 1 = 1[10010100]$ but everthing is in Bytes, therefore 
$b = [10010100]$
$h \wedge 0x1b = [00000001] \wedge [00011011] = [00011011] = 0x1b$
$b \oplus 0x1b = [10010100] \oplus [00011011] = [10001111] = 0x8f$