Как оптимально найти кол-во бит в '1' в переменной.

Тема в разделе "Флудилка", создана пользователем SergeiL, 12 апр 2022.

  1. SergeiL

    SergeiL Оракул Модератор

    Есть задача найти количество бит, выставленных в '1', в переменной.
    То есть, переменная, со значением, например, 0xAA, и нужно посчитать количество бит выставленных в '1' в этой переменной.
    Результат для 0xAA - 4 бита
    Переменная может быть: uint8_t, uint16_t, uint32_t... или int16_t, int32_t, int64_t...

    Понятно что это можно это сделать сдвигом, и проверкой.
    Тогда для переменной uint64_t будет сделано 64 цикла.
    А как с минимальным временим, для МК, выполнить эту задачу?
    Сегодня пока ехал домой с работы, и тер с приятелем на эту тему, родилось прикольное решение.
    Для 0x55 можно сделать только 4 цикла и две строчки кода. ;)
    Он знает мою слабость к булевой алгебре и оптимальным решениям типа вертикальных счетчиков.
     
    Andrey12 нравится это.
  2. parovoZZ

    parovoZZ Гуру

    всё есть в книжке Алгоритмические трюки для программистов
     
    Andrey12 нравится это.
  3. SergeiL

    SergeiL Оракул Модератор

    Мы то ее не читали.
    И, каков ответ? :~
     
    Andrey12 нравится это.
  4. shabronov

    shabronov Нерд

    Уважаемый SergeiL Предлагаю такой вариант подсчета
    0 0xAA BEGIN 2 /MOD 0= IF 0 ELSE 1 THEN SWAP + SWAP 0= UNTIL
    Пояснение
    - строка на языке FORTH дана как интерпритатор. Если обрамить в : *** ; будет компиляция.
    - перед BEGIN 0 - cчетчик единиц в числе
    АА - число ( 1010-1010 )
    - на выходе т.е. после UNTIL будет число с количеством 1 в АА т.е. 4
    как то так решается задач на FORTH
    подобные примеры тут
     
  5. SergeiL

    SergeiL Оракул Модератор

    Forth на AVR, скажем литературно, не очень распространен.
    Вы бы хоть как то алгоритмически, словами, описали бы.
    Я с Forth не сталкивался с 8086-го, да и все знакомые, кто были фанатами Forth перешли на Си уже давно.
     
    Andrey12 нравится это.
  6. ZAZ-965

    ZAZ-965 Гуру

    SergeiL нравится это.
  7. shabronov

    shabronov Нерд

    Уважаемый SergeiL по алгоритму так
    1 - делим на 2 с остатком 2 /MOD
    2 - получаем частное и остаток он всегда или 0 или 1 т.к. делим на 2
    3 - если 0 то единицы в бите нет и наоборот если 1 то это бит 1
    4 - суммируем используя второе число стека т.е. swap + swap
    5 - проверяем частное 0 то выходим так проверка закончилась, если <>0
    то повторяем цикл идем к п 1
    Возможно, надо уточнить, критерий оптимальности. Т.е. что уменьшить время вычисления или количество кодов.
    Для времени вычисления подход следующий, если число не АА а например ААBBCCDD и больше. т.е. большое. Не важно какое. Разбиваем это число на группы и выполняем группы в потоках, потом соединяем результат. В задаче случая АА надо максимально 8 циклов. Для других вариантов разбить на две группы ААBB CCDD и запустить потоки на выполнении. Потоки выполняются параллельно. Или другой вариант, если уж очень большие числа - распределить вычисление между машинами в местной локальной сети. Например используя тсп-ип сокеты.
    Для уменьшения количества кодов надо переходить на ассемблер другого варианта мне неизвестно.
     
  8. shabronov

    shabronov Нерд

    Уважаемый SergeiL практический пример далее
    \ начало текста программы
    : TEST ( -- ) 0 SWAP BEGIN 2 /MOD SWAP 0= IF 0 ELSE 1 THEN ROT + SWAP DUP 0= UNTIL DROP ;
    : MAIN HEX 0x100 0 DO I . I TEST . LOOP KEY ;
    \ подготавливаем переменные и текст программы записываем в исполняемый файл.
    0 TO SPF-INIT? ( в переменную записываем код 0 – означает что инициализация выполняется )
    ' NOOP MAINX ! ( в переменную записываем адрес выхода )
    ' MAIN TO <MAIN> ( в переменную записываем старт программы со слова MAIN )
    S" test2.exe" SAVE ( сохраняем файл исполнения с именем test2.exe )
    BYE ( выходим из режима редактирования и компиляция, т.е. все бай-бай )
    \ текст программы окончен.

    компилятор
    http://90.189.213.191:4422/temp/gr_mi38_37_mp4_sh/gen1/100_spf4.zip
    В блокнот скопируйте текст от \ начало.. и до \ текст окончен.
    назовите файл с расширением f и откройте компилятором из архива сформируется файл test2.exe
    он выдает все количества бит для чисел от 0 до FF там же увидите и АА
     
  9. b707

    b707 Гуру

    алгоритмически это неинтересно - это обычный сдвиг на один бит вправо в цикле.
    Зачем забивать людям голову и писать это на Форте, если на Си тоже самое пишется в две строчки
     
    Andrey12 нравится это.
  10. shabronov

    shabronov Нерд

    Уважаемый b707 Что ты бы показать эти две строчки? Нет ? А пишете что гуру
     
  11. SergeiL

    SergeiL Оракул Модератор

    Все правильно!
    По обеим ссылкам приведены оптимальные алгоритмы.

    На самом деле, все очень просто, действительно две строчки:
    Код (C++):
        uint8_t val;      // входное значение
        uint8_t count; // результат
     
        for(count=0;val;count++)
            val &= val-1;
     
     
  12. b707

    b707 Гуру

    shabronov
    код не мой. потому и не стал показывать
    Но для вас выложу :) - вот, держите, полный аналог вашего кода на форте
    Код (C++):
    uint8_t Result = 0;
        for (; AValue; AValue >>= 1)
            if (AValue & 0x01) Result++;
       
    и да, что этот код. что ваш на Форте - не самый оптимальный.
    Тот, что выложил Сергей на одно сообщение выше - работает быстрее, хотя и там и там две строчки
     
    Andrey12 и DetSimen нравится это.
  13. SergeiL

    SergeiL Оракул Модератор

    Сдвиг вправо на 1 бит - то же деление на 2,
    Проверка остатка от деления - та же проверка бита на 1/0

    По сути это тот же код, что выложил выше @b707
    Для меня со сдвигом более нагляден, но это ИМХО.
    Если сравнивать, то код ниже показывает разницу в циклах:
    Код (C++):
        val=0x80;
        counts=0;
        for(num=0;val;num++)
        {
          val &= val-1;
          counts++;
        }
        Serial.print("Result 1 =  ");
        Serial.print(num);
        Serial.print("   counts 1 =  ");            
        Serial.print(counts);

        val=0x80;
        num=0;
        counts=0;
        while(val)
        {
          if (val%2)
            num++;
          val = val/2;
          counts++;
        }

        Serial.print("\nResult 2 =  ");            
        Serial.print(num);
        Serial.print("   counts 2 =  ");            
        Serial.print(counts);
    Вывод в порт будет следующим:
    Код (Text):
    Result 1 =  1   counts 1 =  1
    Result 2 =  1   counts 2 =  8
    К стати, симулировалось в https://wokwi.com/ Удобно!
     
    Andrey12 и b707 нравится это.
  14. DetSimen

    DetSimen Гуру

    чота знакомое :)))
     
    Andrey12 и b707 нравится это.
  15. b707

    b707 Гуру

    я сразу сказал, что
    :)
     
    Andrey12 и DetSimen нравится это.
  16. DetSimen

    DetSimen Гуру

    Да даже если бы сказал, что твой, я бы не расстроился. :))))