使用位运算符计算最大16个字符的字符串的长度

Question

这个挑战要求使用 C/C++ 中的位运算来快速确定 c 字符串的长度。

char thestring[16];

这个c字符串最大长度为16个字符，位于缓冲区内。如果字符串等于16个字符，则末尾没有空字节。

我相信这是可以做到的，但我还没有做对。

我正在处理这个问题，但是假设该字符串被复制到一个填零的缓冲区中。

len =   buff[0] != 0x0 +
            buff[1] != 0x0 +
            buff[2] != 0x0 +
            buff[3] != 0x0 +
            buff[4] != 0x0 +
            buff[5] != 0x0 +
            buff[6] != 0x0 +
            buff[7] != 0x0 +
            buff[8] != 0x0 +
            buff[9] != 0x0 +
            buff[10] != 0x0 +
            buff[11] != 0x0 +
            buff[12] != 0x0 +
            buff[13] != 0x0 +
            buff[14] != 0x0 +
            buff[15] != 0x0;

注意：缓冲区是零填充的，因此不可能出现 "\0123456789abcde"。

- fabrizioM

---

为什么一些人对位运算符如此着迷？ - anon

@Neil：速度对于GPU内核来说非常重要，内核上少一条指令就意味着设备上少了成千上万条指令。 - fabrizioM

@GMan - Nvidia的显卡支持从1.0到2.0的所有计算能力。 - fabrizioM

@fabrizio 你似乎假设 C 或 C++ 中的位运算符使用会转换为单个 CPU/GPU 操作。 - anon

@fabrizioM说：仅仅编写低级别的代码并不能保证“速度”。通常情况下，这样做会导致1）出现Bug，2）编写的代码比如果你在高层次上表达意图，让编译器自动生成代码还要慢。 - jalf

Answer 1

这样做是可以的，因为buf已经被初始化为零。您的解决方案使用了!=，这将使用跳转指令。如果GPU有多个异或单元，以下代码可以很好地进行流水线操作。另一方面，JUMP指令会导致管道刷新。

len = !!buf[0] +
      !!buf[1] +
      //...
      !!buf[15]

更新：当使用GCC编译并加上-O3标志时，以上代码和OP的代码会产生相同的汇编代码。（如果没有提供优化标志，则不同）

- N 1.1

---

@Gman：我在想两个解决方案，在发布时有点混淆。谢谢 :) - N 1.1

如果GPU有多个XOR单元，上述代码可以很好地进行流水线处理。另一方面，JUMP指令会导致流水线被清空。 - N 1.1

@ergo：是的，fabrizioM假设缓冲区已经被复制为0。 - N 1.1

gcc 4.3.2 在 -O3、x86 目标上无法编译（至少如此）。 - caf

@caf：-O3确实使它们相同。我以为!=会使用JMP来实现。但编译器非常聪明。（没有优化时，它们是不同的 :) - N 1.1

Answer 2

您的代码无法正常工作。例如，考虑一个包含以下内容的缓冲区：

"\0123456789abcde";

根据你的代码，它的长度为15，但实际上因为初始的"\0"，它的长度为0。

尽管并行计算会很好，但事实上字符串的定义或多或少地要求从开头开始计数，只有在遇到"\0"（或在你的情况下达到16）时才停止计数。

- Jerry Coffin

---

Strlen不会执行其他操作... 它也会返回零。 - imacake

@imacake：我觉得你误解了：重点是strlen会返回0，但他的算法不会。看起来他已经编辑了问题，说我提到的问题对于他的输入不可能发生，但我不认为当时有这样的陈述。 - Jerry Coffin

Answer 3

我在《黑客的乐趣》一书中读到了一个小技巧，称为SWAR（寄存器内SIMD），假设每个字符为8位：

#define CHAR_BITS 8
uint_fast_16_t all_character_bits[CHAR_BITS]= { 0 };

for (int bit_index= 0; bit_index<CHAR_BITS; ++bit_index)
{
    for (int character_index= 0; character_index<16; ++character_index)
    {
        all_character_bits[bit_index]|= ((buff[character_index] >> bit_index) & 1) << character_index;
    }
}

uint_fast_32_t zero_byte_character_mask= ~0;

for (int bit_index= 0; bit_index<CHAR_BITS; ++bit_index)
{
    zero_byte_character_mask&= (0xffff0000 | ~all_character_bits[bit_index]);
}

uint_fast_8_t first_null_byte= first_bit_set(zero_byte_character_mask);

其中，first_bit_set是在一个整数中查找第一个位设置的流行和快速实现的任意数量。

基本思路是将这16个字符作为8x16位矩阵，并将所有列的按位非进行AND操作。任何一行都是全零的话，那么该行的位就会在结果中被设置。然后，我们只需要找到结果中第一个被设置的位，那就是字符串的长度。这个特定的实现确保了当所有字符不为空时，位16-31也被设置在结果中。实际的位转置也可以更快（即没有分支）。

- MSN

Answer 4

位运算操作... 可能类似这样：

// TODO: optimize for 64-bit architectures
uint32_t *a = (uint32_t*)thestring;

for (int i = 0; i < 4; i++) // will be unwound
    for (int j = 0; j < 4; j++)
        if (a[i] & 0xff << j == 0)
           return 4*i+j;
return 16;

- el.pescado - нет войне

---

+1 它给了我一些关于如何每次使用4个字符的想法（寄存器是32位） - fabrizioM

请确保这些uints对齐正确。如果未对齐可能会很昂贵，即使它不会引起其他问题。 - Maciej Hehl

Answer 5

你可以进行位运算，但很可能无法超越这个：

int fast1(const char *s)
{ 
    if (!*s++) return 0; 
    if (!*s++) return 1; 
    if (!*s++) return 2; 
    if (!*s++) return 3; 
    if (!*s++) return 4; 
    if (!*s++) return 5; 
    if (!*s++) return 6; 
    if (!*s++) return 7; 
    if (!*s++) return 8; 
    if (!*s++) return 9; 
    if (!*s++) return 10; 
    if (!*s++) return 11; 
    if (!*s++) return 12; 
    if (!*s++) return 13; 
    if (!*s++) return 14; 
    if (!*s++) return 15; 
}

或者，您可以这样做： （是否更快取决于您的处理器和编译器）。

int fast2(const char *s)
{ 
    if (!s[0]) return 0; 
    if (!s[1]) return 1; 
    if (!s[2]) return 2; 
    if (!s[3]) return 3; 
    if (!s[4]) return 4; 
    if (!s[5]) return 5; 
    if (!s[6]) return 6; 
    if (!s[7]) return 7; 
    if (!s[8]) return 8; 
    if (!s[9]) return 9; 
    if (!s[10]) return 10; 
    if (!s[11]) return 11; 
    if (!s[12]) return 12; 
    if (!s[13]) return 13; 
    if (!s[14]) return 14; 
    if (!s[15]) return 15; 
}

更新：

我在我的Core2Duo T7200 @ 2.0 GHz、Windows XP pro、Visual Studio 2008上关闭了优化，对这两个函数进行了分析。（打开优化器会导致VS注意到我的计时循环中没有输出，因此它会将其完全删除）。

我在一个循环中调用每个函数2²²次，然后在8次运行中取平均值。

fast1每个函数调用大约需要87.20纳秒。

fast2每个函数调用大约需要45.46纳秒。

因此，在我的CPU上，数组索引版本的速度几乎是指针版本的两倍。

我无法让这里发布的任何其他函数正常工作，因此我无法进行比较。最接近的是原始帖子的函数，它可以编译，但并不总是返回正确的值。当它确实返回正确的值时，每个函数调用需要大约59纳秒。

更新2

这个函数也非常快，每次调用大约只需要60纳秒。我猜指针解引用是由地址单元执行的，而乘法是由整数单元执行的，因此操作正在进行流水线处理。在我的其他示例中，所有工作都由地址单元完成。

int fast5(const char *s)
{
    return  /* 0 * (s[0] == 0) + don't need to test 1st byte */
            1 * (s[1] == 0)  +
            2 * (s[2] == 0)  +
            3 * (s[3] == 0)  +
            4 * (s[4] == 0)  +
            5 * (s[5] == 0)  +
            6 * (s[6] == 0)  +
            7 * (s[7] == 0)  +
            8 * (s[8] == 0)  +
            9 * (s[9] == 0)  +
            10 * (s[10] == 0) +
            11 * (s[11] == 0) +
            12 * (s[12] == 0) +
            13 * (s[13] == 0) +
            14 * (s[14] == 0) +
            15 * (s[15] == 0);
}

- Seth

---

你测量过这个的速度吗？ - user153062

@KennyTM - 我不太了解GPU的具体情况，为什么多个返回值很重要？@Peter - 我发布了一些结果。 - Seth

没有任何一种内存引用和比较能够击败位操作。 - drawnonward

Answer 6

根据您所说的，我相信您试图避免跳转，这就是我正在努力实现的。

我很确定您发布的代码只是看起来很棒，但在许多处理器上编译时实际上并不会那么好，尽管在您的处理器上可能会很好。我所知道的大多数处理器实际上没有一种简单的方法来从比较中获得1，因此这可能最终会变成条件跳转或条件操作的形式：

set R1, 0
test R2+0, 0
cinc R1                   ; conditional increment
test R2+1, 0
cinc R1
...

如果GPU可以进行条件增量并且在八位大小的项目上表现良好，那么这可能很有效。

如果编译器做得很好，在许多处理器上，这将变成类似于以下内容：

set R1, 0
test R2+0, 0
jz end  ; jump if zero
inc R1
test R2+1, 0
jz end
inc R1
...

如果非跟随条件跳转对您没有太大影响，那么这也是可以接受的，因为您只有一个跟随条件跳转（第一个找到0的跳转）。

由于您说您的目标是GPU，而这些通常非常适合数学计算，因此您可能能够执行以下操作：

int acc = 0;
acc += str[0]/str[0];
acc += str[1]/str[1];
...

如果您能够在不花费太多成本的情况下捕获除以零的异常并处理异常，那么这可能会变得很昂贵。

如果您的计算机具有可以容纳字符串超过一个八位字节的寄存器，则可以尝试进行有限数量的跳转，并一次测试0个以上的字节，然后在字节级别检查最后一个非零字。

您应该查看Bit Twiddling Hacks，这是一种很酷的加速strlen的方法，适用于大型寄存器大小。

另外，您可能还需要考虑从字符串末尾开始测量（您知道最大长度）。 只要空终止字节后面跟着更多的空字节，这将起作用，如果您可能有更长的字符串，即使在其中插入跳转，这也可能是一种胜利。

- nategoose

---

加1的除法技巧实际上可能比!! str [0]更快（1个操作而不是2个）在GPU上，寄存器为32位，我想知道这是否也适用于32。 - fabrizioM

Answer 7

你可以从这里开始

template <typename T>
bool containsANull(T n) {
   return (n  - ((T) -1)/255) & ((T) -1)/255*128) & ~n;
}

构建一些东西。为了值得，T 可能应该是一个 64 位无符号类型，但即使如此，还有一些调整需要做，让我想知道你的缓冲区是否足够长以实现这个技巧。

它是如何工作的？

(T)-1/255 是比特模式 0x01010101，重复使用所需的长度

(T)-1/255*128 因此是比特模式 0x80808080 重复

if n is                        0x0123456789ABCDEF
n - 0x1111..1 is               0xF0123456789ABCDE
(n-0x1111...1) & 0x8888...8 is 0x8000000008888888
~n is                          0xFEDCBA9876543210 
so the result is               0x8000000000000000

在这里得到一个非空字节的唯一方法是从一个空字节开始。

- AProgrammer

---

你能详细说明一下你的逻辑是什么吗？ - fabrizioM

+1 对解释的认同。我发现你的版本是@sparky链接的通用版本！ - fabrizioM

很酷，但你不会用除法和乘法赢得“最快”。 - Seth

是的，（我很久以前从Usenet上得到了这个，我使用了除法技巧得到了一个大小无关的版本。Mycroft这个名字听起来很熟悉，但87年对我来说太早了；我的信息来源可能引用了他）。 - AProgrammer

@Seth，它们是常量表达式。如果你的编译器没有注释这个，只需使用正确的位模式，调整到最长可用类型的大小。 - AProgrammer

Answer 8

请参考由Paul Hsieh实现的fstrlen()，网址为...

http://www.azillionmonkeys.com/qed/asmexample.html

虽然不完全符合您的要求，但稍加调整应该就可以满足您的需求。

该算法尝试使用一些位操作技巧，每次检查四个字节以查找字符串结束字符。

- Sparky

Answer 9

在一个假想的类似于C++的语言中，假设使用2的补码和小端序。

int128_t v = *reinterpret_cast<int128_t*>(thestring);
const int bit_count = 128;
int eight = ((1 << 64) - 1 - v) >> (bit_count - 4) & 8;
v >>>= 8 * eight;
int four  = ((1 << 32) - 1 - v) >> (bit_count - 3) & 4;
v >>>= 8 * four;
int two   = ((1 << 16) - 1 - v) >> (bit_count - 2) & 2;
v >>>= 8 * two;
int one   = ((1 <<  8) - 1 - v) >> (bit_count - 1) & 1;
return (one | two | four | eight) + !!v;

（修改自http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog。）

- kennytm

---

@fab: ">>>" 表示逻辑右移（即无符号右移）。嗯，实际上算术右移也可以因为 & x 的东西。 - kennytm

只需将类型设置为无符号或将其强制转换为无符号以进行移位。 - nategoose

Answer 10

假设为64位长和小端系统：

long a = ((long *)string)[0];
long b = ((long *)string)[1];

a = (a - 0x0101010101010101UL) & ~a & 0x8080808080808080UL;
b = (b - 0x0101010101010101UL) & ~b & 0x8080808080808080UL;

return a ? count_trailing_zeros( a ) / 8 : b ? 8 + count_trailing_zeros( b ) / 8 : 16;

对于大端字节序，计算前导零。任何系统的strlen实现都会使用它。

- drawnonward