Ну давайте я уже тоже вставлю свои пять копеек 
Проверять на ноль не обязательно:
Сдвиг можно сделать и состовным присваиванием:
Кстати приведенная вами задачка, не такая и трививальная как может показаться, особенно когда начинаем говорить о комплексити, в данном случае она O(n), и сразу возникает вопрос, а можно ли улучшить хотябы до O(lgn)?
И есть несколько алгоритмов для подсчета битов, вот например рекурсивный (stackoverflow), по мне так очень эллегантно но не особо эффективно, потому что вызов функции, создание стека для нее и так далее, уже потеря процессорного времени:
А еще более эффективный, так называемый 'Hamming Weight' или popcount:
Но естественно эффективность зависит от процессора на котором работает код, некоторые процессоры имеют встроенную инструкцию для этого, другие имеют параллельные инструкции и оперируют на битовом векторе, т.е. O(lgn) возможен, но все зависит от CPU, а не от реализации.
Проверять на ноль не обязательно:
| Код |
|---|
| while(val)
|
Сдвиг можно сделать и состовным присваиванием:
| Код |
|---|
| val >>= 1;
|
Кстати приведенная вами задачка, не такая и трививальная как может показаться, особенно когда начинаем говорить о комплексити, в данном случае она O(n), и сразу возникает вопрос, а можно ли улучшить хотябы до O(lgn)?
И есть несколько алгоритмов для подсчета битов, вот например рекурсивный (stackoverflow), по мне так очень эллегантно но не особо эффективно, потому что вызов функции, создание стека для нее и так далее, уже потеря процессорного времени:
| Код |
|---|
| int countBits(int x)
{ return (x) ? 1 + countBits (x & (x - 1)) : 0; } |
А еще более эффективный, так называемый 'Hamming Weight' или popcount:
| Код |
|---|
| int NumberOfSetBits(int i)
{ i = i - ((i >> 1) & 0x55555555); i = (i & 0x33333333) + ((i >> 2) & 0x33333333); return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24; } |
Но естественно эффективность зависит от процессора на котором работает код, некоторые процессоры имеют встроенную инструкцию для этого, другие имеют параллельные инструкции и оперируют на битовом векторе, т.е. O(lgn) возможен, но все зависит от CPU, а не от реализации.
Изменено:
- 08.07.2015 20:18:59(Добавил небольшое замечание к алгоритму...)
