Implementation time of Linear Feedback Shift Register (LFSR)
There are two forms of the LSFR algorithm.

There's the hardware implementation, which computes parity = (bitcount(state&amp;mask))&amp;1, and shifts the parity bit into the end of the word. This maps well onto hardware shift registers, but is not software efficient. It's the computation of the parity that will tend not have a single cycle bitcount() operation available.

Then there's the software implementation, which works on a whole word at a time. Pseudocode for this is

if (state&amp;1 == 1)
     state = state XOR mask;
state = state &gt;&gt; 1;


All state bits that correspond to the mask get conditionally XOR'd at the same time, when the LSB is 1, and left unaltered when it's 0. This only works easily for word lengths up to the native word length of the processor, but extension to multi-word operation is trivial.

The mask for the software type is the same as for the hardware type, except for being bit reversed, that is the MSB of one is the LSB of the other.

The execution time for a single bit changes depending on whether a 0 or 1 is present in the LSB, this may or may not be acceptable depending on your precise requirements. If a deterministic time is required, then you'll need an else statement padded with one or more NOPs according to your particular processor. As the total number of 0 and 1 bits is deterministic, you can calculate the run time for a whole 2^m-1 bits, and so the average time for one bit.

If you're trying to get the operations count down, maybe even thinking in assembler, then be aware that in many processors, a right shift operation drops the LSB into one of the flag bits, often the carry, to be available for multi-word shifts. This bit is often testable directly, so avoiding the need to mask off the LSB as a separate operation.