Пока я отсутствовал по причине первого сервиса мота, ещё один бакалавр в Computer Science пал жертвой коварного вопроса.

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

Тё>Пока я отсутствовал по причине первого сервиса мота, ещё один бакалавр в Computer Science пал жертвой коварного вопроса.
Ты полгода назад ещё сам

Автор: Тёмчик
Дата: 27.03.18

считал что "книжная задачка", "уныло", и не верил опытным товарищам.

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

CC>Ты полгода назад ещё сам

Автор: Тёмчик
Дата: 27.03.18

считал что "книжная задачка", "уныло", и не верил опытным товарищам.

Подсчёт битов ничего не говорит о человеке в плане bigO. Поэтому я и сейчас могу повторить- задачка унылая. Можно ещё спросить ieee 754 или перечислить ключи запуска jvm.

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

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

Здравствуйте, 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 и размер, а для подсчёта использовать таблицу. В других языках могут быть свои особенности.

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

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

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

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

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

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

Плохое решение. Выкидывать из кеша процессора линию забивая её мусором (а если будет много таких операций — ещё и кучу линий). И это при том, что в процессоре есть специальная команда как раз для этой задачи: POPCNT.

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

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

Можно ещё спросить ieee 754 или перечислить ключи запуска jvm.

Отличается тупизной: проверяет память кандидата. Ну по твоим ответам оно заметно.

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

Тё>Отличается тупизной: проверяет память кандидата. Ну по твоим ответам оно заметно.
Да, Артёмка, ignorance is bliss это про тебя.

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

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

vsb>Плохое решение. Выкидывать из кеша процессора линию забивая её мусором (а если будет много таких операций — ещё и кучу линий). И это при том, что в процессоре есть специальная команда как раз для этой задачи: POPCNT.

Зависит от процессора. В общем случае неизвестно даже, есть ли в процессоре кэш, не говоря уж об SSE и прочем SIMD.

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

vsb>Плохое решение. Выкидывать из кеша процессора линию забивая её мусором (а если будет много таких операций — ещё и кучу линий).
Нет, ты за деревьями не видишь леса, не отвлекайся.

vsb>И это при том, что в процессоре есть специальная команда как раз для этой задачи: POPCNT.
Упоминание POPCNT будет плюсом, но будет предложено вернутся к обсуждению алгоритма.

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

Тё>>Отличается тупизной: проверяет память кандидата. Ну по твоим ответам оно заметно.
CC>Да, Артёмка, ignorance is bliss это про тебя.

Ты какой-то совсем упертый. Ну считаешь, что трюки с битами отсекут любителей городить O(n*n) на ровном месте и парсить файл путём запихивания в память целиком- это твоё мнение.

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

Тё>Ну считаешь, что трюки с битами отсекут любителей городить O(n*n) на ровном месте и парсить файл путём запихивания в память целиком- это твоё мнение.

Артёмка, ты так и не понял смысл подобных задач. Биты там не важны.

AN> static const int BITS_IN_BYTE[] =

Неудачное название переменной. В байте всегда 8 бит.

S>Зависит от процессора. В общем случае неизвестно даже, есть ли в процессоре кэш, не говоря уж об SSE и прочем SIMD.

IMHO, это экзотика, когда ты не в курсе, пишешь ли ты программу под STM32f4 или i7, под винду или Мак. Используемые алгоритмы и архитектура софта также будет сильно зависеть от платформы (контроллер это или четырехсокетовый сервер). Так что обычно ты в курсе аппаратной архитектуры, оси и возможных версий сторонних библиотек, которые используются в проекте.

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

CC>Артёмка, ты так и не понял смысл подобных задач. Биты там не важны.

Если чел не знает поведение битов- это не делает плохого программиста. А ты просто запомнил простейшую формулу n & (n-1)- совершенно тупой вопрос на память.

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

S>>Зависит от процессора. В общем случае неизвестно даже, есть ли в процессоре кэш, не говоря уж об SSE и прочем SIMD.

M>IMHO, это экзотика, когда ты не в курсе, пишешь ли ты программу под STM32f4 или i7, под винду или Мак. Используемые алгоритмы и архитектура софта также будет сильно зависеть от платформы (контроллер это или четырехсокетовый сервер). Так что обычно ты в курсе аппаратной архитектуры, оси и возможных версий сторонних библиотек, которые используются в проекте.

Да, но в задании нифига не сказано — там сказано только "посчитайте биты в int32". Довольно странно с таким заданием начинать говорить о каких-то линиях кэша и прочих тонкостях, не спросив, а какой процессор и есть ли вообще кэш.

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

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

S>>>Зависит от процессора. В общем случае неизвестно даже, есть ли в процессоре кэш, не говоря уж об SSE и прочем SIMD.

M>>IMHO, это экзотика, когда ты не в курсе, пишешь ли ты программу под STM32f4 или i7, под винду или Мак. Используемые алгоритмы и архитектура софта также будет сильно зависеть от платформы (контроллер это или четырехсокетовый сервер). Так что обычно ты в курсе аппаратной архитектуры, оси и возможных версий сторонних библиотек, которые используются в проекте.

S>Да, но в задании нифига не сказано — там сказано только "посчитайте биты в int32". Довольно странно с таким заданием начинать говорить о каких-то линиях кэша и прочих тонкостях, не спросив, а какой процессор и есть ли вообще кэш.

А есть ли там процессор вообще?
Про это может ничего и не сказано, а семантика языка и без процессора существует.

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

CAF>А есть ли там процессор вообще?
CAF>Про это может ничего и не сказано, а семантика языка и без процессора существует.

Тоже хороший вопрос.

Здравствуйте, Masterspline,

M>Неудачное название переменной. В байте всегда 8 бит.

Чегоооо??? Тебе явно не приходилось сталкиваться с нестандартными архитектурами. А вот мне например приходилось сталкиваться с экзотической архитектурой, где в байте было 18 бит Байт и октет — почувствуйте разницу!