Archive for the ‘Algorithmics’ Category

Fast Bit Reversal

Thursday, 15 October 2009

The naïve method of reversing the bits in a number copies the bits one-by-one in a loop, or alternatively, swaps them two-by-two. This algorithms is O(n) where n is the number of bits.

However, there is an O(log n) method (when n is a power of 2); rather than taking n or n/2 steps, it takes log2(n) steps.

(more…)

HCF without Division

Wednesday, 8 April 2009

The previous blog entry reminded me of this…

(more…)

Division via Multiplication

Wednesday, 8 April 2009

In very special circumstances, integer division can be replaced by (integer) multiplication.

(more…)