代码之家 › 专栏 › 技术社区 › LeopardSkinPillBoxHat

确定用户输入中存储差异所需的最小字段大小的有效方法

bit-manipulation c++

LeopardSkinPillBoxHat · 技术社区 · 14 年前

我从多个32位整数的用户那里得到一个输入。例如,用户可以输入以下值(为便于解释,以十六进制显示):

0x00001234
0x00005678
0x0000abcd

在这种特殊情况下,每个输入的前2个字节是常量,最后2个字节是变量。为了提高效率,我可以存储 0x0000 作为单个常量,并创建 uint16_t 存储输入变量部分的值( 0x1234 0x5678 , 0xabcd ).

现在假设用户输入以下内容:

0x00000234
0x56780000
0x00001000

在这种情况下,我需要一个向量 uint32_t 值存储输入的变量部分,因为每个值影响不同的字节。

uint32_t myVal = 0;
myVal |= input1;
myVal |= input2;
// ...

然后在最后找到第一个和最后一个“切换”之间的距离。 1 )咬入 myVal

然而,这听起来并不能很好地适应大量用户的输入。关于一种优雅而有效的方法来确定这一点有什么建议吗?

更新:

我在上面的解释中简化了这个问题。

为了清楚起见,我这样做并不是为了节省内存(我有更好的事情要做,而不是试图保存几个字节,这不是为了优化目的)。

总之,组件A为系统中的组件B提供值。有时这些值为128位,但组件B仅支持32位值。

如果128位值的可变部分可以用32位值表示,我可以接受它。否则我就需要错误地拒绝它。

我不能修改组件B以允许128位值,也不能修改组件a以防止使用128位值(这里也有硬件限制)。

5 回复 | 直到 14 年前

Kirill V. Lyadvinsky 14 年前

尽管我看不出这一切的原因。。。为什么不将输入与 std::numeric_limits<uint16_t>::max() ? 如果输入值较大,则需要使用 uint32_t

回答您的编辑:

我认为为了获得更好的性能,您应该使用特定于硬件的低级指令。您可以迭代输入128位值的32位部分,然后将每个部分添加到某个变量中,并检查下一个值与当前和之间的差异。如果差值不等于和,那么应该跳过这个128位的值,否则最终会得到必要的结果。样本如下:

uint32_t get_value( uint32_t v1, uint32_t v2, uint32_t v3, uint32_t v4)
{
  uint32_t temp = v1; 
  if ( temp - v2 != temp ) throw exception;
  temp += v2; if ( temp - v3 != temp ) throw exception;
  temp += v3; if ( temp - v4 != temp ) throw exception;
  temp = v4;
  return temp;
}

Tony Delroy 14 年前

存储遇到的第一个完整的128位数字,然后将其低位32位推到向量上,设置 bool reject_all = false reject_all = true ,否则将它们的低阶位推到向量上。在循环结束时,使用reject_all来决定是否使用值的向量。

Jonathan Grynspan 14 年前

在范围内存储一系列无符号整数的最有效方法 [0, (2^32)-1] 只是通过使用 uint32_t 老死早在任何现代系统出现记忆限制之前。

Dean Michael 14 年前

算法将类似于您已经做过的事情:

unsigned long long bitmask = 0uL;
std::size_t count = val.size();
for (std::size_t i = 0; i < count; ++i)
  bitmask |= val[i];

然后,您可以检查前导/尾随的位/字节数是否可以设为常量,以及是否要使用完整的32位。如果您可以访问SSE指令,则可以使用OpenMP将其矢量化。

还有一种可能的优化方法是短路,看看第一个 1 一点一滴 1个 位已经大于32,在这种情况下可以停止。

为了更好地扩展这个算法,您必须并行地执行它。你的朋友可能是矢量处理(可能在Nvidia gpu上使用CUDA,或者在Mac上或已经支持OpenCL的平台上使用OpenCL,或者只使用OpenMP注释)。

JohnPS 14 年前

使用

uint32_t ORVal = 0;
uint32_t ANDVal = 0xFFFFFFFF;

ORVal  |= input1;
ANDVal &= input1;
ORVal  |= input2;
ANDVal &= input2;
ORVal  |= input3;
ANDVal &= input3; // etc.

// At end of input...
mask = ORVal ^ ANDVal; 
// bit positions set to 0 were constant, bit positions set to 1 changed

一点位置 ORVal 将 1 1个 在那个位置上 0 如果所有输入都有在那个位置。一点位置 ANDVal 将如果至少有一个输入 0个 在那个位子上 1个 如果所有输入都有 1个

如果输入中的位位置总是 1个 奥瓦尔 和 安德瓦尔 1个 . 如果输入中的位位置总是 ,然后 奥瓦尔 和 安德瓦尔 都会被设置为 0个 如果有和在一个小位置 奥瓦尔 将设置为 1个 安德瓦尔 0个 ,因此 XOR