Как работают битовые манипуляции в этом коде сортировки битов?

Джон Бентли в колонке 1 своей книги "Жемчужины программирования" представляет методику сортировки последовательности ненулевых натуральных чисел с использованием битовых векторов.

Я взял программу bitsort.c из здесь и вставил ее ниже:

/* 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;
}

Я понимаю, что делают функции clr, set и test, и объясню их ниже: (пожалуйста, исправьте меня, если я ошибаюсь).

  • clr очищает i-й бит
  • set устанавливает i-й бит
  • test возвращает значение в i-м бите

Теперь я не понимаю, как функции делают то, что они делают. Я не могу понять все битовые манипуляции, происходящие в этих трех функциях.

Ответы

Ответ 1

Первые 3 константы взаимосвязаны. BITSPERWORD - 32. Это вы хотите установить на основе вашей архитектуры компилятора+. SHIFT равен 5, потому что 2 ^ 5 = 32. Наконец, MASK - это 0x1F, который равен 11111 в двоичном (т.е.: все 5 бит установлены). Эквивалентно, MASK = BITSPERWORD - 1.

Битрейт концептуально представляет собой только массив бит. Эта реализация фактически использует массив ints и предполагает 32 бита на int. Поэтому, когда мы хотим установить, очистить или проверить (прочитать) немного, нам нужно выяснить две вещи:

  • который int (из массива) находится в
  • какой из этих битов int мы говорим о

Поскольку мы принимаем 32 бита на int, мы можем просто делить на 32 (и обрезать), чтобы получить требуемый индекс массива. Разделение на 32 (BITSPERWORD) совпадает с сдвигом вправо на 5 (SHIFT). Итак, о чем бит [i → SHIFT]. Вы также можете написать это как [i/BITSPERWORD] (и на самом деле вы, вероятно, получите тот же или очень похожий код, если ваш компилятор имеет разумный оптимизатор).

Теперь, когда мы знаем, какой элемент мы хотим, нам нужно выяснить, какой бит. В самом деле, мы хотим остаться. Мы могли бы сделать это с помощью i% BITSPERWORD, но оказывается, что я & MASK эквивалентен. Это потому, что BITSPERWORD - это сила 2 (2 ^ 5 в этом случае), а MASK - это всего лишь 5 бит.

Ответ 2

В основном оптимизирован вид корзины:

  • зарезервировать бит массива длины n  биты.
  • очистить бит массива (сначала в основном).
  • читайте элементы поодиночке (все они должны быть разными).
    • установите i-й бит в битовом массиве, если прочитанным номером является i.
  • итерация битового массива.
    • если бит установлен, затем распечатайте позицию.

Или, другими словами (для N < 10 и сортировать 3 числа 4, 6, 2) 0

начните с пустого 10-битного массива (ака одно целое)

0000000000

прочитайте 4 и установите бит в массиве.

0000100000

прочитайте 6 и установите бит в массиве

0000101000

прочитайте 2 и установите бит в массиве

0010101000

итерация массива и печать каждой позиции, в которой биты установлены на один.

2, 4, 6

отсортирован.

Ответ 3

Начиная с set():
Правый сдвиг 5 совпадает с делением на 32. Он делает это, чтобы найти, в каком int бит находится. MASK - это 0x1f или 31. Инициация с адресом дает бит индекс внутри int. Это то же самое, что и остаток деления адреса на 32.
Смещение 1, оставшееся от битового индекса ( "1 < < (i и MASK)" ), приводит к целому числу, которое имеет только 1 бит в заданной позиции.
ORing устанавливает бит.
Строка "int sh = я → SHIFT;" это потерянная линия, потому что они не использовали sh снова под ней, а вместо этого просто повторяли "i → SHIFT"

clr() в основном то же самое, что и set, за исключением того, что вместо ORing с 1 < < (i и MASK), чтобы установить бит, это AND с инверсией для очистки бит. test() AND с 1 < (i и MASK) для проверки бит.

Битовый набор также удалит дубликаты из списка, поскольку он будет считать только до 1 на целое число. Сорт, который использует целые числа вместо битов для подсчета более одного из них, называется сортировкой по основанию.

Ответ 4

Бит-магия используется как специальная схема адресации, которая хорошо работает с размерами строк, которые имеют две степени.

Если вы попытаетесь понять это (обратите внимание: я скорее использую биты за строку, чем бит-за-слово, поскольку мы говорим о битовой матрице здесь):

// 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)

Утверждение linear_address = y*BITSPERWORD + x также означает, что x = linear_address % BITSPERWORD и y = linear_address / BITSPERWORD.

Когда вы оптимизируете это в памяти, используя 1 слово из 32 бит на строку, вы получаете тот факт, что бит в столбце x можно установить с помощью

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

Теперь, когда мы перебираем биты, у нас есть линейный адрес, но нужно найти соответствующее слово.

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;

Итак, чтобы установить i-й бит, вы можете сделать это:

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

Дополнительный getcha заключается в том, что оператор modulo может быть заменен логическим И, а оператор/может быть заменен сдвигом, если второй операнд является степенью двух.

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

Это в конечном счете сводится к очень плотной, но трудно понятной для бит-хук-агностической нотации

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

Но я не вижу алгоритма, работающего, например. 40 бит на слово.

Ответ 5

Цитируя выдержки из оригинальной статьи Bentleys в DDJ, это то, что делает код на высоком уровне:

/* 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

Ответ 6

Несколько сомнений: 1. Почему это необходимо для 32-битного? 2. Можем ли мы сделать это на Java, создав HashMap с ключами от 0000000 до 9999999  и значения 0 или 1 в зависимости от наличия/отсутствия бит? Каковы последствия  для такой программы?