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

cetgtptt  于 2023-01-18  发布在  其他
关注(0)|答案(3)|浏览(139)

我有以下问题:我有一个十六进制数(数据类型:std::uint64_t),十六进制数包含从1到给定n的所有数字。我们还给定了另一个数字d〈= n。是否可以从十六进制数的所有大于或等于n的数字中减去1?下面是我所期望的示例:

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

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

bmp9r5qi

bmp9r5qi1#

即使事先不知道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技术负责对每个半字节应用相同的操作。
这个技巧的基础是,当且仅当x < v时,avg(~x, v)的高位才会被置位,这与我们想要的条件相反,所以不是从半字节中减去半字节的高位,而是先无条件地减去1,然后如果半字节小于d,则有条件地加回1。
只要是d >= 1,则向半字节减1和加1不需要特殊的SWAR加/减,因为将不会自动借位到下一个半字节(这仅在从为零的半字节减去1时发生)。在从每个半字节无条件地减去1期间,一些借用可能在半字节之间交叉,但是这将被随后的加法撤销。如果d可以为零,那么这将需要更多的注意。
下面是另一种使用"向上舍入" SWAR平均值的方法。其中(x & y) + ((x ^ y) >> 1)计算xy向下舍入的平均值,(x | y) - ((x ^ y) >> 1)计算xy向上舍入的平均值。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);
nfzehxib

nfzehxib2#

这是可能的,而且对于常数d来说相当简单。
对于d=3和输入x的示例
注意,半字节〉= 3,如果

  • 8s位已设置 * 或 *
  • 4s位被设置 * 或 *
  • 2s位和1s位均置位

因此

subtrahend = ((x >> 3) | (x >> 2) | ((x >> 1) & x)) & 0x11111111;
result = x - subtrahend;

在无分支的代码中对变量d做这样的事情并不有趣,如果分支是可接受的,你可以简单地预先分析所有最小化的逻辑函数,然后使用switch (d)从中挑选。

bq9c1y66

bq9c1y663#

我不认为标准库中有任何对这个特定操作的支持,但是您可以为它创建自己的函数。

  • 创建一个index_sequence,将类型中的半字节数作为模板参数。
  • 通过右移提取每个半字节,并执行二进制AND0xF
  • 检查结果是否为您提供的限值的>=
  • 将布尔结果左移相同的位数。
  • 将结果与|的倍数合并。
#include <climits>
#include <type_traits>
#include <utility>

template <class T>
T sub(T val, std::type_identity_t<T> lim) {
    return val - [=]<std::size_t... I>(std::index_sequence<I...>) {
        return ((T((val >> (I * 4) & 0xF) >= lim) << (I * 4)) | ...);
    }(std::make_index_sequence<sizeof(T) * CHAR_BIT / 4>{});
}

Demo

相关问题