c++ - 从 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，然后如果该半字节小于 d，则有条件地加回 1。 .

只要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 < y在最高位，avg_up(~x, y)计算 x <= y在最高位。我们需要 x >= v所以，所以使用 SWAR_AVG_UP(x, ~v, L) :

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