C++ 中小于给定值 d 的十六进制所有数字减 1

Question

我有以下问题：我有一个 C++ 中的十六进制数（数据类型：std::uint64_t），该十六进制数包含从 1 到给定 n 的所有数字。我们还给出了另一个数字 d <= n。是否可以将十六进制数中大于或等于n的所有数字减1？这是我所期待的一个例子：

hex = 0x42513, d = 3 -> Result : 0x42513
                               - 0x10101 <- the zero's are there because the digits
                              ----------    over them are smaller than 3
                                 0x32412

我已经尝试过使用带有左移和右移的 for 循环来实现结果，但现在我感兴趣是否存在不使用循环而是仅使用位操作的解决方案？

Answer 1

有一些方法，即使d事先不知道。

使用SWAR平均值，

uint64_t L = 0x1111111111111111;
uint64_t v = L * d;
uint64_t decrementedHighNibbles = x - L + ((SWAR_AVG(~x, v, L) >> 3) & L);

在哪里：

uint64_t SWAR_AVG(uint64_t x, uint64_t y, uint64_t L) {
    return (x & y) + (((x ^ y) & ~L) >> 1);
}

对于其余的解释，我们只考虑一个半字节，标准 SWAR 技术负责将相同的操作应用于每个半字节。

该技巧的基础是，avg(~x, v)当且仅当 时， 的最高位才会被设置x < v。这与我们想要的条件相反，因此不是从该半字节中减去该半字节的最高位，而是先无条件地减去 1，然后如果该半字节小于 则有条件地加回 1 d。

只要d >= 1，半字节减 1 和加 1 就不需要特殊的 SWAR 加法/减法，因为下一个半字节不会自动借位（这种情况只有在从零的半字节中减 1 时才会发生）。在从每个半字节无条件减 1 的过程中，一些借位可能会在半字节之间交叉，但随后的加法将撤消这种情况。如果d可以为零，那么就需要更加小心。

这是使用“四舍五入”SWAR 平均值的替代方法。其中(x & y) + ((x ^ y) >> 1)计算平均值x并向y下舍入，(x | y) - ((x ^ y) >> 1)计算平均值x并向y上舍入。它的 SWAR 版本是：

uint64_t SWAR_AVG_UP(uint64_t x, uint64_t y, uint64_t L) {
    return (x | y) - (((x ^ y) & ~L) >> 1);
}

当在最高位中avg(~x, y)计算时，在最高位中计算。我们需要这样，所以使用：x < yavg_up(~x, y)x <= yx >= vSWAR_AVG_UP(x, ~v, L)

uint64_t decrementedHighNibbles = x - ((SWAR_AVG_UP(x, ~v, L) >> 3) & L);