divisor moves over to align with the next 1 in the dividend (since quotient for that step was zero) 1011 (in other words, it doesn't necessarily move one bit per iteration) 00000000110100 000 1011 00000000011000 000 1011 00000000001110 000 1011 00000000000101 000 101 1 ----------------- 00000000000000 100 <--- remainder (3 bits). Division algorithm stops here as dividend is equal to zero. Since the leftmost divisor bit zeroed every input bit it touched, when this process ends the only bits in the input row that can be nonzero are the n bits at the right-hand end of the row. These n bits are the remainder of the division step, and will also be the value of the CRC function (unless the chosen CRC specification calls for some postprocessing). The validity of a received message can easily be verified by performing the above calculation again, this time with the check value added instead of zeroes. The remainder should equal zero if there are no detectable errors. 11010011101100 100 <--- input with check value 1011 <--- divisor 01100011101100 100 <--- result 1011 <--- divisor ... 00111011101100 100 ...... 00000000001110 100 1011 00000000000101 100 101 1 ------------------ 00000000000000 000 <--- remainder The following Python code outlines a function which will return the initial CRC remainder for a chosen input and polynomial, with either 1 or 0 as the initial padding. Note that this code works with string inputs rather than raw numbers: def crc_remainder(input_bitstring, polynomial_bitstring, initial_filler): """Calculate the CRC remainder of a string of bits using a chosen polynomial. initial_filler should be '1' or '0'. """ polynomial_bitstring = polynomial_bitstring.lstrip('0') len_input = len(input_bitstring) initial_padding = (len(polynomial_bitstring) - 1) * initial_filler input_padded_array = list(input_bitstring + initial_padding) while '1' in input_padded_array[:len_input]: cur_shift = input_padded_array.index('1') for i in range(len(polynomial_bitstring)): input_padded_array[cur_shift + i] \ = str(int(polynomial_bitstring[i] != input_padded_array[cur_shift + i])) return ''.join(input_padded_array)[len_input:] def crc_check(input_bitstring, polynomial_bitstring, check_value): """Calculate the CRC check of a string of bits using a chosen polynomial.""" polynomial_bitstring = polynomial_bitstring.lstrip('0') len_input = len(input_bitstring) initial_padding = check_value input_padded_array = list(input_bitstring + initial_padding) while '1' in input_padded_array[:len_input]: cur_shift = input_padded_array.index('1') for i in range(len(polynomial_bitstring)): input_padded_array[cur_shift + i] \ = str(int(polynomial_bitstring[i] != input_padded_array[cur_shift + i])) return ('1' not in ''.join(input_padded_array)[len_input:]) >>> crc_remainder('11010011101100', '1011', '0') '100' >>> crc_check('11010011101100', '1011', '100') True CRC-32 algorithm This is a practical algorithm for the CRC-32 variant of CRC. The CRCTable is a memoization of a calculation that would have to be repeated for each byte