Ответ в теме: Дан массив из n n-битных значений. Подсчитать количество единиц

Главная Форумы Программирование Дан массив из n n-битных значений. Подсчитать количество единиц Ответ в теме: Дан массив из n n-битных значений. Подсчитать количество единиц

#4267

По статье (я ее просмотрел). Есть стойкое ощущение, что парня сильно умыли на собеседовании в google, чтобы поднять ЧСВ он решил “отомстить” и слегка наврать. Последний вопрос я не понял (возможно, в силу некомпетентности автор статьи даже смысл не смог передать).

По вопросу:

Я так понимаю, надо узнать количество единиц. В примере 8 единиц.

Если так – то самый быстрый способ – это завести таблицу, в которой для каждого числа (допустим 8-ми разрядного) записать число единиц. Т.е. банально в массив помещаем количества единиц. Нужно узнать сколько единиц в числе 123 – обращаемся в table[123]. Расчет такой таблицы можно сделать весьма быстро. Чтобы посчитать число единиц во всей последовательности (1000 чисел) пишем что-то типа:

for (int i = 0; i < 10000/sizeof(table[0]); ++i) {
  count += table[seq[i]];
}

Это схематично. Асимптотическая сложность такого алгоритма – O(n/m) где n – длина исходной последовательности, а m – разрядность чисел в таблице. Лично мне очевидно, что более эффективного решения нет, если кто-то знает такой способ – очень прошу объяснить.

По ответу и сдвигам. Я не понял что там предлагается и как это связано с вопросом (возможно ты неверно понял вопрос, как и я). Сдвиги тут никак не помогут. Берем число 0101. В нем 2 единицы, куда его сдвинуть чтобы получить нужный мне ответ? У числа 1100 и 0011 тоже две единицы. Сдвигами одно число в другое не превращается.