将 uint64_t 的位复制到特定位置的两个 uint64_t

Question

我有一个输入 uint64_t X 及其 N 最低有效位的数量，我想将其写入目标 Y、Z uint64_t 值从 Z 中的位索引 M 开始。 Y 和 Z 未受影响的部分不应更改。我如何在 C++ 中为最新的英特尔 CPU 高效地实现它？

在循环中执行应该是高效的。我想它需要没有分支：使用的指令数量应该是恒定的并且尽可能小。

M 和 N 在编译时不固定。 M 可以取 0 到 63（Z 中的目标偏移量）之间的任何值，N 的范围为 0 到 64（要复制的位数）。

插图：

Answer 1

在合理的现代 IA 处理器上至少有四个指令序列可用。

X &= (1 << (N+1)) - 1;     // mask off the upper bits
//  bzhi    rax, rdi, rdx

Z = X << M;                
//  shlx    rax, rax, rsi

Y = X >> (64 - M);         
//  neg     sil
//  shrx    rax, rax, rsi

值 M=0 会造成一些麻烦，因为在这种情况下 Y 需要为零，而且表达式 N >> (64-M) 也需要清理。

克服这个问题的一种可能性是

x = bzhi(x, n);
y = rol(x,m);
y = bzhi(y, m);   // y &= ~(~0ull << m);
z = shlx(x, m);   // z = x << m;

由于 OP 实际上想要更新位，一个明显的解决方案是复制掩码的逻辑：

xm = bzhi(~0ull, n);
ym = rol(xm, m);
ym = bzhi(ym, m);
zm = shlx(xm, m);

然而，clang 似乎总共产生了大约 24 条指令，并应用了掩码：

Y = (Y & ~xm) | y; // |,+,^  all possible
Z = (Z & ~zm) | z;

改变方法可能会更好：

x2 = x << (64-N);  // align xm to left
y2 = y >> y_shift; // align y to right
y = shld(y2,x2, y_shift); // y fixed

这里y_shift = max(0, M+N-64)

修复 Z 稍微复杂一些，因为 Z 可以由三部分组合而成：

zzzzz.....zzzzXXXXXXXzzzzzz, where m=6, n=7

如上两个双班应该可以做到。

将 uint64_t 的位复制到特定位置的两个 uint64_t

Copy bits of uint64_t into two uint64_t at specific location

c++

x86

bit-manipulation

bmi