bit-manipulation - 快速查找 64 位无符号中的空半字节

Question

考虑一个 64 位无符号整数，它在可被 4 整除的位置恰好包含一个值为 0000b 的半字节。

是否有一个次线性的，即比 O(16) 算法更好的算法来提取这个空半字节的位置？ SIMD 解决方案也是可以接受的。

Answer 1

一种方法是使用 Alan Mycroft 的空字节检测算法的变体。包含零的字节变成 0x80，其他字节变成 0x00。 这可以通过调整掩码简单地修改为处理半字节而不是字节。使用 Posix 函数 ffsll()，我们可以找到第一个设置位并对位索引进行必要的调整，因为 ffsll() 使用基于 1 的位位置Mycroft 的算法标记零半字节中的最高有效位，而不是最低有效位。

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

/* Adapted from Alan Mycroft's null-byte detection algorithm 
   newsgroup comp.lang.c, 1987/04/08,
   https://groups.google.com/forum/#!original/comp.lang.c/2HtQXvg7iKc/xOJeipH6KLMJ
*/
int zero_nibble_position (uint64_t a)
{
    const uint64_t nibble_lsb = 0x1111111111111111ULL;
    const uint64_t nibble_msb = 0x8888888888888888ULL; 
    uint64_t t = (a - nibble_lsb) & (~a & nibble_msb);
    return (t) ? (ffsll (t) - 4) : -1;
}

int zero_nibble_position_ref (uint64_t a)
{
    if (!(a & (0xfULL <<  0))) return  0;
    if (!(a & (0xfULL <<  4))) return  4;
    if (!(a & (0xfULL <<  8))) return  8;
    if (!(a & (0xfULL << 12))) return 12;
    if (!(a & (0xfULL << 16))) return 16;
    if (!(a & (0xfULL << 20))) return 20;
    if (!(a & (0xfULL << 24))) return 24;
    if (!(a & (0xfULL << 28))) return 28;
    if (!(a & (0xfULL << 32))) return 32;
    if (!(a & (0xfULL << 36))) return 36;
    if (!(a & (0xfULL << 40))) return 40;
    if (!(a & (0xfULL << 44))) return 44;
    if (!(a & (0xfULL << 48))) return 48;
    if (!(a & (0xfULL << 52))) return 52;
    if (!(a & (0xfULL << 56))) return 56;
    if (!(a & (0xfULL << 60))) return 60;
    return -1;
}
/*
  https://groups.google.com/forum/#!original/comp.lang.c/qFv18ql_WlU/IK8KGZZFJx4J
  From: geo <gmars...@gmail.com>
  Newsgroups: sci.math,comp.lang.c,comp.lang.fortran
  Subject: 64-bit KISS RNGs
  Date: Sat, 28 Feb 2009 04:30:48 -0800 (PST)

  This 64-bit KISS RNG has three components, each nearly
  good enough to serve alone.    The components are:
  Multiply-With-Carry (MWC), period (2^121+2^63-1)
  Xorshift (XSH), period 2^64-1
  Congruential (CNG), period 2^64
*/
static uint64_t kiss64_x = 1234567890987654321ULL;
static uint64_t kiss64_c = 123456123456123456ULL;
static uint64_t kiss64_y = 362436362436362436ULL;
static uint64_t kiss64_z = 1066149217761810ULL;
static uint64_t kiss64_t;
#define MWC64  (kiss64_t = (kiss64_x << 58) + kiss64_c, \
                kiss64_c = (kiss64_x >> 6), kiss64_x += kiss64_t, \
                kiss64_c += (kiss64_x < kiss64_t), kiss64_x)
#define XSH64  (kiss64_y ^= (kiss64_y << 13), kiss64_y ^= (kiss64_y >> 17), \
                kiss64_y ^= (kiss64_y << 43))
#define CNG64  (kiss64_z = 6906969069ULL * kiss64_z + 1234567ULL)
#define KISS64 (MWC64 + XSH64 + CNG64)

int main (void)
{
    for (int i = 0; i < 1000000000; i++) {
        uint64_t a  = KISS64;
        int res = zero_nibble_position (a);
        int ref = zero_nibble_position_ref (a);
        if (res != ref) {
            printf ("a=%016llx  res=%d  ref=%d\n", a, res, ref);
            return EXIT_FAILURE;
        }
    } 
    return EXIT_SUCCESS;
}

如果您的平台不支持 POSIX 函数 ffsll() ，您可以使用特定于编译器的内置函数，例如 gcc 的 __builtin_ctz() 、MSVC 的 _BitScanForward64() 或 Intel 编译器的 _tzcnt_u64() ，使用内联汇编来访问提供计数的机器指令尾随零，或滚动你自己的，例如像这样:

int clzll (uint64_t a)
{
    uint64_t r = 64;
    if (a >= 0x100000000ULL) { a >>= 32; r -= 32; }
    if (a >= 0x000010000ULL) { a >>= 16; r -= 16; }
    if (a >= 0x000000100ULL) { a >>=  8; r -=  8; }
    if (a >= 0x000000010ULL) { a >>=  4; r -=  4; }
    if (a >= 0x000000004ULL) { a >>=  2; r -=  2; }
    r -= a - (a & (a >> 1));
    return r;
}

int ffsll (uint64_t a)
{
    return 64 - clzll(a & -a);
}

由于我们在这里不需要完全通用的 ffsll() 实现，因此还可以基于 previous answer of mine 构建一个更快的变体，它使用寄存器内查找表:

/* return the position of a single set bit at (one-based) position n*4 */
int bit_pos (uint64_t a)
{
    const uint64_t magic_multiplier = 
        (( 0ULL << 60) | ( 1ULL << 56) | ( 2ULL << 52) | ( 3ULL << 48) |
         ( 4ULL << 44) | ( 5ULL << 40) | ( 6ULL << 36) | ( 7ULL << 32) |
         ( 8ULL << 28) | ( 9ULL << 24) | (10ULL << 20) | (11ULL << 16) |
         (12ULL << 12) | (13ULL <<  8) | (14ULL <<  4) | (15ULL <<  0));
    return (int)((((a >> 3) * magic_multiplier) >> 60) * 4 + 4);
}

/* special version for MSBs of nibbles only! */
int ffsll (uint64_t a)
{
#if NEVER_MORE_THAN_ONE_ZERO_NIBBLE
    /* find the position of the only bit set */
    return bit_pos (a);
#else // NEVER_MORE_THAN_ONE_ZERO_NIBBLE
    /* isolate least significant set bit and find its position */
    return bit_pos (a & -a);
#endif // NEVER_MORE_THAN_ONE_ZERO_NIBBLE
}