Пример bsort из программирования жемчуг

Question

В Программировании Жемчуга есть алгоритм, который сортирует массивы различной длины, но сортирует по времени, пропорциональному сумме их длины. Например, если у нас есть массив записей x[0...n-1]и каждая запись имеет целочисленную длину и указатель на массив bit[0...length-1],

Код реализован так:

void bsort(l, u, depth){
    if (l >= u)
        return ;
    for (i = l; i <= u; i++){
        if (x[i].length < depth)
            swap(i, l++);
    }
    m = l;
    for (int i = l; i < u; i++){
        if (x[i].bit[depth] == 0)
            swap(i, m++);
    }
    bsort(l, m - 1, depth + 1);
    bsort(m, u, depth + 1);
}

Мой вопрос таков, учитывая запись:

x[6] = {"car", "bus", "snow", "earth", "dog", "mouse"}

Я знаю, как получить длину строки, но как насчет битового массива? Как я могу сделать битовый массив, подходящий для этого массива строк? И даже x[i].bit[depth] как я могу это реализовать?

Answer 1

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

По сути, сначала вы должны выяснить, в каком байте находится требуемый бит, а затем получить значение этого конкретного бита. Что-то вместе:

char* array = "the array";
int required_bit = 13;
int bit = required_bit & 0x7;  // get the bit's offset in its byte
int byte = required_bit >> 3;  // get the bit's byte
int val = (array[byte] >> bit) & 0x1; // check if the bit is 1

Теперь оберните это в функцию (возможно, с дополнительными проверками привязки, чтобы убедиться, что required_bit не вне массива), и использовать с x[i],