Как сделать побитово-лексикографическое сравнение

Компилятор gcc интерпретирует тип данных char как целое число, и это имеет смысл... Есть ли функция сравнения для сравнения битовых строк?

  char a='0';  
  char b= 0b11111111;
  if (a<b) {/* never goes here! */}
  if (bitStringCompare(a,b)) {/* this kind of "native" function exists? */}

Лучший способ решить мою проблему из реальной жизни — объявить a и b с другим типом данных, который на самом деле является битовой строкой, например (предположим) ASN1TDynBitStr, но я не вижу для него побитово-лексикографического сравнения.

ПРИМЕЧАНИЯ

Лексикографический порядок строк битов переменной длины:
0 ‹ 00 ‹ 01 ‹ 1 ‹ 10 ‹ 11
где все элементы представляют собой строки битов (например, 0b10, но с 0!=00), они не ASCII. струны.
Для математиков, используя формальное определение, каждая строка представляет собой слово из алфавит из 2 букв.

std::lexicographical_compare не кажется решением, потому что не является побитовым.

Важно: мне нужна хорошая производительность, поэтому (для моего приложения) недопустимо преобразовывать биты в ASCII 0s и 1s. Мне нужно быстрое и побитовое лексикографическое сравнение.

Предложение (придумать оптимальное решение): при разделении длинной строки битов на n кусков (например, с более чем 32 битами и менее чем с 1024 битами) сканирование с помощью i =0 to n-1... Возможно, более быстрый подход заключается в использовании быстрой функции по частям (например, chunck x_i из 32 битов) для проверки a_i==b_i, их ( когда a_i!=b_i) используйте побитовую функцию, чтобы вернуть a_i<b_i.

Лексикографическое сравнение строк битов a_i==b_i возможно для числовых (беззнаковых) типов данных при объединении битов 1: например, для сравнения 0000==0 мы можем использовать 0b10000==ob10.


gcc compare lexicographic bitwise-operators
person Peter Krauss    schedule 09.06.2019    source источник
comment
Насколько я понимаю, вы пытаетесь сделать is_less_than(to_string_base2(integer_a), to_string_base2(integer_b)), но эффективно, без преобразования в строку? Я прав? Если да, то как получить такие строки, как 00 или 01? Функции преобразования числа в строку обычно не записывают начальные нули?   -  person PSkocik    schedule 09.06.2019
comment
Спасибо @PSkocik, смотрите мои ПРИМЕЧАНИЯ: ... это не строки ASCII ... мне нужна хорошая производительность ... мне нужно быстрое и побитовое лексикографическое сравнение.   -  person Peter Krauss    schedule 09.06.2019
comment
Хорошо, теперь я понимаю: у типа ASN1TDynBitStr есть счетчик битов, поэтому вы знаете, сколько начальных нулей должно быть в строковой форме. Извините за путаницу.   -  person PSkocik    schedule 09.06.2019
comment
@PSkocik ваш вопрос без преобразования в строку? возможно, это другой способ выразить мой вопрос, функция существует? :-)   -  person Peter Krauss    schedule 09.06.2019

Ответы (2)


arrow_upward
1
arrow_downward

Проще всего накладывать биты на беззнаковый тип (например, unsigned char, а не char). Если тип может хранить W бита (8 в случае char), то вы можете адресовать nth бит с помощью

nth_bit(array,nth) array[nth/W]&(1ull<<(nth%W))

Самый простой способ выполнить лексикографическое сравнение битов — начать слева и пройтись по битам слева направо лексикографически сравнивая их, как если бы вы перебирали символы в строке.

Этот подход можно ускорить, сравнивая несколько битов за раз, но тогда вам придется следить за тем, как все выравнивается.

person PSkocik    schedule 09.06.2019
comment
Да, для больших битовых строк нам нужно то, что вы прокомментировали, Этот подход можно ускорить, сравнивая несколько битов за раз... В языке C есть функция для сравнить лексикографически unsigned char? - person Peter Krauss; 09.06.2019
comment
Абсолютно. Отсюда часть о сравнении нескольких битов за раз. Для больших битовых строк вы получите наилучшую производительность, если вам удастся сравнить потерянные выровненные фрагменты размером со слово, но для небольших, которые могут быть смещены, битовая версия должна быть быстрее и меньше. C имеет только strcmp, который работает только с реальными строками, но алгоритм тривиален. - person PSkocik; 09.06.2019
comment
@PeterKrauss Нет. Нет. Адаптировать шаблон C++ тривиально, но вы все равно можете использовать его только в том случае, если все выровнено. Вы можете сравнивать 10-битную строку с 9-битной строкой. Лексикографическое сравнение беззнаковых символов в этой ситуации бесполезно. - person PSkocik; 09.06.2019
comment
Хм... Нет современных процессоров, которые помогли бы реализовать что-то вроде bitstr_cmp? (Вы уверены в этом?) Да, нужны выровненные фрагменты размером в слово, но нужна внутренняя быстрая функция для сравнения фрагментов за один шаг. - person Peter Krauss; 09.06.2019
comment
Побитовая версия должна иметь наименьший размер кода и может быть достаточно быстрой. Для быстрой версии я бы посмотрел, достаточно ли все выровнено, а затем выполнил сравнение слов во времени или символов во времени, и если бы это было не так, я бы все равно сравнил несколько битов за раз, переходя от следующего символа /слово. Могут быть более быстрые подходы. - person PSkocik; 09.06.2019
comment
Большое спасибо PSkocik (!). Я подожду несколько недель или месяцев (соответствующих просмотров страниц), прежде чем нажать кнопку «Принять» в этом ответе только для того, чтобы подтвердить, что никто не видит функцию bitstr_cmp. Более быстрые подходы, возможно, используют пошаговую проверку на идентичность фрагментов (a_i==b_i), они используют побитовую проверку для проверки a_i<b_i. Проверка строки битов 00!=0 возможна путем числового сравнения путем объединения битов 1, 100!=10 в число без знака. - person Peter Krauss; 09.06.2019

arrow_upward
0
arrow_downward

Это вики, пожалуйста, отредактируйте (!) и дополните ответ.

Этот фрагмент показывает, что можно оптимизировать:

  1. по тесту выберите длину фрагмента (что-то вроде 8, 16 или 32 бит) для более быстрого побитового сравнения.
  2. используйте побитовое сравнение только один раз, все остальные являются эквивалентностью фрагментов.

Предположим, что наилучшая производительность в @PSkocik побитовом сравнении составляет 8 бит (char) на фрагмент, и предположим, что мы подаем данные длинными целыми числами,

  #include <stdio.h>
  #include <string.h>
  #include <stdint.h>

  union Data {
    uint64_t i;  // unsigned long long
    char str[8]; // 8bits*8=64bits
  };

  int main( ) {
    int kmax = 6;
    union Data x[6] = {
      [0].i=0b0000000000000000000000000000000000000000000000000000000000000010,
      [1].i=0b1000000000000000000000000000000000000000000000000000000000000000,
      [2].i=0b0000000000000000000000000000000000000000000000000000000000000101, //
      [3].i=0b0000000000000000000000000000000001000000000000000000000000000011,
      [4].i=0b0000000000000000000000000000000000000000000000000000000000000110,
      [5].i=0b0000000000000000000000000000000000000000000000000000000000000111
    };
    printf( "\nComparing all with x[2], %zu bytes/item\n", sizeof(x[2]));
    for (int k=0; k<kmax; k++) {
      printf( "\nx[%d]: i=%ju\n\t", k, x[k].i);
      for (int j=7;j>=0;j--) {
        printf( " %d(%s)", j, (x[k].str[j]==x[2].str[j])? "=": "≠" );
      }
    }
    printf("\n");
    return 0;
  }

Выход:

Comparing all with x[2], 8 bytes/item

x[0]: i=2
     7(=) 6(=) 5(=) 4(=) 3(=) 2(=) 1(=) 0(≠)
x[1]: i=9223372036854775808
     7(≠) 6(=) 5(=) 4(=) 3(=) 2(=) 1(=) 0(≠)
x[2]: i=5
     7(=) 6(=) 5(=) 4(=) 3(=) 2(=) 1(=) 0(=)
x[3]: i=1073741827
     7(=) 6(=) 5(=) 4(=) 3(≠) 2(=) 1(=) 0(≠)
x[4]: i=6
     7(=) 6(=) 5(=) 4(=) 3(=) 2(=) 1(=) 0(≠)
x[5]: i=7
     7(=) 6(=) 5(=) 4(=) 3(=) 2(=) 1(=) 0(≠)
person Community    schedule 10.06.2019