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

Question

Компилятор 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 <<code>00 <<code>01 <<code>1 <<code>10 <<code>11где все элементы являются битовыми строками (например, 0b10, но с 0! = 00), они не являются строками ASCII.Для математиков, использующих формальное определение 1028 *, каждая строка представляет собой слово алфавита с 2 буквами.

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

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

---

Предложение (воображаемое оптимальное решение): при делении большой битовой строки на n кусков (например, сбольше 32 бита и меньше 1024 бита), сканирование с i = от 0 до 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.

Answer 1

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

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

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

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

Answer 2

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

---

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

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

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

  #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(≠)