Как оптимально найти кол-во бит в '1' в переменной.
- Войдите на сайт для отправки комментариев
Втр, 12/04/2022 - 23:37
Есть задача найти количество бит, выставленных в '1', в переменной.
То есть, переменная, со значением, например, 0xAA, и нужно посчитать количество бит выставленных в '1' в этой переменной.
Результат для 0xAA - 4 бита = 4.
Переменная может быть: uint8_t, uint16_t, uint32_t... или int16_t, int32_t, int64_t...
Понятно что это можно это сделать сдвигом, и проверкой.
Тогда для переменной uint64_t будет сделано 64 цикла.
А как с минимальным временим, для МК, выполнить эту задачу?
Сегодня пока ехал домой с работы, и тер с приятелем на эту тему, родилось прикольное решение.
Для 0x55 можно сделать только 4 цикла и две строчки кода. ;)
Он знает мою слабость к булевой алгебре и оптимальным решениям типа вертикальных счетчиков :-).
А какова прикладная цель данной задачи? Что потом с результатом то будете делать? Просто интересно.
Сергей, вот в этой книге есть целая глава про эту задачу. Полюбопытствуйте.
Не мудрствуя лукаво
Не мудрствуя лукаво
O_O Это как раз мудрствуя. Не мудрствуя вот:
template <typename T> uint8_t NumBitsInValue(T AValue) { uint8_t Result = 0; for (; AValue != 0; AValue >>= 1) { if (AValue & 0x01) Result++; } return Result; }14 байт кода:
uint8_t __attribute__ ((noinline)) NumOneBits(uint8_t b) { uint8_t result; asm volatile( "mov r18,%1\n\t" "clr %0\n\t" "l:\n\t" "sbrc r18,0\n\t" "inc %0\n\t" "lsr r18\n\t" "brne l\n\t" : "=r" (result) : "r" (b) : "r18" ); return result; }template <typename T> uint8_t NumBitsInValue(T AValue) { uint8_t Result = 0; for (; AValue != 0; AValue >>= 1) { if (AValue & 0x01) Result++; } return Result; }Вот и я таким же образом всегда делал.
Сергей, вот в этой книге есть целая глава про эту задачу. Полюбопытствуйте.
Книжка очень интересная, я раньше не сталкивался с ней. Спасибо!!!
Поднятая тема в ней раскрыта.
SergeiL там написано что если нет 256 байт под таблицу, то всё печально относительно скорости...
Раньше в библиотеке берёшь книжку, а там всё исписано "книга очень интересная"... Типа, отзывы.)
Даже в ARM не запасли встроенную инструкцию по этому поводу - видимо не очень часто используется.
14 байт кода:
uint8_t __attribute__ ((noinline)) NumOneBits(uint8_t b) { uint8_t result; asm volatile( "mov r18,%1\n\t" "clr %0\n\t" "l:\n\t" "sbrc r18,0\n\t" "inc %0\n\t" "lsr r18\n\t" "brne l\n\t" : "=r" (result) : "r" (b) : "r18" ); return result; }Я на Асме под AVR не писал. Еще на 8051 перешел с Асма на Си.
Посмотрел вариант со сдвигом в цикле на Си, он ровно в такой же код как у вас компилируется.
Мне очень понравился данный вариант:
Тут в цикле крутимся только столько раз, сколько '1'
Понятно, что это "копейки", но прикольно.
Посмотрел вариант со сдвигом в цикле на Си, он ровно в такой же код как у вас компилируется.
ПРУФ будет ? Я то же посмотрел что во что вырисовывается.
Тут в цикле крутимся только столько раз, сколько '1'
дак в моём тоже, пока есть 1, крутимся, кончились - выходим
дак в моём тоже, пока есть 1, крутимся, кончились - выходим
нет Деда, тут большая разница. Твой цикл пропускает нули только в старших разрядах...
Если, для примера, взять байт 0b00010000 - то твой цикл отработает его за 5 итераций. а этот - всего за одну.
Тут в цикле крутимся только столько раз, сколько '1'
дак в моём тоже, пока есть 1, крутимся, кончились - выходим
А для 0x8000000000000000 сколько раз прокрутимся? Это uint64_t c 1 в старшем разряде.
Да понятно, что это только в теории. :-)
Да понятно, что это только в теории. :-)
почему "только в теории"? - алгоритм рабочий, ошибок в нем не вижу
добавка ... хотя нет, вроде понял, о чем вы... операция x & y , где оба операнда - uint64 - явно будет выполнена не за одну операцию контроллера...
дак в моём тоже, пока есть 1, крутимся, кончились - выходим
нет Деда, тут большая разница. Твой цикл пропускает нули только в старших разрядах...
Если, для примера, взять байт 0b00010000 - то твой цикл отработает его за 5 итераций. а этот - всего за одну.
Согласен.
А вот интересно, кто нибудь использовал подсчёт этих 1-ц? И для каких целей?
А вот интересно, кто нибудь использовал подсчёт этих 1-ц? И для каких целей?
У меня климат задний в машине светодиодиками показывает выставленный уровень.
Нужно его считать и вывести миганиями на индикатор на передней консоли.
Светодиоды ШИМ-тся для снижения яркости в вечернее время, тут все на ассиметричных вертикальных счетчиках прекрасно решается, по маске.
Незамаскированные биты (кнопки) обрабатываются симметрично.
Весь дребезг и ШИМ устраняется за 1 проход для всех каналов светодиодов и кнопок (без циклов). Т.К. они лезут в 1 байт.
Так и прикольно же написать "правильно" :-)
А вот интересно, кто нибудь использовал подсчёт этих 1-ц? И для каких целей?
Я использовал. Очень давно, правда, когда ещё бортовые вычислители программировал, а это уж почти неправда. По прямому назначению. Было восемь датчиков, каждый взводил свой бит, а мне было важно сколько датчиков сработало. Не важно, какие именно - важно сколько. Вот и использовал.
Код:
unsigned char NumBitsInValue(unsigned char val) { unsigned char Result = 0; for (; val != 0; val >>= 1) { if (val & 0x01) Result++; } return Result; }Листинг после компиляции:
(0176) unsigned char NumBitsInValue(unsigned char val) (0177) { (0178) unsigned char Result = 0; 0014A 24AA CLR R10 (0179) for (; val != 0; val >>= 1) { 0014B C004 RJMP 0x0150 (0180) if (val & 0x01) Result++; 0014C FF00 SBRS R16,0 0014D C001 RJMP 0x014F 0014E 94A3 INC R10 0014F 9506 LSR R16 00150 2300 TST R16 00151 F7D1 BNE 0x014C (0181) } (0182) return Result; (0183) }SergeiL Чем компилировали ? (не похоже на GCC)
Очень похоже, но длиннее (реализации возврата еще не видно в листинге).
Вот вариант с обходом только единиц, 20 байт (аналог кода из #10):
uint8_t __attribute__ ((noinline)) NumOneBits(uint8_t b) { uint8_t result; asm volatile( "mov r18,%1\n\t" "clr %0\n\t" "tst r18\n\t" "l:\n\t" "breq exit\n\t" "inc %0\n\t" "mov r19,r18\n\t" "dec r19\n\t" "and r18,r19\n\t" "rjmp l\n\t" "exit:\n\t" : "=r" (result) : "r" (b) : "r18", "r19" ); return result; }Я использовал. Очень давно, правда...
А я совсем недавно. Приходилось шимить 7-ми сегментник, в зависимости от кол-ва одновременно горящих сегментов.
А ещё есть вот какое чудо):
Green сдвига на нужное число бит нет в AVR - листинг будет ужасен ...
Главное что бы исходник был запутанным.)
uint8_t ones[255] = {0 , 1, 1 , 2 , 1 , 2 , ... , 8} ; uint8_t howMuchOnes(uint8_t num) { return ones[num]; }Обычно табличное преобразование. Делали и так.
А если двумя полубайтами прецтавить, длина таблицы существенно снизица.
SergeiL Чем компилировали ? (не похоже на GCC)
Очень похоже, но длиннее (реализации возврата еще не видно в листинге).
Вот вариант с обходом только единиц, 20 байт (аналог кода из #10):
uint8_t __attribute__ ((noinline)) NumOneBits(uint8_t b) { uint8_t result; asm volatile( "mov r18,%1\n\t" "clr %0\n\t" "tst r18\n\t" "l:\n\t" "breq exit\n\t" "inc %0\n\t" "mov r19,r18\n\t" "dec r19\n\t" "and r18,r19\n\t" "rjmp l\n\t" "exit:\n\t" : "=r" (result) : "r" (b) : "r18", "r19" ); return result; }Компилировал древним iccavr (от imagecraft). Билд v.7.23, аж от 2010-го года. Последний из v.7
Я им давно пользуюсь, где то с начала 2000-ных, начиная с v6. А вот версия 8 не зашла, очень тяжелая была.
Код из поста #10 компилируется так:
_NumBitsInValue: count0 --> R10 val --> R16 0003C 92AA ST -Y,R10 0003D 24AA CLR R10 0003E C004 RJMP 0x0043 (0002) { (0003) unsigned char count; (0004) (0005) for(count=0;val;count++) (0006) val &= val-1; 0003F 2F80 MOV R24,R16 00040 5081 SUBI R24,1 00041 2308 AND R16,R24 00042 94A3 INC R10 00043 2300 TST R16 00044 F7D1 BNE 0x003F (0007) return count; 00045 2D0A MOV R16,R10 00046 90A9 LD R10,Y+ 00047 9508 RETУ ICCAVR с давних времен есть очень удобная штука "Application Builder"
Выбираем кристалл частоту, порты, и т.д.
Приложение генерит код, который можно править, не залезая в даташит.
ICC Генерит код:
//ICC-AVR application builder : 13.04.2022 22:54:37 // Target : T13 // Crystal: 0.1280Mhz #include <iot13v.h> #include <macros.h> void port_init(void) { PORTB = 0x00; DDRB = 0x18; } //Watchdog initialize // prescale: 128K void watchdog_init(void) { WDR(); //this prevents a timout on enabling WDTCR = 0x0E; //WATCHDOG ENABLED - dont forget to issue WDRs } //TIMER0 initialize - prescale:1024 // WGM: Normal // desired value: 1Hz // actual value: 1,000Hz (0,0%) void timer0_init(void) { TCCR0B = 0x00; //stop OCR0A = 0x7D; OCR0B = 0x7D; TCNT0 = 0x83; //set count TCCR0A = 0x00; TCCR0B = 0x05; //start timer } #pragma interrupt_handler timer0_ovf_isr:iv_TIM0_OVF void timer0_ovf_isr(void) { TCNT0 = 0x83; //reload counter value } //call this routine to initialize all peripherals void init_devices(void) { //stop errant interrupts until set up CLI(); //disable all interrupts port_init(); watchdog_init(); timer0_init(); MCUCR = 0x00; TIMSK0 = 0x02; //timer interrupt sources GIMSK = 0x00; //interrupt sources SEI(); //re-enable interrupts //all peripherals are now initialized } // void main(void) { init_devices(); //insert your functional code here... }Не, не очень. У CodevisionAVR Wizard начиная с v.3 генерит с наименованиями битов.
Есть и отдельные утилиты, типа AvrWiz. Чего только не выдумают для ленивцев.)