Dima TКотовасияСоздаем массив целых, большой... [INT_MAX] (т.е. 0..2147483647)
...
главное - чтобы памяти хватило... :)
8 Гб под это безобразие ... мдя ...

И не факт что будет быстрее чем эти 5 действий 21336940 , т.к. обращение к памяти отсутствующей в кэше проца достаточно много времени занимает.
Если внимательно посмотреть на эту таблицу - то можно увидеть что она вырожденная. Куча повторов.
Ее можно свести к списку интервалов или еще какой-то структуре. Впрочем мне нравятся задачи доведенные
до абсурда. Они позволяют пересмотреть постановку под другим углом.

По поводу сабж. Генри Уоррен что-то упоминал о процессорах (не семейства x86) которые
изначально имеют команды для подсчета битов и определения порядка лидирующего бита.

А вот еще кусок кода. Так вычисляет сабж один финский парень...

http://lxr.linux.no/#linux v2.6.25/include/asm-x86/bitops_32.h#L134