c++ - Incremento de bitsets ''enmascarados''

bit-manipulation intrinsics

Question

Actualmente estoy en el proceso de escribir un enumerador de árbol donde me encuentro con el siguiente problema:

Estoy mirando conjuntos de bits enmascarados, es decir, conjuntos de bits donde los bits de conjunto son un subconjunto de una máscara, es decir, 0000101 con la máscara 1010101 . Lo que quiero lograr es incrementar el conjunto de bits, pero solo con respecto a los bits enmascarados. En este ejemplo, el resultado sería 0010000 . Para hacerlo un poco más claro, extraiga solo los bits enmascarados, es decir, 0011 , increméntelos a 0100 y 0010000 nuevamente a los bits de máscara, dando 0010000 .

¿Alguien ve una manera eficiente de hacer esto, sin implementar la operación a mano utilizando una combinación de escaneos de bits y máscaras de prefijo?

Answer 1

Si bien no es intuitivo en comparación con la respuesta aceptada, esto funciona en solo 3 pasos:

x = -(x ^ mask) & mask;

Esto se puede verificar según lo sugerido por zch:

 -(x ^ mask)
= ~(x ^ mask) + 1 // assuming 2''s complement
= (x ^ ~mask) + 1
= (x | ~mask) + 1 // since x and ~mask have disjoint set bits

Entonces se vuelve equivalente a la respuesta aceptada.

Answer 2

Si el orden de iteración no es tan importante y una operación de disminución satisfará sus necesidades, es posible usar solo dos operaciones:

Empecemos con

x = mask

y obtener valor anterior con

x = (x - 1) & mask

x - 1 parte cambia el último bit distinto de cero a cero y establece todos los bits menos significativos a 1. Luego, la parte de & mask solo deja fragmentos de máscara entre ellos.

Answer 3

Simplemente llene los bits sin máscara con unos para que propaguen carry:

// increments x on bits belonging to mask
x = ((x | ~mask) + 1) & mask;