Как делают побитовые обработки в этой сортирующей бит работе кода?
Jon Bentley в Столбце 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
#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;
}
Я понимаю то, что функции сбрасывают, устанавливают и тестируют, делают и объясняют их ниже: (исправьте меня, если я неправ здесь).
- сброс очищается, ith укусил
- набор устанавливает бит ith
- тест возвращает значение на уровне бита ith
Теперь, я не понимаю, как функции делают то, что они делают. Я не могу выяснить всю побитовую обработку, происходящую в тех трех функциях.
4 ответа
Первые 3 константы взаимосвязаны. BITSPERWORD - 32. Это нужно установить в зависимости от вашего компилятора и архитектуры. SHIFT равен 5, потому что 2 ^ 5 = 32. Наконец, MASK - это 0x1F, что равно 11111 в двоичном формате (то есть: все нижние 5 бит установлены). Эквивалентно MASK = BITSPERWORD - 1.
Битовый набор концептуально представляет собой просто массив бит. Эта реализация фактически использует массив int и предполагает 32 бита на int. Поэтому всякий раз, когда мы хотим установить, очистить или протестировать (прочитать) бит, нам нужно выяснить две вещи:
- какой int (массива) находится в
- , о каком из этих битов int идет речь
Поскольку мы предполагаем, что на int 32 бита, мы можем просто разделить на 32 (и усечь), чтобы получить нужный нам индекс массива. Деление на 32 (BITSPERWORD) аналогично сдвигу вправо на 5 (SHIFT). Вот что такое бит a [i >> SHIFT]. Вы также можете записать это как [i / BITSPERWORD] (и на самом деле вы, вероятно, получите такой же или очень похожий код, если у вашего компилятора есть разумный оптимизатор).
Теперь, когда мы знаем, какой элемент мы хотим , нам нужно выяснить, какой бит. На самом деле мы хотим остаток. Мы могли бы сделать это с помощью i% BITSPERWORD, но оказывается, что i & MASK эквивалентны. Это потому, что BITSPERWORD - это степень 2 (в данном случае 2 ^ 5), а MASK - это все 5 нижних битов.
The bit magic is used as a special addressing scheme that works well with row sizes that are powers of two.
If you try understand this (note: I rather use bits-per-row than bits-per-word, since we're talking about a bit-matrix here):
// 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)
The statement linear_address = y*BITSPERWORD + x also means that x = linear_address % BITSPERWORD and y = linear_address / BITSPERWORD.
When you optimize this in memory by using 1 word of 32 bits per row, you get the fact that a bit at column x can be set using
int bitrow = 0;
bitrow |= 1 << (x);
Now when we iterate over the bits, we have the linear address, but need to find the corresponding word.
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;
So to set the i'th bit, you can do this:
bits[ i%BITSPERROW ] |= 1 << (linear_address / BITSPERROW );
An extra gotcha is, that the modulo operator can be replaced by a logical AND, and the / operator can be replaced by a shift, too, if the second operand is a power of two.
a % BITSPERROW == a & ( BITSPERROW - 1 ) == a & MASK
a / BITSPERROW == a >> ( log2(BITSPERROW) ) == a & SHIFT
This ultimately boils down to the very dense, yet hard-to-understand-for-the-bitfucker-agnostic notation
a[ i >> SHIFT ] |= ( 1 << (i&MASK) );
But I don't see the algorithm working for e.g. 40 bits per word.
Я решил использовать Csv Reader Себастьяна Лориона.
Предложение Джея Риггса также является отличным решением, но мне просто не нужны были все функции, которые предоставляет Общий синтаксический анализатор Эндрю Риссинга .
ОБНОВЛЕНИЕ 25.10.2010
После использования Csv Reader Себастьяна Лориона в мой проект в течение почти полутора лет, я обнаружил, что он вызывает исключения при синтаксическом анализе некоторых файлов CSV, которые я считаю правильно сформированными.
Начиная с set ():
Сдвиг вправо на 5 аналогичен делению на 32. Он позволяет определить, в каком int находится бит.
МАСКА равна 0x1f или 31. Операция И с адресом дает битовый индекс в int. Это то же самое, что и остаток от деления адреса на 32.
Сдвиг 1 влево на битовый индекс ("1 << (i & MASK)") приводит к целому числу, которое имеет только 1 бит в заданном наборе позиции.
Операция ИЛИ устанавливает бит.
Строка «int sh = i >> SHIFT;» является потраченной впустую строкой, потому что они не использовали sh снова под ней, а вместо этого просто повторяли «i >> SHIFT»
clr () в основном то же самое, что и set, за исключением того, что вместо OR с 1 << (i & MASK), чтобы установить бит, он выполняет операцию И с инверсией, чтобы очистить бит. test () И с 1 << (i & MASK) для проверки бита.
Битовая сортировка также удалит дубликаты из списка, потому что она будет считать до 1 на целое число. Сортировка, которая использует целые числа вместо битов для подсчета более одного каждого из них, называется поразрядной сортировкой.