Небольшая задачка

Медленный - сдвигать и считать.
Быстрый - табличный, где индекс массива - само число, значение - кол-во единиц в нем.

 

если есть SSE4, то одна asm инструкция POPCNT

 

дабл можно побить на байты, а уже байты смотреть в таблице. или бить дабл на байты тоже долго? (я надеюсь интересует число единиц в двоичном представлении числа дабл)

 

тебе для дела или чисто академический интерес?
надо придумать реализацию вообще без сдвигов?
опять же помоему в памяти все эти 10 байт будут хранится рядом, тоесть достаточно просто выбрать нужный байт и ничего никуда не сдвигать.
чето вроде
ff[k], s[256],sum=0;
for(i=0;i<8;i++)sum+=s[((char*)ff)[k*8+i]];
дабл можно 80 раз маскировать по 1 биту, дальше без сдвига, 0-не 0, но думаю тоже медленно. опять же нужна ассемблерная быстрая реализация или красивая на ЯВУ?
можно попридумывать какнибудь последовательно маскировать хитрыми масками, типа с начала 11110000, потом 11001100, потом 10101010., а потом из всего этого ченить нужное накопать (лениво думать, но кажется что что-то сделать можно)

 

HorstWessel, Вообще-то, сдиг это быстрая операция. Но если "бить" сдвигом не нравится, можно использовать union, к примеру, и получить доступ сразу к нужному байту.

Единицы будем считать в мантиссе или в экспоненте?

 

HorstWessel,
лениво моск напрягать, чес слово... ну наверняка сводится к ln(N) где N число бит маскирований... Я как понимаю топикстартер знает оптимальное решение, но хочет что-бы мы втут коллективно его нашли?

 

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

 

DirectX,
в яблочко

 

А если серьёзно, то наверное оно можно придумать красивое с математической точки зрения решение, но сомневаюсь, что на практике оно будет быстро работать. ИМХО код вроде этого, может быть на ассемблере, успеет расчитать количество единиц во многих миллиардах чисел прежде, чем будет предложено что-то быстрее.

int bitcount(int x)
{
int n = 0;

for (int i = 0; i < 8; i++)
if ((1 << i) & x)
n++;

return n;
}

добавлено через 10 минут
Как вариант, действительно можно сделать таблицу результатов, например, для байта и индексировать числом, полученным по маске. Это будет некий промежуточный вариант. Но здесь тоже нет уверенности, что это быстрее.

int ht[256];

int bitcount(char x)
{

int n = 0;

for (int i = 0; i < 8; i++)

if ((1 << i) & x)

n++;​

return n;​

}

int hashbitcount(int x)
{

return ht[(char)x] + ht[(char)(x >> 8)] + ht[(char)(x >> 16)] + ht[(char)(x >> 24)];​

}

int _tmain(int argc, _TCHAR* argv[])
{

for (int n = 0; n < 256; n++)

ht[n] = bitcount(n);​

printf("\n%d\n", hashbitcount(12345)); // например

return 0;​

}