Есть задача найти количество бит, выставленных в '1', в переменной. То есть, переменная, со значением, например, 0xAA, и нужно посчитать количество бит выставленных в '1' в этой переменной. Результат для 0xAA - 4 бита Переменная может быть: uint8_t, uint16_t, uint32_t... или int16_t, int32_t, int64_t... Понятно что это можно это сделать сдвигом, и проверкой. Тогда для переменной uint64_t будет сделано 64 цикла. А как с минимальным временим, для МК, выполнить эту задачу? Сегодня пока ехал домой с работы, и тер с приятелем на эту тему, родилось прикольное решение. Для 0x55 можно сделать только 4 цикла и две строчки кода. Он знает мою слабость к булевой алгебре и оптимальным решениям типа вертикальных счетчиков.
Уважаемый 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 подобные примеры тут
Forth на AVR, скажем литературно, не очень распространен. Вы бы хоть как то алгоритмически, словами, описали бы. Я с Forth не сталкивался с 8086-го, да и все знакомые, кто были фанатами Forth перешли на Си уже давно.
@SergeiL, у меня в закладках такой вариант https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel (по-моему @DIYMan давал ссылку) + поиск по fast bit counting дает еще ссылку https://gurmeet.net/puzzles/fast-bit-counting-routines/
Уважаемый SergeiL по алгоритму так 1 - делим на 2 с остатком 2 /MOD 2 - получаем частное и остаток он всегда или 0 или 1 т.к. делим на 2 3 - если 0 то единицы в бите нет и наоборот если 1 то это бит 1 4 - суммируем используя второе число стека т.е. swap + swap 5 - проверяем частное 0 то выходим так проверка закончилась, если <>0 то повторяем цикл идем к п 1 Возможно, надо уточнить, критерий оптимальности. Т.е. что уменьшить время вычисления или количество кодов. Для времени вычисления подход следующий, если число не АА а например ААBBCCDD и больше. т.е. большое. Не важно какое. Разбиваем это число на группы и выполняем группы в потоках, потом соединяем результат. В задаче случая АА надо максимально 8 циклов. Для других вариантов разбить на две группы ААBB CCDD и запустить потоки на выполнении. Потоки выполняются параллельно. Или другой вариант, если уж очень большие числа - распределить вычисление между машинами в местной локальной сети. Например используя тсп-ип сокеты. Для уменьшения количества кодов надо переходить на ассемблер другого варианта мне неизвестно.
Уважаемый 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 там же увидите и АА
алгоритмически это неинтересно - это обычный сдвиг на один бит вправо в цикле. Зачем забивать людям голову и писать это на Форте, если на Си тоже самое пишется в две строчки
Все правильно! По обеим ссылкам приведены оптимальные алгоритмы. На самом деле, все очень просто, действительно две строчки: Код (C++): uint8_t val; // входное значение uint8_t count; // результат for(count=0;val;count++) val &= val-1;
shabronov код не мой. потому и не стал показывать Но для вас выложу - вот, держите, полный аналог вашего кода на форте Код (C++): uint8_t Result = 0; for (; AValue; AValue >>= 1) if (AValue & 0x01) Result++; и да, что этот код. что ваш на Форте - не самый оптимальный. Тот, что выложил Сергей на одно сообщение выше - работает быстрее, хотя и там и там две строчки
Сдвиг вправо на 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/ Удобно!