Здравствуйте, CreatorCray, Вы писали:

CC>Здравствуйте, Тёмчик, Вы писали:

Тё>>Подсчёт битов ничего не говорит о человеке в плане bigO.
CC>Ты правда думаешь что это как то сильно отличается от переворота строки?

Зависит от размера числа. Для 8-битного можно сделать так:

int bits_cnt( uint8_t byte )
{
    static const int BITS_IN_BYTE[] =
    {
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
        4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
    };

    return BITS_IN_BYTE[ byte ];
}

Для чисел большей размерности табличка слишком большой получится. В этом случае можно сложить сумму бит в каждом байте или посчитать с помощью сдвигов и битовых масок. Реализовать подсчёт битов в числе произвольного размера можно тоже по разному. В С++ можно сделать шаблонную функцию, а можно, в стиле C — функцию, в которой передаётся адрес, преобразованный к указателю на uint8_t и размер, а для подсчёта использовать таблицу. В других языках могут быть свои особенности.

Но вполне возможно, что оба участника собеседования могут сделать разные реализации, но реализация сделанная на собеседовании может и совпасть и не совпасть с тем, что ожидают от кандидата.