¿Necesita una manera de recoger un poco común en dos máscaras de bits al azar

Question

Imaginemos dos máscaras de bits, sólo voy a usar 8 bits por simplicidad:

01101010 
10111011 

El 2º, 4º, 6º y bits son ambos 1. I desea elegir uno de esos bits "en" comunes al azar. Pero quiero hacer esto en O (1).

La única forma que he encontrado de hacer esto hasta ahora es elegir un bit aleatorio "encendido" en uno, luego verificar el otro para ver si también está activado, luego repetir hasta encontrar una coincidencia. Esto sigue siendo O (n), y en mi caso la mayoría de los bits están desactivados en ambas máscaras. Lo hago, por supuesto, & juntos para verificar inicialmente si hay bits comunes en absoluto.

¿Hay alguna manera de hacerlo? Si es así, puedo aumentar la velocidad de mi función en alrededor del 6%. Estoy usando C# si eso importa. ¡Gracias!

Mike

Answer 1

Si está dispuesto para tener una solución de O (lg n), a costa de una probabilidad posiblemente no uniforme, de forma recursiva un medio de división, es decir, y con la mitad superior de los bits puestos y la mitad inferior conjunto. Si ambos son distintos de cero, elija uno al azar, de lo contrario, elija el que no sea cero. Luego divide a la mitad lo que queda, etc. Esto tomará 10 comparaciones para un número de 32 bits, tal vez no los pocos que te gustaría, pero mejor que 32.

Puedes ahorrar unos pocos y eligiendo y con la alta mitad o mitad baja al azar, y si no hay hits que tomen la otra mitad, y si hay hits que tomen la mitad probada.

El número aleatorio solo debe generarse una vez, ya que solo está utilizando un bit en cada prueba, simplemente cambie el bit usado cuando haya terminado con él.

Si tiene muchos bits, esto será más eficiente. Sin embargo, no veo cómo puedes llegar a O (1).

Por ejemplo, si tiene un número de 32 bits primero y la combinación anded con 0xffff0000 o 0x0000ffff si el resultado es distinto de cero (digamos que anded con 0xffff0000) conitinue con 0xff000000 de 0x00ff0000, y así sucesivamente hasta llegar a un bit. Esto termina siendo un código tedioso. 32 bits tiene 5 capas de código.

Answer 2

Creo que, si quieres uniforme, entonces la respuesta tendrá que ser Theta(n) en términos del número de bits, si tiene que funcionar para todas las combinaciones posibles.

El siguiente fragmento de código C++ (robados) debe ser capaz de verificar si los hubiere dado num es una potencia de 2.

if (!var || (var & (var - 1))) { 
     printf("%u is not power of 2\n", var); 
    } 
    else { 
     printf("%u is power of 2\n", var); 
    } 

Answer 3

¿Quieres una distribución aleatoria uniforme? Si es así, no veo una buena manera de contar los bits y luego seleccionar uno al azar, o seleccionar bits aleatorios hasta que llegue a uno que esté configurado.

Si no se preocupan por el uniforme, se puede seleccionar un conjunto de bits de una palabra al azar con:

unsigned int pick_random(unsigned int w, int size) { 
    int bitpos = rng() % size; 
    unsigned int mask = ~((1U << bitpos) - 1); 
    if (mask & w) 
     w &= mask; 
    return w - (w & (w-1)); 
} 

donde rng() es su generador de números aleatorios, w es la palabra que desea elegir y size es el tamaño relevante de la palabra en bits (que puede ser el tamaño de palabras de la máquina, o puede ser menor siempre que no establezca los bits superiores de la palabra. Entonces, para su ejemplo, use pick_random(0x6a & 0xbb, 8) o lo que sea valores que te gustan

Answer 4

Esta función selecciona aleatoriamente un bit que es alto en ambas máscaras. Si hay no hay bits posibles para elegir, se devuelve cero en su lugar. El tiempo de ejecución es O (n), donde n es el número de bits altos en las máscaras anded. Entonces, si tiene un bajo número de bits altos en sus máscaras, esta función podría ser más rápida, incluso si el peor de los casos es O (n), que ocurre cuando todos los bits son altos. La implementación en C es el siguiente:

unsigned int randomMasksBit(unsigned a, unsigned b){ 
    unsigned int i = a & b; // Calculate the bits which are high in both masks. 
    unsigned int count = 0 
    unsigned int randomBit = 0; 
    while (i){ // Loop through all high bits. 
     count++; 
     // Randomly pick one bit from the bit stream uniformly, by selecting 
     // a random floating point number between 0 and 1 and checking if it 
     // is less then the probability needed for random selection. 
     if ((rand()/(double)RAND_MAX) < (1/(double)count)) randomBit = i & -i; 
     i &= i - 1; // Move on to the next high bit. 
    } 
    return randomBit; 
} 

Answer 5

O (1) con una distribución uniforme (o lo más uniforme ofrece generador aleatorio) se puede hacer, dependiendo de si se cuenta determinada operación matemática como O (1). Como regla, lo haríamos, aunque en el caso del ajuste de bits uno podría argumentar que no lo son.

El truco es que, si bien es fácil obtener el bit más bajo y obtener el bit más alto, para tener una distribución uniforme, tenemos que elegir al azar un punto de partición, y luego elegir aleatoriamente si vamos a ir para el bit más alto debajo de él o el bit más bajo de arriba (probando el otro enfoque si eso devuelve cero).

He reducido esto un poco más de lo normal para permitir que los pasos se sigan más fácilmente. La única pregunta sobre el tiempo constante que puedo ver es si Math.Pow y Math.Log deben considerarse O (1).

Por lo tanto:

public static uint FindRandomSharedBit(uint x, uint y) 
{//and two nums together, to find shared bits. 
    return FindRandomBit(x & y); 
} 
public static uint FindRandomBit(uint val) 
{//if there's none, we can escape out quickly. 
    if(val == 0) 
    return 0; 
    Random rnd = new Random(); 
    //pick a partition point. Note that Random.Next(1, 32) is in range 1 to 31 
    int maskPoint = rnd.Next(1, 32); 
    //pick which to try first. 
    bool tryLowFirst = rnd.Next(0, 2) == 1; 
    // will turn off all bits above our partition point. 
    uint lowerMask = Convert.ToUInt32(Math.Pow(2, maskPoint) - 1); 
    //will turn off all bits below our partition point 
    uint higherMask = ~lowerMask; 
    if(tryLowFirst) 
    { 
    uint lowRes = FindLowestBit(val & higherMask); 
    return lowRes != 0 ? lowRes : FindHighestBit(val & lowerMask); 
    } 
    uint hiRes = FindHighestBit(val & lowerMask); 
    return hiRes != 0 ? hiRes : FindLowestBit(val & higherMask); 
} 
public static uint FindLowestBit(uint masked) 
{         //e.g 00100100 
    uint minusOne = masked - 1;  //e.g. 00100011 
    uint xord = masked^minusOne; //e.g. 00000111 
    uint plusOne = xord + 1;  //e.g. 00001000 
    return plusOne >> 1;   //e.g. 00000100 
} 
public static uint FindHighestBit(uint masked) 
{ 
    double db = masked; 
    return (uint)Math.Pow(2, Math.Floor(Math.Log(masked, 2))); 
} 

Answer 6

Esto no puede hacerse en O (1), y cualquier solución para un número fijo de N bits (a menos que sea totalmente realmente ridículamente estúpida) tendrá una constante límite superior, para que N.

Answer 7

Si tiene pocos bits suficiente para preocuparse, puede obtener O (1) usando una tabla de consulta:

var lookup8bits = new int[256][] = { 
    new [] {}, 
    new [] {0}, 
    new [] {1}, 
    new [] {0, 1}, 
    ... 
    new [] {0, 1, 2, 3, 4, 5, 6, 7} 
}; 

de no ser así, se puede encontrar el bit menos significativo de un número x con (x & -x), asumiendo el complemento 2s. Por ejemplo, si x = 46 = 101110b, entonces -x = 111 ... 111010010b, por lo tanto x & -x = 10. Puede usar esta técnica para enumerar los bits establecidos de x en el tiempo O (n), donde n es el número de bits establecidos en x.

Tenga en cuenta que calcular un número pseudoaleatorio llevará un lote más largo que el de enumerar los bits establecidos en x!