Skip to content

Comment on Absolute Beginner's Guide to Bit Shiftingparent

Comments

As well as the practical details of barrel shifter implementation design that psykotic points out, older CPUs couldn't afford the space for a barrel shifter and implemented shifts as a sequence of one-bit shifts. So for instance the 8086 took 8 clock cycles plus another 4 cycles per bit shift, and on that kind of CPU it was definitely not as fast as an addition.

Incidentally there is a standard trick for integer division by constant which allows you to convert it into a series of 3 to 5 shift and add/subtract operations; any decent C compiler will implement this. _Hacker's Delight_ has the explanation of the algorithm, I think.

Here's an article explaining the trick:

http://ridiculousfish.com/blog/posts/labor-of-division-episo...

And a library from the same guy for generating code at runtime to do fast division by constants:

http://libdivide.com/

AboutSource Built by g1lg1l

Hackerly is an independent reader for Hacker News, built on the public HN API. Not affiliated with Y Combinator.