我想在标准C中将任何大小整数的前导零位设置为1。
例如。
0001 0011 0101 1111 -
我发现的所有算法都需要相当昂贵的前导零计数。然而,这很奇怪。有非常快速和简单的方法来进行其他类型的位操作,例如:
int y = -x & x; //Extracts lowest set bit, 1110 0101 -> 0000 0001
int y = (x + 1) & x; //Will clear the trailing ones, 1110 0101 - > 1110 0100
int y = (x - 1) | x; //Will set the trailing zeros, 0110 0100 - > 0110 0111
这让我想到一定有一种方法可以在一行简单的代码中设置整数的前导零,这些代码由基本的位明智运算符组成。请告诉我有希望,因为现在我正满足于反转整数中的位顺序,然后使用设置尾随零的快速方法,然后再次反转整数以将前导零设置为1。这实际上比使用前导零计数要快得多,但是与上面的其他算法相比仍然很慢。
template<typename T>
inline constexpr void reverse(T& x)
{
T rev = 0;
size_t s = sizeof(T) * CHAR_BIT;
while(s > 0)
{
rev = (rev << 1) | (x & 0x01);
x >>= 1;
s -= 1uz;
}//End while
x = rev;
}
template<typename T>
inline constexpr void set_leading_zeros(T& x)
{
reverse(x);
x = (x - 1) | x;//Set trailing 0s to 1s
reverse(x);
}
因为有些人问:我正在使用MS-DOS运行在CPU上,从早期的X86到安装在旧CNC机床中的486DX。欢乐时光。:D
你的反面
非常慢!使用 N 位 int 时,您需要 N 次迭代来反转,每次至少 6 条指令,然后至少 2 条指令来设置尾随位,最后 N 次迭代以再次反转该值。OTOH即使是最简单的前导零计数也只需要N次迭代,然后直接设置前导位:
template<typename T>
inline constexpr T trivial_ilog2(T x) // Slow, don't use this
{
if (x == 0) return 0;
size_t c{};
while(x)
{
x >>= 1;
c += 1u;
}
return c;
}
template<typename T>
inline constexpr T set_leading_zeros(T x)
{
if (std::make_unsigned_t(x) >> (sizeof(T) * CHAR_BIT - 1)) // top bit is set
return x;
return x | (-T(1) << trivial_ilog2(x));
}
x = set_leading_zeros(x);
还有许多其他方法可以更快地计算前导零/获取整数对数。其中一种方法涉及按照2的幂步骤进行操作,例如如何在harold的答案中创建面具:
但是由于你是针对一个特定的目标而不是跨平台做一些事情,并且想要压缩每一点性能,所以几乎没有理由使用纯标准特性,因为这些用例通常需要特定于平台的代码。如果内部函数可用,你应该使用它,例如在现代C中,有std::countl_zero
,但是每个编译器已经有内部函数来做这件事,它将映射到该平台的最佳指令序列,例如_BitScanReverse
或__builtin_clz
如果内在函数不可用,如果性能仍然不够,则尝试查找表。例如,这是一个具有256元素日志表的解决方案
static const char LogTable256[256] =
{
#define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
-1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6),
LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7)
};
uint16_t lut_ilog2_16(uint16_t x)
{
uint8_t h = x >> 8;
if (h) return LogTable256[h] + 8;
else return LogTable256[x & 0xFF];
}
在< code>set_leading_zeros中,只需像上面那样调用< code>lut_ilog2_16
比日志表更好的解决方案是掩码表,这样您可以直接获得掩码,而不用计算< code>1
static const char MaskTable256[256] =
{
0xFF, 0xFE, 0xFC...
}
其他一些注意事项:
您可以使用< code>std::countl_zero计算前导零,并创建一个位掩码,与原始值进行位或运算:
#include <bit>
#include <climits>
#include <type_traits>
template<class T>
requires std::is_unsigned_v<T>
T leading_ones(T v) {
auto lz = std::countl_zero(v);
return lz ? v | ~T{} << (CHAR_BIT * sizeof v - lz) : v;
}
如果您有标准::uint16_t
,喜欢
0b0001001101011111
然后~T{}
是0b1111111111111111
,CHAR_BIT*sizeof v
是16,countl_zero(v)
是3
。左移0b11111111111111
16-3步骤:
0b1110000000000000
按位或与原始:
0b0001001101011111
| 0b1110000000000000
--------------------
= 0b1111001101011111
可以设置前导零而不对它们进行计数,同时还可以避免反转整数。为了方便起见,我不会对通用整数类型T执行此操作,但可能会对其进行调整,或者您可以使用模板专用化。
首先计算所有不是前导零的位的掩码,方法是向下“展开”位:
uint64_t m = x | (x >> 1);
m |= m >> 2;
m |= m >> 4;
m |= m >> 8;
m |= m >> 16;
m |= m >> 32;
然后设置该掩码未覆盖的所有位:
return x | ~m;
奖励:即使 x = 0
并且当 x
设置了所有位时,这也会自动工作,其中一个在计数-前导-零方法中可能会导致过大的移位量(这取决于细节,但几乎总是其中一个是麻烦的,因为有65个不同的情况,但只有64个有效的移位量, 如果我们在谈论uint64_t
)。
问题内容: 给定以下示例: 输出为: 为什么? 问题答案: 这是因为前导零的整数文字是八进制整数(以8为底):
问题内容: 我有下面的代码 和输出是 我期望输出如下。 当我打印直接int值时,为什么会给出?我期望Java自动将值从零开始转换为八进制。 和之间是什么关系? 问题答案: 前导0表示一个八进制数(以8为底)。 01111(八进制)是1 * 8 ^ 3 + 1 * 8 ^ 2 + 1 * 8 ^ 1 + 1 * 8 ^ 0 = 585(十进制) 将十进制数字1111转换为八进制字符串。八进制2127
问题内容: 尝试这个: 因为什么时候40 = 32? 问题答案: 带有前导零的数字将解释为八进制和。
我有一堆荧光标记的细胞。 样本有一个人工制品,在细胞内引起非常明亮的区域,这些区域不是基于我感兴趣的信号。 由于这些人工制品的强度(亮度)远高于我感兴趣的信号强度,我想简单地将高于我将选择的某个任意值的所有像素归零。 所以我想要一个宏,它在逻辑上执行如下操作: 对于每个切片: 对于每个像素: 我用imageJ宏语言编码。我想避免在这个部分中使用ROI,因为我已经有了表示每个单元格的ROI,并且在脚
我有一个JFrame,我已经将布局设置到GroupLayout。 我添加了两个Jpanel即workingPanel(红色)和backgroundPanel(绿色)。 代码是`import javax.swing.;导入java.awt; 请帮帮我。
我想在内部设置一个的。 我试着用 但这不起作用。我怎么能这么做?