Как написать программу сортировки битов на Java?

Question

Привет всем, у меня есть проблема с пониманием программы битовой сортировки в классическом программировании Bentley.Я новичок в Bitmask и Bitset, поэтому я не в состоянии понять эти концепции.На самом деле программа предназначена для «Как отсортировать файл на диске?». Ниже приведен код

#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){ 
    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;
}

Может кто-нибудь объяснить мне этот код?Если возможно, предоставьте версию на Java.На самом деле, я чувствую себя комфортно только на Java, поэтому я спрашиваю.Это не домашняя работа.

Возможные дубликаты: ссылка1 ссылка2

Answer 1

Нам даны числа, которые будут лежать в диапазоне от 0 до N,

Итак, мы делаем большой BitSet, который необходим для большого логического массива (работа объяснена в конце), нозанимает меньше памяти (каждый бит технически является логическим)

Итак, что делает Джон, он устанавливает весь бит на false, затем для каждого встреченного числа он устанавливает этот бит на true ...он пробегает набор битов и для каждой записи true печатает индекс.Это позволит отсортировать массив, где мы знаем, что элемент всегда лежит между 0 to N.

Примечание. Вышеприведенный алгоритм завершится ошибкой с дубликатами.

Теперь для материала с битовой маской ...

Скажем, у меня есть целочисленный массив (sizeof (int) = 32), но я хочу использовать его как логический массив размера N.Так сколько элементов мне действительно нужно?Это N/32

int a[1 + N/BITSPERWORD]; // allocates BitSet of N size

Теперь, если я хочу получить доступ к ith элементу BitSet, вот как работает индексация.

Например, i = 49

, такa[0] содержит биты 0-31, a [1] содержит 32-63.

a[i/32] (показывает, какой элемент int array содержит бит) и i % 32 битположение в этом элементе.

, поэтому для i= 49, a[49/32] & ( 1 << (i % 32) ) сообщит вам, установлен ли 49-й бит или нет.

Если вы знакомы с побитовой оптимизацией, вы знаете, что делениев 2 раза означает смещение числа вправо на число факторов.

32 = 2 ^ 5 ... поэтому X/32 тоже самое, что X >> 5

также X % 32 то же самое, что и X & 0x1f

test функция выдает 1, если набор битов в позиции установлен,

clr очищает набор битов в этой позиции в ноль

set устанавливает битовый набор в позиции на единицу.

Фу!Надеюсь, это поможет.

Answer 2

Если я правильно помню, бит, установленный в этом контексте, используется для эффективного отслеживания того, какие целые числа появляются в файле на диске.При передаче по файлу наличие целого числа i указывается путем установки i-го бита массива a на 1.

Например, если a [0] = 5, двоичное значениеиз 32 битов (помните, что константа BITSPERWORD предполагает, что код работает на 32-битной машине) при [0] составляет 0 ... 01010.Это будет означать, что целые числа 1 и 3 присутствовали в файле, но целые числа 2, а также 4 - 31 не были найдены в файле.

Шаги основного метода:

1. Установите все биты в массиве a на 0.
2. Сканируйте файл, установив i-й бит массива на 1, если встречается целое число i.
3. Проверка, было ли найдено целое число i в файле и выведено ли это целое число на экран.