jeudi 29 novembre 2018

Uniform random bit from a mask

Suppose I have a 64 bit unsigned integer (u64) mask, with one or more bits set.

I want to select one of the set bits uniformly at random from m to give a new mask x such that x & mask has one bit set. Some pseudocode that does this might be:

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

However I need to do this as fast as possible (code similar to the above in a low-level language is slowing a hot loop). Does anyone have a more efficient scheme?




Aucun commentaire:

Enregistrer un commentaire