Hacker News Reader

It is method #9.

Deleted comment

Because the methods clearly get more complicated. Starting simply and naively and then improving is a perfectly standard way of teaching.

Articles like these, which provide detailed explanation of the methods involved and results of benchmarks help greatly.

The benchmarks would probably be somewhat misleading in a lot of cases here. I'm fairly certain that most compilers will replace a /2 with >>1 for example, so that isn't really going to end up being reflected when you compile it.

That depends on the CPU used. Modern CPU have more arithmetic units than logical units and can perform more divisions than bit shifts. There was a good video presentation of that, but I can't find the link now.

EDIT: http://blogs.msdn.com/b/shawnhar/archive/2007/03/19/a-story-... gives other reasons why multiplications can be faster than bit shifts.

That's multiplies, not divides. Modern CPUs are still faster at shifts than divides, even the pentium4, which lacked a single-cycle shift unit.

Reply on news.ycombinator.com