Ayúdeme a entender este programa "bits perlas de programación"

Question

Jon Bentley en la Columna 1 de sus perlas de programación de libros introduce una técnica para clasificar una secuencia de enteros positivos distintos de cero utilizando vectores de bits.

yo he tomado el programa bitsort.c de here y pegado a continuación:

/* Copyright (C) 1999 Lucent Technologies */ 
/* From 'Programming Pearls' by Jon Bentley */ 

/* bitsort.c -- bitmap sort from Column 1 
* Sort distinct integers in the range [0..N-1] 
*/ 

#include <stdio.h> 

#define BITSPERWORD 32 
#define SHIFT 5 
#define MASK 0x1F 
#define N 10000000 

int a[1 + N/BITSPERWORD]; 

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

int main() 
{ int i; 
for (i = 0; i < N; i++) 
    clr(i); 

    /*Replace above 2 lines with below 3 for word-parallel init 
    int top = 1 + N/BITSPERWORD; 
    for (i = 0; i < top; i++) 
    a[i] = 0; 
    */ 

while (scanf("%d", &i) != EOF) 
    set(i); 
for (i = 0; i < N; i++) 
     if (test(i)) 
    printf("%d\n", i); 
return 0; 
} 

entiendo lo que el CLR funciones, ajuste y prueba están haciendo y las explican a continuación: (por favor, corríjanme si estoy mal aquí).

• CLR borra el bit i
• conjunto establece el bit i
• prueba devuelve el valor en el bit i

Ahora, yo no entiendo como lo hacen las funciones de lo que hacen . No puedo entender toda la manipulación de bit que ocurre en esas tres funciones.

Por favor ayuda.

Answer 1

Las primeras 3 constantes están interrelacionadas. BITSPERWORD es 32. Esto lo querrá establecer en función de su compilación + arquitectura. SHIFT es 5, porque 2^5 = 32. Finalmente, MASK es 0x1F que es 11111 en binario (es decir: los 5 bits inferiores están todos configurados). Equivalentemente, MASK = BITSPERWORD - 1.

El conjunto de bits es conceptualmente solo una matriz de bits. Esta implementación realmente usa una matriz de ints, y asume 32 bits por int. Así que cada vez que queremos establecer, borrar o de prueba (leer) un poco tenemos que averiguar dos cosas:

• cuales int (de la matriz) es en
• cuál de los bits de ese int estamos hablando aproximadamente

Dado que asumimos 32 bits por int, podemos dividir por 32 (y truncar) para obtener el índice de matriz que queremos. Dividir por 32 (BITSPERWORD) es lo mismo que cambiar a la derecha por 5 (SHIFT). De eso se trata el bit a [i >> SHIFT]. También podría escribir esto como [i/BITSPERWORD] (y de hecho, probablemente obtenga el mismo código o un código muy similar suponiendo que su compilador tenga un optimizador razonable).

Ahora que sabemos qué elemento queremos, debemos determinar qué bit. Realmente, queremos el resto. Podríamos hacer esto con i% BITSPERWORD, pero resulta que i & MASK es equivalente. Esto se debe a que BITSPERWORD es una potencia de 2 (2^5 en este caso) y MASK está en la parte inferior de 5 bits.

Answer 2

Básicamente es un cubo tipo optimizado:

• reserva una matriz de bits de longitud n bits.
• borra la matriz de bits (primero para en main).
• lea los artículos uno por uno (todos deben ser distintos).
  • establece el i-ésimo bit en la matriz de bits si el número de lectura es i.
• iterar la matriz de bits.
  • si el bit está configurado, imprima la posición.

O en otras palabras (por N < 10 y para ordenar 3 números 4, 6, 2) 0

comienzo con una matriz de 10 bits vacío (también conocido como un número entero por lo general)

0000000000 

leer 4 así como el bit de la matriz ..

0000100000 

leer 6 y establecer el bit en la matriz

0000101000 

leer 2 y establecer el bit en la matriz

0010101000 

iterar la matriz e imprimir cada posición en la que los bits se ponen a uno.

2, 4, 6

ordenados.

Answer 3

A partir de set():
Un desplazamiento a la derecha de la figura 5 es lo mismo que dividir por 32. Lo hace para encontrar qué int el bit está en
máscara es o 31. AND con la dirección da 0x1f. el índice de bits dentro de la int. Es el mismo que el resto de dividir la dirección entre 32.
Cambiando 1 a la izquierda por el índice de bit ("1 < < (i & MASK)") da como resultado un entero que tiene solo 1 bit en la posición dada establecida.
ORing establece el bit.
La línea "int sh = i >> SHIFT;" es una línea desperdiciada, porque no usaron sh otra vez debajo de ella, y en su lugar simplemente repitieron "i >> SHIFT"

clr() es básicamente lo mismo que el conjunto, excepto en lugar de ORing con 1 < < (i & MÁSCARA) para establecer el bit, AND con el inverso para borrar el bit. test() AND con 1 < < (i & MASK) para probar el bit.

bitsort también eliminará los duplicados de la lista, ya que solo contará hasta 1 por entero. Un ordenamiento que usa números enteros en lugar de bits para contar más de 1 de cada uno se denomina ordenar por radix.

Answer 4

La magia de bits se utiliza como un esquema de direccionamiento especial que funciona bien con tamaños de fila que son potencias de dos.

Si intenta entender esto (nota: yo prefiero usar bits por fila de bits por palabra, ya que estamos hablando de una matriz poco aquí):

// supposing an int of 1 bit would exist... 
int1 bits[BITSPERROW * N]; // an array of N x BITSPERROW elements 

// set bit at x,y: 
int linear_address = y*BITSPERWORD + x; 
bits + linear_address = 1; // or 0 
// 0 1 2 3 4 5 6 7 8 9 10 11 ... 31 
// . . . . . . . . . . . .  . 
// . . . . X . . . . . . .  . -> x = 4, y = 1 => i = (1*32 + 4) 

La declaración linear_address = y*BITSPERWORD + x también significa que x = linear_address % BITSPERWORD y y = linear_address/BITSPERWORD.

Al optimizar esto en memoria mediante el uso de 1 palabra de 32 bits por fila, se obtiene el hecho de que un poco en la columna x se puede ajustar con

int bitrow = 0; 
bitrow |= 1 << (x); 

Ahora, cuando iteramos sobre los bits, nos tiene la dirección lineal, pero necesita encontrar la palabra correspondiente.

int column = linear_address % BITSPERROW; 
int bit_mask = 1 << column; // meaning for the xth column, 
          // you take 1 and shift that bit x times 
int row = linear_address/BITSPERROW; 

Así que para establecer el bit de orden i, se puede hacer esto:

bits[ i%BITSPERROW ] |= 1 << (linear_address/BITSPERROW); 

Un Gotcha adicional es, que el operador de módulo puede ser reemplazado por un AND lógico, y el/operador puede ser reemplazado por un cambio, también, si el segundo operando es una potencia de dos.

a % BITSPERROW == a & (BITSPERROW - 1) == a & MASK 
a/BITSPERROW == a >> (log2(BITSPERROW)) == a & SHIFT 

Esta última instancia se reduce a la muy densa, pero difícil de entender-para-el-bitfucker agnóstica notación

a[ i >> SHIFT ] |= (1 << (i&MASK)); 

Pero no veo el algoritmo de trabajo para, por ejemplo, 40 bits por palabra

Answer 5

Algunas dudas: 1. ¿Por qué es necesario un 32 bit? 2. ¿Podemos hacer esto en Java creando un HashMap con claves de 0000000 a 9999999 y valores 0 o 1 según la presencia/ausencia del bit? ¿Cuáles son las implicaciones para un programa de este tipo?

Answer 6

Citando los extractos del artículo original Bentley en DDJ, esto es lo que hace el código en un nivel alto:

/* phase 1: initialize set to empty */ 

for (i = 0; i < n; i++) 

    bit[i] = 0 

/* phase 2: insert present elements */ 

for each i in the input file 

    bit[i] = 1 

/* phase 3: write sorted output */ 

for (i = 0; i < n; i++) 

    if bit[i] == 1 

     write i on the output file