如何进行按位词典比较

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<00><01><1><10><11>
，其中所有项目都是位字符串(如0b10但为 0！=00)，它们不是 ASCII 字符串。
对于数学家来说，使用正式定义，每个字符串都是一个带有 2 个字母的字母表单词。

std::lexicographical_compare似乎不是解决方案，因为它不是面向位的。

重要提示：我需要良好的性能，因此(对于我的应用程序)将位转换为 ASCII0s 和1s 是无效的。我需要快速和按位词典比较。

---

建议(想象最佳解决方案)：当将一个大位字符串分成 n 个块(例如，更多的 tham 32 位和更少的 tham 1024 位)，使用i=0 到n-1扫描......也许更快的方法是使用一次块(例如 32 位的 chuckx_i)快速函数来检查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位比较中的最佳性能是每 chuck 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/itemn", sizeof(x[2]));
for (int k=0; k<kmax; k++) {
printf( "nx[%d]: i=%junt", 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(≠)