Выбор последовательности побитовых операций

Если я правильно понял вашу постановку задачи, это очень похоже на русское крестьянское умножение. Учтите, что случайно сгенерированный long будет иметь каждый бит независимым и каждый бит установлен с вероятностью 50%. Предположим (ради рекурсии) у нас есть желаемая функция f(p); затем

rand()       gives the same distribution as f(0.5)
f(p) & f(q)  gives the same distribution as f(p*q)
f(p) | f(q)  gives the same distribution as f(p + q - p*q)

Итак, предположим, мы ищем f(0.9). Мы знаем это

f(0.9) = f(0.5) | f(x) where 0.5 + x - 0.5*x = 0.9, i.e. 0.5x = 0.4

Итак, теперь мы ищем f(0.8). Мы знаем это

f(0.8) = f(0.5) | f(x) where 0.5x = 0.3
f(0.6) = f(0.5) | f(x) where 0.5x = 0.1
f(0.2) = f(0.5) & f(x) where 0.5x = 0.2
f(0.4) = f(0.5) & f(x) where 0.5x = 0.4
f(0.8) = f(0.5) | f(x) where 0.5x = 0.3
[...]

Эта рекурсия никогда не завершится; но в любой момент мы можем достичь дна и начать перематывать стек.

f(0.9) = R | R | (R & R & (R | R | (R & R & ...)))

Например, этот код на C дает распределение, чертовски близкое к p=0,9:

#define R (rand() % 256)
unsigned get09() {
  unsigned x = R;  // 0.5
  x |= R; // 0.75      
  x |= R; // 0.875
  x &= R; // 0.4375     
  x &= R; // 0.21875
  x |= R; // 0.609375
  x |= R; // 0.8046875
  x |= R; // 0.90234375
  return x;
}

Теперь, могли бы вы стать еще ближе, используя продукцию, отличную от непосредственного использования R — например, можем ли мы использовать тот факт, что f(0.9) = f(0.684) | f(0.684), а затем искать способы производства f(0.684)? Конечно.

Возможно, это эффект Баадера-Мейнхофа в действии, но на самом деле (по счастливой случайности!) это похоже на проблему «кратчайшего пути» направленного гиперграфа, сродни https://mathoverflow.net/questions/466176/what-is -подходящее-имя-для-этой-самой-самой-проблемы-пути-в-бесконечном-крафте — см. https://quuxplusone.github.io/blog/2024/03/03/infinite-craft-theory / и Кнут Том 2 §4.6.3 «Оценка степеней» для некоторой теории. Мы ищем кратчайший путь от $V_0 = {0.5}$ до p, используя операцию $E$, которая на самом деле представляет собой две возможные операции: & и |. Таким образом, от {0,5} мы можем достичь любого из {0,5, 0,25, 0,75} за один шаг; мы можем достичь любого из {0,5, 0,25, 0,75, 0,125, 0,625, 0,375, 0,875, 0,1875, 0,8125} за два шага; и так далее; и вы просто хотите знать, сколько шагов пройдет, прежде чем мы достигнем некоторого числа в пределах определенного эпсилона p.

Обновлено: Мне пришло в голову, что эти цели гораздо лучше представлены в базе 2, а не в базе 10. Из {0,1} (база 2) мы можем достичь любого из {0,1, 0,01, 0,11} за один шаг; любой из {0,1, 0,01, 0,11, 0,001, 0,101, 0,011, 0,111, 0,0011, 0,1101} в два этапа; и так далее. Конечно, будет невозможно достичь любого p, двоичное представление которого имеет бесконечное количество 1-битов (например, p=0,9=0,1110011001...₂); но мы можем подобраться сколь угодно близко.

И это действительно похоже на то, что общее решение состоит в том (как и в случае с русским крестьянским умножением) записать цель в двоичном формате; затем превратите 1 в |s, а 0 в &s. Например, чтобы получить p=0,7⏨, что равно 0,101100111...₂, мы напишем это, где при чтении снизу вверх побитовые операции будут такими: |&||&&|||... Каждая побитовая операция с 0,5₁₀ добавляет к результату еще один ведущий бит. .

#define R (rand() % 256)
unsigned get07() {
  unsigned x = R | R;  // 0.11
  x |= R; // 0.111
  x &= R; // 0.0111    
  x &= R; // 0.00111
  x |= R; // 0.100111
  x |= R; // 0.1100111
  x &= R; // 0.01100111
  x |= R; // 0.101100111
  return x;
} 

Обратите внимание, что (как и в случае с цепочками сложения) метод русского крестьянина не всегда дает самое краткое решение. Например, чтобы получить 0,5675₁₀ = 0,1001₂ (Годболт):

unsigned russianPeasant() { return (R & R & R) | R; }
unsigned butILikeThis()   { return (R | R) & (R | R); }