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

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

#4272

Это вообще что?
Ну вот смотри, у тебя есть байт, ты назвал его u8:
typedef unsigned char u8;
Тебе надо посчитать сколько в нем единиц. Ты для этого выполнишь в худшем случае 8 операций сдвига, 8 операций логического И, 8 проверок n на равенство нулю и 8 суммирований. Это только то, что внутри функции CountOnes0 записано. Вне этой функции добавляется еще одно логическое И, суммирование, умножение и сложение. Я не учитываю затраты на вызов функции, пускай она проинлайнится.

Что предложил я (возможно такой же вариант предложили в google) – table[seq[i]], операция обращения к элементу массива – это одно умножение и одно сложение (к адресу начала массива прибавляется i*sizeof(Type)). Да, одно из них можно убрать, кстати. Интересно, что же работает быстрее?

ЗЫ. В твоем коде вообще не все понял. Как этот код с задачей связан (ну кроме функции, которая каким-то стремным способом считает число единиц)? – в задаче ведь есть массив из 10 тысяч значений, а у тебя этот массив где? – ты считаешь количества единиц для некоторых k, которые получаешь из m, выковыривая последние 8 разрядов оттуда. Сами эти m при этой считаешь по какой-то дикой формуле. Просто не понятно как это с исходной задачей связано, но если ты доработаешь это (чтобы условию соответствовало) – можно будет скорость сравнить (предполагаю, что мой вариант будет работать раз в 5-10 быстрее).