我有以下问题:我有一个十六进制数(数据类型: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循环来获得结果,但是现在我感兴趣的是是否存在不使用循环而是仅使用位操作的解决方案?
3条答案
按热度按时间bmp9r5qi1#
即使事先不知道
d
,也有一些方法。使用SWAR平均值,
其中:
对于其余的解释,让我们只考虑一个半字节,标准的SWAR技术负责对每个半字节应用相同的操作。
这个技巧的基础是,当且仅当
x < v
时,avg(~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版本为:当
avg(~x, y)
在高位计算x < y
时,avg_up(~x, y)
在高位计算x <= y
,我们需要x >= v
,所以使用SWAR_AVG_UP(x, ~v, L)
:nfzehxib2#
这是可能的,而且对于常数
d
来说相当简单。对于
d=3
和输入x
的示例注意,半字节〉= 3,如果
因此
在无分支的代码中对变量
d
做这样的事情并不有趣,如果分支是可接受的,你可以简单地预先分析所有最小化的逻辑函数,然后使用switch (d)
从中挑选。bq9c1y663#
我不认为标准库中有任何对这个特定操作的支持,但是您可以为它创建自己的函数。
index_sequence
,将类型中的半字节数作为模板参数。AND
0xF
。>=
|
的倍数合并。Demo