1. Этот сайт использует файлы cookie. Продолжая пользоваться данным сайтом, Вы соглашаетесь на использование нами Ваших файлов cookie. Узнать больше.

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

Тема в разделе "Программирование", создана пользователем HorstWessel, 25.04.07.

  1. HorstWessel

    HorstWessel Активный участник

    1.585
    0
    Есть метод, у него один параметер типа байт. метод возвращает кол-во единиц в этом байте. Предлагайте варианты реализации
     
  2. Zuka58

    Zuka58 Активный участник

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

    Гость Гость

    если есть SSE4, то одна asm инструкция POPCNT :d
     
  4. HorstWessel

    HorstWessel Активный участник

    1.585
    0
    Корректно.

    Если теперь слегка усложнить задачу. метод в качестве параметра принимает число типа double. по прежнему считаем что сдвигать по битам слишком долго.
     
  5. sema

    sema Активный участник

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

    HorstWessel Активный участник

    1.585
    0
    бить сдвигом? долго конечно.
     
  7. sema

    sema Активный участник

    8.741
    70
    тебе для дела или чисто академический интерес?
    надо придумать реализацию вообще без сдвигов?
    опять же помоему в памяти все эти 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., а потом из всего этого ченить нужное накопать (лениво думать, но кажется что что-то сделать можно)
     
  8. Zuka58

    Zuka58 Активный участник

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

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

    HorstWessel Активный участник

    1.585
    0
    в двоичном представлении ;)

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

    добавлено через 2 минуты
    Проще...
     
  10. sema

    sema Активный участник

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

    HorstWessel Активный участник

    1.585
    0
    sema,
    Ты если можешь - напряги свой моск, а для чего мне это нужно не нужно отгадывать. На все есть своя причина.
     
  12. DirectX

    DirectX Активный участник

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

    sema Активный участник

    8.741
    70
    DirectX,
    :grin: в яблочко
     
  14. DirectX

    DirectX Активный участник

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

    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;​
    }
     
    Последнее редактирование: 25.04.07
  15. HorstWessel

    HorstWessel Активный участник

    1.585
    0
    Его, мозга, просто нет. Отсюда и весь флуд.

    А если серьезно, то твое предложение плохое и очень плохое.

    Тем не мене, спасибо всем кто ответил, акутальность в этом уже отпала.