Explicación de un algoritmo para establecer, borrar y probar un solo bit

Question

Oye, en el libro Programming Pearls, hay un código fuente para configurar, borrar y probar un bit del índice dado en una matriz de entradas que en realidad es un establecer representación

El código es el siguiente:

#include<stdio.h> 
#define BITSPERWORD 32 
#define SHIFT 5 
#define MASK 0x1F 
#define N 10000000 

int a[1+ N/BITSPERWORD]; 

void set(int i) 
{ 
    a[i>>SHIFT] |= (1<<(i & MASK)); 
} 

void clr(int i) 
{ 
    a[i>>SHIFT] &= ~(1<<(i & MASK)); 
} 

int test(int i) 
{ 
    a[i>>SHIFT] & (1<<(i & MASK)); 
} 

Podría alguien explicar la razón del cambio y los define máscara? ¿Y cuáles son sus propósitos en el código?

Ya he leído el question relacionado con anterioridad.

Answer 1

VonC ha publicado una respuesta buena sobre bitmasks en general. Aquí hay información que es más específica del código que publicaste.

Dado un número entero que representa un poco, calculamos qué miembro de la matriz contiene ese bit. Es decir: los bits 0 a 31 viven en a[0], los bits 32 a 63 viven en a[1], etc. Todo lo que hace i>>SHIFT es i/32. Esto resuelve qué miembro de a vive el bit. Con un compilador de optimización, estos son probablemente equivalentes.

Obviamente, ahora que hemos descubierto qué miembro de a vive esa marca de bit, debemos asegurarnos de establecer el bit correcto en ese entero. Esto es lo que 1 << i hace. Sin embargo, debemos asegurarnos de que no intentemos acceder al bit 33 en un entero de 32 bits, por lo que la operación de cambio está restringida mediante el uso de 1 << (i & 0x1F). La magia aquí es que 0x1F es 31, por lo que nunca vamos a desplazar hacia la izquierda el bit representado por i más de 31 lugares (de lo contrario debería haber ido en el siguiente miembro de a).

Answer 2

De Here (respuesta general para conseguir este hilo iniciado)

Una máscara de bits es un valor (que puede ser almacenado en una variable) que le permite aislar un conjunto específico de bits dentro de un tipo entero.

Normalmente, el enmascarado tendrá los bits que le interesan establecidos en 1 y todos los demás bits en 0. La máscara le permite aislar el valor de los bits, borrar todos los bits o establecer todos los bits o establecer un nuevo valor para los bits.

Las máscaras (particularmente las de varios bits) a menudo tienen un valor de desplazamiento asociado que es la cantidad que los bits necesitan desplazarse hacia la izquierda para que el bit enmascarado menos significativo se desplace al bit menos significativo del tipo.

Por ejemplo, utilizando un tipo de datos cortos de 16 bits, suponga que desea poder enmascarar los bits 3, 4 y 5 (LSB es el número 0). Enmascara y el cambio sería algo como

#define MASK 0x0038 
#define SHIFT 3 

máscaras son a menudo asignados en hexadecimal, ya que es más fácil trabajar con bits en el tipo de datos en esa base en contraposición a decimal. Históricamente octal también se ha usado para máscaras de bits.

Si tengo una variable, var, que contiene datos que la máscara es relevante para entonces puedo aislar los bits como esto

var & MASK 

puedo aislar a todos los otros bits como esto

var & ~MASK 

puedo borrar los bits como esto

var &= ~MASK; 

puedo borrar todos los otros bits como esto

var &= MASK; 

puedo configurar todos los bits como este

var |= MASK; 

I pueden establecer todos los otros bits como este

var |= ~MASK; 

puedo extraer el valor decimal de los bits como este

(var & MASK) >> SHIFT 

Puedo asignar un nuevo valor para los bits como este

var &= ~MASK; 
var |= (newValue << SHIFT) & MASK; 

Answer 3

cuando se quiere establecer un bit dentro de la matriz, usted tiene que

1. buscan el índice de la derecha y
2. establece el bit apropiado dentro de este elemento de la matriz.

Hay BITSPERWORD (= 32) bits en un elemento de la matriz, lo que significa que el índice de i tiene que ser dividido en dos partes:

• más a la derecha 5 bits sirven como un índice en el elemento de la matriz y
• el resto de los bits (el extremo izquierdo 28) sirven como un índice en la matriz.

que se obtiene:

• los 28 bits de la izquierda descartando los cinco más a la derecha, que es exactamente lo i>>SHIFT hace, y
• los cinco bits de la derecha enmascarando a cabo cualquier cosa menos los cinco bits más a la derecha, que es lo que i & MASK hace.

Supongo que usted entiende el resto.

Answer 4

Bitwise operation y los párrafos iniciales de Mask son una explicación concisa, y contienen algunos indicadores para un estudio posterior.

Piense en un byte de 8 bits como un conjunto de elementos de un universo de 8 miembros. Un miembro es EN el conjunto cuando se establece el bit correspondiente. Establecer un poco más de una vez no modifica set membership (un bit puede tener solo 2 estados). El bitwise operators en C proporciona acceso a bits por enmascaramiento y cambiando.

Answer 5

El código está tratando de almacenar N bits por una matriz, donde cada elemento de la matriz contiene BITSPERWORD (32) bits.

Por lo tanto, si intenta acceder al bit i, necesita calcular el índice del elemento de matriz que lo almacena (i/32), que es lo que i>>SHIFT hace.

Y luego necesita acceder a ese bit en el elemento de matriz que acabamos de obtener.

(i & MASK) da la posición del bit en el elemento de la matriz (palabra). (1<<(i & MASK)) hace que se establezca el bit en esa posición.

Ahora puede establecer/borrar/probar ese bit en a[i>>SHIFT] por (1<<i & MASK)).

También puede pensar que i es un número de 32 bits, que los bits 6 ~ 31 son el índice del elemento de matriz que lo almacena, los bits 0 ~ 5 representan la posición del bit en la palabra.