如何使用位操作有效地找到64位值中唯一设置位的位置？

Question

只是说我的类型值uint64_t被视为八位字节序列(1个八位字节= 8位).uint64_t已知该值仅包含MSB位置的一个设置位.因此,该uint64_t值可以是以下二进制表示之一:

00000000 00000000 00000000 00000000 00000000 00000000 00000000 10000000  pos = 7
00000000 00000000 00000000 00000000 00000000 00000000 10000000 00000000  pos = 15
00000000 00000000 00000000 00000000 00000000 10000000 00000000 00000000  pos = 23
00000000 00000000 00000000 00000000 10000000 00000000 00000000 00000000  pos = 31
00000000 00000000 00000000 10000000 00000000 00000000 00000000 00000000  pos = 39
00000000 00000000 10000000 00000000 00000000 00000000 00000000 00000000  pos = 47
00000000 10000000 00000000 00000000 00000000 00000000 00000000 00000000  pos = 55
10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000  pos = 63

我需要一个返回设置位位置的快速函数,但如果没有设置位,则返回0.

如果可能的话,我希望它既没有循环也没有分支.

Answer 1

将值乘以精心设计的64位常数,然后屏蔽高4位.对于具有快速64位乘法的任何CPU,这可能是您可以获得的最佳值.

int field_set(uint64_t input) {
    uint64_t field = input * 0x20406080a0c0e1ULL;
    return (field >> 60) & 15;
}

// field_set(0x0000000000000000ULL) = 0
// field_set(0x0000000000000080ULL) = 1
// field_set(0x0000000000008000ULL) = 2
// field_set(0x0000000000800000ULL) = 3
// field_set(0x0000000080000000ULL) = 4
// field_set(0x0000008000000000ULL) = 5
// field_set(0x0000800000000000ULL) = 6
// field_set(0x0080000000000000ULL) = 7
// field_set(0x8000000000000000ULL) = 8

clang在三个x86_64指令中实现了这一点,不包括帧设置和清理:

_field_set:
    push   %rbp
    mov    %rsp,%rbp
    movabs $0x20406080a0c0e1,%rax
    imul   %rdi,%rax
    shr    $0x3c,%rax
    pop    %rbp
    retq

请注意,任何其他输入的结果将是非常随机的.(所以不要这样做.)

我认为没有任何可行的方法来扩展此方法直接返回7..63范围内的值(常量的结构不允许),但您可以通过将结果乘以结果将结果转换为该范围7点.

关于如何设计这个常数:我从以下观察开始:

• 无符号乘法是大多数CPU的快速操作,并且可以产生有用的效果.我们应该使用它.:)
• 将任何乘以零会导致零.由于这与无位设置输入的期望结果相匹配,因此到目前为止我们表现良好.
• 乘以任何东西1ULL<<63(即,你的"pos = 63"值)只能产生相同的值,或者为零.(它不可能设置任何较低的位,并且没有更高的位可以更改.)因此,我们必须找到一些方法将此值视为正确的结果.
• 使该值成为其自身正确结果的便捷方法是将其右移60位.这将它降低到"8",这是一个足够方便的表示.我们可以继续将其他输出编码为1到7.

• 将我们的常数乘以每个其他位字段相当于将其左移一个等于其"位置"的位数.右移60位使得给定位置左侧的4位仅出现在结果中.因此,我们可以创建除以下情况之外的所有情况:

   uint64_t constant = (
        1ULL << (60 - 7)
      | 2ULL << (60 - 15)
      | 3ULL << (60 - 23)
      | 4ULL << (60 - 31)
      | 5ULL << (60 - 39)
      | 6ULL << (60 - 47)
      | 7ULL << (60 - 55)
   );
  

到目前为止,常数是0x20406080a0c0e0ULL.但是,这并没有给出正确的结果pos=63; 这个常数是偶数,所以将它乘以该输入给出零.我们必须设置最低位(即constant |= 1ULL)才能使该情况起作用,给出最终值0x20406080a0c0e1ULL.

请注意,可以修改上面的结构以对结果进行不同的编码.但是,输出8如上所述是固定的,并且所有其他输出必须适合4位(即0到15).

Answer 2

这是一个可移植的解决方案,但它会比利用专用指令(如clz计数前导零)的解决方案慢.我在算法的每一步都添加了注释,解释了它的工作原理.

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

/* return position of set bit, if exactly one of bits n*8-1 is set; n in [1,8]
   return 0 if no bit is set
*/
int bit_pos (uint64_t a)
{
    uint64_t t, c;
    t = a - 1; // create mask
    c = t >> 63; // correction for zero inputs
    t = t + c; // apply zero correction if necessary
    t = t & 0x0101010101010101ULL; // mark each byte covered by mask
    t = t * 0x0101010101010101ULL; // sum the byte markers in uppermost byte
    t = (t >> 53) - 1; // retrieve count and diminish by 1 for bit position
    t = t + c; // apply zero correction if necessary
    return (int)t;
}

int main (void)
{
    int i;
    uint64_t a;
    a = 0;
    printf ("a=%016llx   bit_pos=%2d   reference_pos=%2d\n", a, bit_pos(a), 0);
    for (i = 7; i < 64; i += 8) {
        a = (1ULL << i);
        printf ("a=%016llx   bit_pos=%2d   reference_pos=%2d\n", 
                a, bit_pos(a), i);
    }
    return EXIT_SUCCESS;
}

此代码的输出应如下所示:

a=0000000000000000   bit_pos= 0   reference_pos= 0
a=0000000000000080   bit_pos= 7   reference_pos= 7
a=0000000000008000   bit_pos=15   reference_pos=15
a=0000000000800000   bit_pos=23   reference_pos=23
a=0000000080000000   bit_pos=31   reference_pos=31
a=0000008000000000   bit_pos=39   reference_pos=39
a=0000800000000000   bit_pos=47   reference_pos=47
a=0080000000000000   bit_pos=55   reference_pos=55
a=8000000000000000   bit_pos=63   reference_pos=63

在x86_64平台上,我的编译器转换bit_pos()为此机器代码:

bit_pos PROC 
        lea       r8, QWORD PTR [-1+rcx]
        shr       r8, 63
        mov       r9, 0101010101010101H
        lea       rdx, QWORD PTR [-1+r8+rcx]
        and       rdx, r9
        imul      r9, rdx
        shr       r9, 53
        lea       rax, QWORD PTR [-1+r8+r9]
        ret

[稍后更新]

duskwuff的回答让我清楚地知道我原来的想法是不必要的错综复杂的.事实上,使用duskwuff的方法,可以更简洁地表达所需的功能,如下所示:

/* return position of set bit, if exactly one of bits n*8-1 is set; n in [1,8]
   return 0 if no bit is set
*/
int bit_pos (uint64_t a)
{
    const uint64_t magic_multiplier = 
         (( 7ULL << 56) | (15ULL << 48) | (23ULL << 40) | (31ULL << 32) |
          (39ULL << 24) | (47ULL << 16) | (55ULL <<  8) | (63ULL <<  0));
    return (int)(((a >> 7) * magic_multiplier) >> 56);
}

任何合理的编译器都会预先计算魔术乘数,即0x070f171f272f373fULL.为x86_64目标发出的代码缩小为

bit_pos PROC 
        mov       rax, 070f171f272f373fH
        shr       rcx, 7
        imul      rax, rcx
        shr       rax, 56
        ret

Answer 3

如果您可以使用POSIX,请使用(不是!)中的ffs()函数.它返回最低有效位集的位置(一个索引)或如果参数为零则返回零.在大多数实现中,调用内联并编译到相应的机器指令中,就像在x86上一样.如果可用的话,glibc还有一些参数应该更适合您的问题.strings.hstring.hffs()bsfffsll()long long

Answer 4

值mod 0x8C为每种情况产生唯一值.

此值mod 0x11仍然是唯一的.

表中的第二个值是结果mod 0x11.

128 9
32768   5
8388608 10
2147483648  0
549755813888    14
140737488355328 2
36028797018963968   4
9223372036854775808     15

所以一个简单的查找表就足够了.

int find_bit(uint64_t bit){ 
  int lookup[] = { the seventeen values };
  return lookup[ (bit % 0x8C) % 0x11];
}

没有分支,没有编译器技巧.

为了完整性,数组是

{ 31, 0, 47, 15, 55, 0, 0, 7, 23, 0, 0, 0, 39, 63, 0, 0}

Answer 5

如果你想要一个算法而不是内置的算法,那就可以了.即使设置了多于一位,它也会产生最高1位的位数.它通过迭代地将所考虑的位范围划分为两半来缩小位置,测试在上半部分中是否设置了任何位,如果是,则将该半位作为新位范围,否则将下半部分作为新位范围.

#define TRY_WINDOW(bits, n, msb) do { \
    uint64_t t = n >> bits;           \
    if (t) {                          \
        msb += bits;                  \
        n = t;                        \
    }                                 \
} while (0)

int msb(uint64_t n) {
    int msb = 0;

    TRY_WINDOW(32, n, msb);
    TRY_WINDOW(16, n, msb);
    TRY_WINDOW( 8, n, msb);
    TRY_WINDOW( 4, n, msb);
    TRY_WINDOW( 2, n, msb);
    TRY_WINDOW( 1, n, msb);

    return msb;
}