Crazy_Shrike Member Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору Вопросы по программированию на C/С++   Справочники, книги Выбор IDE (среды программирования)   Постарайтесь дать как можно больше информации о возникшей проблеме - это в конце концов в ваших же интересах чтобы вам помогли. Решения конкретных задач собираются и обсуждаются в теме Задачи по C/С++ . Прежде чем просить помощи в задании... Если позарез надо и вы даже готовы заплатить Как правильно задавать вопросы, если вы хотите получить ответ. Полезные ссылки: C++(eng) Всего записей: 241 | Зарегистр. 25-03-2004 | Отправлено: 13:37 06-05-2004 | Исправлено: AZJIO, 19:45 12-05-2014

V0lt_r Advanced Member Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору Пожалуйста, подскажите простой алгоритм проверки наличия одного единственного бита в 32 битном числе. Ну чтобы проще подсчета всех битов был. Всего записей: 722 | Зарегистр. 15-11-2015 | Отправлено: 22:32 19-09-2016

V0lt_r Advanced Member Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору zedxxxx Неа. Нужно проверить наличие любого бита, но чтобы он был в единственом экземпляре. Можно конечно цикл зарядить, но вдруг есть алгоритм типа такого Код: /**  * Count number of bits set to one in x  * @param x value to count bits of  * @return the number of bits set to one in x  */ static av_always_inline av_const int av_popcount_c(uint32_t x) {     x -= (x >> 1) & 0x55555555;     x = (x & 0x33333333) + ((x >> 2) & 0x33333333);     x = (x + (x >> 4)) & 0x0F0F0F0F;     x += x >> 8;     return (x + (x >> 16)) & 0x3F; } но для одного бита. Всего записей: 722 | Зарегистр. 15-11-2015 | Отправлено: 07:04 20-09-2016 | Исправлено: V0lt_r, 07:05 20-09-2016

Aleksoid1978 Gold Member Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору V0lt_r Тебе нужно что именно - проверить наличие конкретного бита или еще проверить что только этот бит выставлен в 1(а остальные в 0) ?? ---------- AMD Ryzen 5 3600 /GIGABYTE B450 Gaming X /Patriot 32Gb@3200 /Kingston 500Gb M.2 /RTX 4060 /Samsung U28R550UQI /OLED Philips 55OLED707 /Yamaha RX-V471 + NS-555 + NS-C444 + NS-333 + YST-SW215 Всего записей: 9225 | Зарегистр. 11-05-2006 | Отправлено: 04:54 21-09-2016

V0lt_r Advanced Member Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору RedLord Не понял.   Aleksoid1978 Да. Типа задачка, как определить единственный бит с минимумом операций.   Пока самое простое: Код: uint32_t X =...; bool one-bit = (av_popcount_c(X) == 1); функция av_popcount_c описана сообщением выше. Всего записей: 722 | Зарегистр. 15-11-2015 | Отправлено: 09:11 21-09-2016

V0lt_r Advanced Member Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору akaGM Бит там не конкретный, а любой. Я же простое решение привел, в котором сначала считаем все биты, а потом проверяем равно ли колличество 1.   Добавлено: Цитата: и каков критерый? Хорошо. Сделать быстрее или короче чем Код: int popcount(uint32_t x) {     x -= (x >> 1) & 0x55555555;     x = (x & 0x33333333) + ((x >> 2) & 0x33333333);     x = (x + (x >> 4)) & 0x0F0F0F0F;     x += x >> 8;     return (x + (x >> 16)) & 0x3F; }   int main() {     uint32_t X = rand();     return (popcount(X) == 1); } Всего записей: 722 | Зарегистр. 15-11-2015 | Отправлено: 16:58 21-09-2016 | Исправлено: V0lt_r, 17:08 21-09-2016

Aleksoid1978 Gold Member Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору V0lt_r https://msdn.microsoft.com/en-us/library/bb385231.aspx для SSE4.2 тоже есть https://blogs.msdn.microsoft.com/vcblog/2007/10/18/new-intrinsic-support-in-visual-studio-2008/   Можешь сравнить скорость выполнения того кода что у тебя есть и тех же __popcnt...   Добавлено: Вот можно так, с использованием инструкций: Код:   static int popcount(unsigned x) {     x -= (x >> 1) & 0x55555555;     x = (x & 0x33333333) + ((x >> 2) & 0x33333333);     x = (x + (x >> 4)) & 0x0F0F0F0F;     x += x >> 8;     return (x + (x >> 16)) & 0x3F; }     static int bitcnt(unsigned x) {     std::bitset<32> ECX;     int cpuInfo[4] = { 0 };     __cpuid(cpuInfo, 1);     ECX = cpuInfo[2];     const bool SSE42  = ECX[20];     const bool POPCNT = ECX[23];       if (POPCNT) {         if (SSE42) {             return _mm_popcnt_u32(x);         }           return __popcnt(x);     }       return popcount(x); }     конечно же код по определению SSE42 и POPCNT вынести отдельно в статические переменные. ---------- AMD Ryzen 5 3600 /GIGABYTE B450 Gaming X /Patriot 32Gb@3200 /Kingston 500Gb M.2 /RTX 4060 /Samsung U28R550UQI /OLED Philips 55OLED707 /Yamaha RX-V471 + NS-555 + NS-C444 + NS-333 + YST-SW215 Всего записей: 9225 | Зарегистр. 11-05-2006 | Отправлено: 07:38 23-09-2016 | Исправлено: Aleksoid1978, 07:39 23-09-2016

Aleksoid1978 Gold Member Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору Сравнил ради интереса скорость выполнения _mm_popcnt_u32(), __popcnt() и popcount(). На машине I7@920 цикл 10 000 000 раз(правда запускал в отладчике чтобы замерять время выполнения). _mm_popcnt_u32() и __popcnt() - одинаковые значения (ну видимо за счет того что SSE42 поддерживается то и выполняется одна и та же инструкция, так что проверка на SSE42 в коде выше - излишне) ~25-27мс, popcount() > 300мс (иногда до 400мс). ---------- AMD Ryzen 5 3600 /GIGABYTE B450 Gaming X /Patriot 32Gb@3200 /Kingston 500Gb M.2 /RTX 4060 /Samsung U28R550UQI /OLED Philips 55OLED707 /Yamaha RX-V471 + NS-555 + NS-C444 + NS-333 + YST-SW215 Всего записей: 9225 | Зарегистр. 11-05-2006 | Отправлено: 10:00 23-09-2016 | Исправлено: Aleksoid1978, 10:03 23-09-2016

Zatupitel Full Member Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору Ого как все сложно оказывается. А варианты типа: Код:  if (x & 0xFFFFFFFF > 0 ) {}   Не подойдут ?   Или все куда тяжелее ? Всего записей: 469 | Зарегистр. 31-08-2006 | Отправлено: 12:04 23-09-2016

Aleksoid1978 Gold Member Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору Zatupitel Нужно кол-во бит узнать. ---------- AMD Ryzen 5 3600 /GIGABYTE B450 Gaming X /Patriot 32Gb@3200 /Kingston 500Gb M.2 /RTX 4060 /Samsung U28R550UQI /OLED Philips 55OLED707 /Yamaha RX-V471 + NS-555 + NS-C444 + NS-333 + YST-SW215 Всего записей: 9225 | Зарегистр. 11-05-2006 | Отправлено: 12:18 23-09-2016 | Исправлено: Aleksoid1978, 13:31 23-09-2016

Zatupitel Full Member Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору Если надо кол-во бит узнать, я бы пошел другим путем. Создал бы массив из 256 значений, где для каждого значения было бы подсчитано кол-во бит. Затем, берем 32-битное число, и делим на блоки по 8 бит.   Из массива выдергиваем значения бит для каждого из 4 блоков. В итоге, время будет самым минимальным, а лишний 1к байт потраченной памяти наверное не проблема. Если памяти совсем много, то можно было бы заполнить массив не из 256 значений (FF), а скажем, 65535 (FFFF). Времени наверное много не выиграли, но чуток было бы быстрей на сотые доли. Всего записей: 469 | Зарегистр. 31-08-2006 | Отправлено: 15:46 23-09-2016 | Исправлено: Zatupitel, 15:47 23-09-2016

Aleksoid1978 Gold Member Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору Зачем придумывать велосипед - я уже, выше смотрим, привел пример. Один код "свой", другой - использование готовых инструкций, у него время выполнения самое выполнения. ---------- AMD Ryzen 5 3600 /GIGABYTE B450 Gaming X /Patriot 32Gb@3200 /Kingston 500Gb M.2 /RTX 4060 /Samsung U28R550UQI /OLED Philips 55OLED707 /Yamaha RX-V471 + NS-555 + NS-C444 + NS-333 + YST-SW215 Всего записей: 9225 | Зарегистр. 11-05-2006 | Отправлено: 16:34 23-09-2016

Zatupitel Full Member Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору Aleksoid1978 А если проц не поддерживает SSE4 ? Скажем у меня не Core 2 Duo и выше (или до 2012-2013 года выпуска ) ? Всего записей: 469 | Зарегистр. 31-08-2006 | Отправлено: 17:03 23-09-2016 | Исправлено: Zatupitel, 17:05 23-09-2016

MERCURY127 Platinum Member Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору не Си, но ответ на Цитата: Бит там не конкретный, а любой, но один как хочет V0lt_r:   __asm{ mov BX, value   bsf AX, BX   jz все-биты-в-0 mov CX, AX   mov BX, value ; возможно, лишнее bsr AX, BX   cmp AX, СX   jz только-один-бит-в-1 много-бит-в-1 }//asm достаточно процессора 386 Всего записей: 11554 | Зарегистр. 03-08-2008 | Отправлено: 17:29 23-09-2016 | Исправлено: MERCURY127, 17:30 23-09-2016

V0lt_r Advanced Member Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору RedLord, Aleksoid1978 Спасибо. Теперь понятно, что для быстрого подсчета битов для GCC можно использовать __builtin_popcount, а для MSVC __popcnt, которые будут использовать спец инструкцию процессора по возможности.   Aleksoid1978 Цитата: Нужно кол-во бит узнать. По условиям задачи этого не требуется. Просто с подсчетом нагляднее. Я же пример решения привел, где return выдает наличие единственного бита (не двух, не трех, а одного из 32-х).   MERCURY127 Спасибо, но ассемблер не понимаю, увы. Всего записей: 722 | Зарегистр. 15-11-2015 | Отправлено: 21:58 23-09-2016

Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322

Компьютерный форум Ru.Board » Компьютеры » Прикладное программирование » Вопросы по программированию на C/С++

Переход по форумам  Закладки   » Компьютеры Цифровое изображение Программы Microsoft Windows UNIX Другие OS Hardware В помощь сисадмину Прикладное программирование Игры Форумные игры   » Интернет Web-программирование В помощь вебмастеру Графика Хостинг Зацените-ка!   » Тематические Ikonboard v.2 Ikonboard v.3 Invision Board Другие форумы PHP-Nuke и другие порталы Мобила   » Общие Спорт Флейм Темы по региональным встречам Музыка и Кино Юмор Литература и Живопись   » Ru.Board Новости Помощь по форуму   » Андеграунд eBookz Варезник Раздачи и акции Мобильный варезник Андеграунд Игры и фильмы   » Специальные Тестирование