[whale 6]

Допустим есть случайное число байт, нужно из него получить число, в котором будет заранее определенной кол-во единиц, например 1, 2, 3

Как такое можно наиболее просто сделать ?

Также можно сформулировтаь по другому - как получить байт, в котором будет заданное кол-во бит=1 , расположенных случайном образом в байте

Изменено 18 марта, 2023 пользователем whale

[blackfin 28]

On 3/18/2023 at 6:39 PM, whale said:

как получить байт, в котором будет заданное кол-во бит=1 , расположенных случайном образом в байте

Сделать таблицу на 56 строк (если кол-во единиц равно 3) и обращаться к ней по случайному адресу.

[engel65536 12]

48 minutes ago, whale said:

как получить байт, в котором будет заданное кол-во бит=1 , расположенных случайном образом в байте

uint8_t result = 0;
for (bits_cnt = 0; bits_cnt < 3; ) {
  shift = rand() % 8;
  if ((result & (1ul << shift)) == 0) {
    result |= 1ul << shift;
    bit_cnt++;
  }
}

Генерим случайную величину сдвига, проверяем, что на этой позиции ещё не стоит 1, если не стоит - ставим и увеличиваем счётчик бит. Если вам не нужно генерить такие байты очень-очень быстро, то такое сгодится.

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

Изменено 18 марта, 2023 пользователем engel65536

[xvr 12]

Делаете массив на 8 байтов, заполняете в нём подряд нужное количество единиц, хвост заполняете нулями. Затем запукаете на него std::random_shuffle. Затем сворачиваете массив в байт.

 

Можно и сразу в байте сделать, но тогда вам придётся изобрести итератор на бит.

 

[whale 6]

3 hours ago, engel65536 said:

Генерим случайную величину сдвига

Да, такое я думал, это решение в лоб, может как то еще проще/быстрее ?

2 hours ago, xvr said:

Делаете массив на 8 байтов

Что то совсем сложно.

 

Короче надо рисовать шум в заданной области с разной плотностью на экране ssd1306 а  там ввод точек идет по столбцам в байт.

Изменено 18 марта, 2023 пользователем whale

[quark 48]

7 часов назад, whale сказал:

как получить байт, в котором будет заданное кол-во бит=1 , расположенных случайном образом в байте

Не нужно усложнять себе жизнь. Байт может содержать только одно из 256-ти возможных значений. В данном случае, метод прямого перебора наиболее эффективен.

Делаете девять массивов, для хранения значений байт:
В первом массиве - значения, где 1 единица в байте;
Во втором массиве - значения, где 2 единицы в байте;
В третьем массиве - значения, где 3 единицы в байте;
...
В девятом массиве - значения, где нет единиц в байте;

При старте программы, перебираете все значения байта по очереди, от 0 до 255. Подсчитываете количество единиц в текущем байте и отправляете его в соответствующий массив. Это делается один раз. Можно, вообще, все сделать за пределами рабочей программы, и использовать уже готовые массивы с предварительно рассчитаными элементами.

Когда вам нужно сгенерировать значение байта - берете случайный элемент из нужного массива.

[xvr 12]

13 hours ago, whale said:

Что то совсем сложно.

 

🤪

char get_rnd_byte(int total_ones)
{
	bool buf[8];
  
	for(int i=0; i<8; ++i) buf[i] = i < total_ones;
  
	std::random_shuffle(buf, buf+8);

	char result = 0;
	for(int i=0; i<8; ++i) result = (result << 1) | buf[i];
  
    return result;
}

 

13 hours ago, whale said:

Короче надо рисовать шум в заданной области с разной плотностью на экране ssd1306 а  там ввод точек идет по столбцам в байт.

При рисовании побайтно у вас шум будет полосатым 🙂. И плотность менее 1/8 сделать не получится. Генерите сразу строку (моим алгоритмом вполне можно сгенерить, хоть всю картинку сразу)

 

[jcxz 242]

20 часов назад, whale сказал:

Короче надо рисовать шум в заданной области с разной плотностью на экране

Так и надо было сразу говорить. Для такой задачи совсем не нужно формировать точное число единиц в байтах. Достаточно завести некую переменную, которая будет управлять генератором случайных чисел, повышая или понижая среднюю плотность потока единиц в числах идущих с него. И каждое полученное число - выдавать на экран, а также считать число единиц в нём и увеличивать/уменьшать нашу переменную. Тогда можно очень быстро генерировать поток случайных данных с заданным средним удельным количеством "1" в нём.

Примерно так:

enum {FILTER_ORDER = 5};   //значение порядка фильтра - подобрать
u32 j = N << FILTER_ORDER; //начальное значение управляющей переменной; где: N - среднее требуемое кол-во единиц в слове
uint n = размер_видеобуфера_в_словах;
do {
  u32 i = funcRnd(j);  //функция генерит случайное число, со средней вероятностью "1" == (j >> FILTER_ORDER)
  вывод_пачки_точек_на_экран(i);
  i = функция_подсчитывающая_число_единиц_в_слове(i);
  j += i - (j >> FILTER_ORDER);
} while (--n);

Обратная связь будет всегда тянуть скользящий фильтр к идеальному == (N << FILTER_ORDER), плавно регулируя количество "1" в выводе.

funcRnd() тут не обязана генерить жёстко заданное число единиц. Достаточно чтобы просто число единиц в её выводе росло с уменьшением аргумента; и падало с его ростом. Это сделать нетрудно.

 

PS: А попытки фиксировать число единиц в байте фиксированным значением, приведут к полосатости на экране. Как уже выше заметили.

[whale 6]

1 hour ago, jcxz said:

А попытки фиксировать число единиц в байте фиксированным значением, приведут к полосатости

Не пойму откуда полосатость ?

Забыл сказать что точки не желательно объединять, те чтобы между точками была по меньшей мере одна нулевая точка.

По моему вариант с массивом самый быстрый и прозрачный. 

9 hours ago, xvr said:

Генерите сразу строку

Попробую хотя срока там от 1 столбца до 128, меняется.

 

ps хотя да, наверно будет некая полосатость, особено если будет по одной единице в байте.

 

Упростим  задачу, 

есть часть строки из n байт (от 1 - 128), те массив из n байт, каждый бит в котором отображает точку.

нужно в этот массив байт записать белый шум, 

потом весь массив тупо выводим на дисплей.

 

Изменено 19 марта, 2023 пользователем whale

[xvr 12]

14 hours ago, whale said:

те чтобы между точками была по меньшей мере одна нулевая точка.

Тогда макисмальный коэфициент заполнения - 50%

14 hours ago, whale said:

нужно в этот массив байт записать белый шум, 

 

Мой алгоритм (только надо убрать промежуточный массив и сразу работать на массиве битов) или алгоритм от jcxz

[whale 6]

6 hours ago, xvr said:

Тогда макисмальный коэфициент заполнения - 50%

Мой алгоритм (только надо убрать промежуточный массив и сразу работать на массиве битов) или алгоритм от jcxz

Решу проблеммы с прерыванием и попробую.

Изменено 20 марта, 2023 пользователем whale

[_pv 79]

вот массив отсортированный по возрастанию количества 1 в байте.

const series[256] = {0, 1, 2, 4, 8, 16, 32, 64, 128, 3, 5, 6, 9, 10, 12, 17, 18, 20, 24, 33, 34, 36, 40, 48, 65, 66, 68, 72, 80, 96, 129, 130, 132, 136, 144, 160, 192, 7, 11, 13, 14, 19, 21, 22, 25, 26, 28, 35, 37, 38, 41, 42, 44, 49, 50, 52, 56, 67, 69, 70, 73, 74, 76, 81, 82, 84, 88, 97, 98, 100, 104, 112, 131, 133, 134, 137, 138, 140, 145, 146, 148, 152, 161, 162, 164, 168, 176, 193, 194, 196, 200, 208, 224, 15, 23, 27, 29, 30, 39, 43, 45, 46, 51, 53, 54, 57, 58, 60, 71, 75, 77, 78, 83, 85, 86, 89, 90, 92, 99, 101, 102, 105, 106, 108, 113, 114, 116, 120, 135, 139, 141, 142, 147, 149, 150, 153, 154, 156, 163, 165, 166, 169, 170, 172, 177, 178, 180, 184, 195, 197, 198, 201, 202, 204, 209, 210, 212, 216, 225, 226, 228, 232, 240, 31, 47, 55, 59, 61, 62, 79, 87, 91, 93, 94, 103, 107, 109, 110, 115, 117, 118, 121, 122, 124, 143, 151, 155, 157, 158, 167, 171, 173, 174, 179, 181, 182, 185, 186, 188, 199, 203, 205, 206, 211, 213, 214, 217, 218, 220, 227, 229, 230, 233, 234, 236, 241, 242, 244, 248, 63, 95, 111, 119, 123, 125, 126, 159, 175, 183, 187, 189, 190, 207, 215, 219, 221, 222, 231, 235, 237, 238, 243, 245, 246, 249, 250, 252, 127, 191, 223, 239, 247, 251, 253, 254, 255}

const idx[9][2] = {{0, 0}, {1, 8}, {9, 36}, {37, 92}, {93, 162}, {163, 218}, {219, 246}, {247, 254}, {255, 255}};

series[random(idx[n][0], idx[n][1])]

даст случайное число с n единицами

 

[whale 6]

7 hours ago, _pv said:

даст случайное число с n единицами

Спасибо, интересно, попробую.