Единый случайный бит из маски

Question

Предположим, у меня есть 64-разрядное целое число без знака (u64) mask, с одним или несколькими установленными битами.

Я хочу выбрать один из установленных битов случайным образом из m, чтобы получитьновая маска x такая, что x & mask имеет один установленный бит.Некоторый псевдокод, который делает это, может быть:

def uniform_random_bit_from_mask(mask):
  assert mask > 0
  set_indices = get_set_indices(mask)
  random_index = uniform_random_choice(set_indices)
  new_mask = set_bit(random_index, 0)
  return new_mask

Однако мне нужно сделать это как можно быстрее (код, подобный приведенному выше на низкоуровневом языке, замедляет горячий цикл).У кого-нибудь есть более эффективная схема?

Answer 1

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

В большинстве современных архитектур есть инструкция для подсчета количества установленных битов в целом числе,обычно называется «popcount», и эта инструкция предоставляется на большинстве языков низкого уровня.В Rust вы можете использовать count_ones() метод .Это дает вам общее число k битов для выбора.

Затем вы можете сгенерировать случайное число i между 0 и k - 1 (включительно).Следующим шагом является выбор i-го установленного бита в mask.Эффективным подходом для этого является такой цикл (код Rust):

for _ in 0..i {
    mask &= mask - 1;
}
let new_mask = 1 << mask.trailing_zeros();

Цикл очищает младший значащий установленный бит в каждой итерации.Поскольку i < k, мы знаем, что mask не может быть нулем после цикла.Последняя строка генерирует новую маску из младшего значащего бита mask, который все еще установлен.

В обычных архитектурах, вероятно, узким местом будет генератор случайных чисел.Если вы используете rand ящик Rust, вы можете использовать SmallRng для повышения производительности за счет криптографической небезопасности, что может не иметь отношения к вашему варианту использования.