中间位与模式匹配的下一个最大整数？

问题描述：

一个位掩码的宽度nmask和一些偏移k> = 0
在一些1S（但不一定是全部），其中所述位掩码具有的位置的位模式pattern 1秒。
val

我想找到一个最大的整数result使得整数

result > val
result & mask == pattern

例如，假设mask = 0xFF00和pattern = 0x0100。由此，我们得到以下结果：

NextLargest(mask, pattern, 0x00000) => 0x00100 
NextLargest(mask, pattern, 0x000FF) => 0x00100 
NextLargest(mask, pattern, 0x010FE) => 0x001FF 
NextLargest(mask, pattern, 0x010FF) => 0x10100

另一个例子 - 说mask = 0xF和pattern = 0xF。然后，我们预计：

NextLargest(mask, pattern, 0x20) => 0x2F.

我已经试过像“带出的是mask关心，增加，或早在pattern并返回位”，但我一直打的边缘情况。这个问题就像寻找某个整数的下一个最大倍数的概括。

这里是我的尝试，到目前为止（可运行链接：https://ideone.com/AhXG5M）：

#include <iostream> 
using namespace std; 

using uint32 = unsigned long; 

uint32 NextLargest(int width, int offset, uint32 mask, uint32 pattern, uint32 val) { 
    unsigned long long ret = (val + 1) & ~mask; 
    if ((ret & ((1 << (offset + 1)) - 1)) == 0) { 
     // "carry" across the mask 
     ret += 1 << (offset + width); 
    } 
    return ret | pattern; 
} 

int main() { 
    // your code goes here 
    int width = 12; 
    int offset = 4; 

    uint32 significant_bits = (1 << (width + 1) - 1) << offset; 
    uint32 wanted_bits = 0xFFF << offset; 

    cout << hex; 
    // want 0xFFF1 -- correct 
    cout << NextLargest(width, offset, significant_bits, wanted_bits, 0) << endl; 
    // want 0xFFF2 -- correct 
    cout << NextLargest(width, offset, significant_bits, wanted_bits, 1) << endl; 
    // want 0x1FFFF0 -- incorrect, get 0xFFF0 
    cout << NextLargest(width, offset, significant_bits, wanted_bits, 0xF) << endl; 

    return 0; 
}

这是真的为'VAL＆mask'等于'pattern'呢？ –

@Ron大概是因为这是在C++中完成的？这是相关的，因为不同的语言可以提供不同的位操作功能，即使它们大部分是相同的，或者可能有一个有用的库函数或其他东西。为什么*不会相关？ –

'NextLargest（mask，pattern，0x010FF）=> 0x101FF'应该不是'=> 0x10100'？ – user2079303

答

想到将value分解为3. 掩码上方的位，掩码中和掩码下方的位。 H(value)，M(value)，L(value)。

我们知道M(result)==pattern。我们有三个候选人。

C1是H(value)+pattern+0。

C2是

C3是H(value)+pattern+X

X==(mask<<1)&~mask。这是mask以上的最低位。

如果pattern>M(value)我们可以使用C1。减少高位将得到一个数字<value，设置任何低位将增加数量。

如果pattern==M(value)那么我们可以尝试C2，它实际上是value+1。如果向模式位添加一个溢出，则会失败。

这意味着所有的低位被设置，并且下一个要添加的最低位置是掩模上方的第一位。

unsigned next_masked(unsigned mask,unsigned pattern,unsigned value){ 
    unsigned reduced_pattern=(mask&pattern);//May not be required... 
    unsigned over_add=(mask<<1)&~mask; 
    unsigned upper_mask=~(over_add-1); 
    unsigned cand=(value&upper_mask)|reduced_pattern; 
    if(cand>value){ 
     return cand; 
    } 
    if((value&mask)==reduced_pattern){ 
     unsigned scand=value+1; 
     if((scand&mask)==reduced_pattern){ 
      return scand; 
     } 
    } 
    return cand + over_add; 
}

这又是一些单元测试：

#include <iostream> 

unsigned next_masked(unsigned mask,unsigned pattern,unsigned value){ 
    unsigned reduced_pattern=(mask&pattern);//May not be required... 
    unsigned over_add=(mask<<1)&~mask; 
    unsigned upper_mask=~(over_add-1); 
    unsigned cand=(value&upper_mask)|reduced_pattern; 
    if(cand>value){ 
     return cand; 
    } 
    if((value&mask)==reduced_pattern){ 
     unsigned scand=value+1; 
     if((scand&mask)==reduced_pattern){ 
      return scand; 
     } 
    } 
    return cand + over_add; 
} 

bool invariant_next_masked(unsigned mask,unsigned pattern,unsigned value,unsigned result){ 
    if((result&mask)!=(pattern&mask)){ 
     return false; 
    } 
    if(result<=value){ 
     return false; 
    } 
    for(unsigned test=result-1;test>value;--test){ 
     if((test&mask)==(pattern&mask)){ 
      return false; 
     } 
    } 
    return true; 
} 

int check_next_masked(unsigned mask,unsigned pattern,unsigned value,unsigned expect){ 
    unsigned result=next_masked(mask,pattern,value); 
    if(result!=expect){ 
     std::cout << std::hex << mask << ' ' << std::hex << pattern << ' ' << std::hex <<value << "==" << std::hex <<result << "!=" << std::hex <<expect <<'\n'; 
       return 1; 
    } 
    if(!invariant_next_masked(mask,pattern,value,result)){ 
     return 1; 
    } 
    return 0; 
} 

int main() { 
    int errors=0; 

    errors+=check_next_masked(0xFF00,0x0100,0x0000,0x00100); 
    errors+=check_next_masked(0xFF00,0x0100,0x00FF,0x00100); 
    errors+=check_next_masked(0xFF00,0x0100,0x10FE,0x10100);   
    errors+=check_next_masked(0xFF00,0x0100,0x1067,0x10100); 
    errors+=check_next_masked(0xFF00,0x0100,0x10123,0x10124); 
    errors+=check_next_masked(0xFF00,0x0100,0x110FF,0x20100); 
    errors+=check_next_masked(0xFF00,0x0100,0x102FF,0x20100); 
    errors+=check_next_masked(0xFF00,0x0100,0x101FF,0x20100); 
    errors+=check_next_masked(0x000F,0x0007,0x10123,0x10127); 
    errors+=check_next_masked(0x000F,0x0007,0x10128,0x10137); 
    errors+=check_next_masked(0x0FF0,0x0230,0x10128,0x10230); 
    errors+=check_next_masked(0x0FFF0,0x,0x,0x); 
    errors+=check_next_masked(0x0FFF0,0x,0x41237,0x41238); 
    errors+=check_next_masked(0x0FFF0,0x,0x4123F,0x51230); 


    if(errors>0){ 
     std::cout << "Errors "<< errors << '\n'; 
     return 1; 
    } 
    std::cout << "Success\n"; 
    return 0; 
}

答

我没有测试这一点，但下面的算法应该工作（伪）：

let mask, pattern, and val be inputs 
let fls be function that finds last bit set in word 
let ffs be function that finds first bit set in a word 

let applied be (val & ~mask) | pattern 
if applied is greater than val then 
    return applied 
let low_order_mask be (1 << ffs(mask)) - 1 
if applied == val then 
    let flipped_low be (~value & low_order_mask) 
    if not flipped_low then 
     return applied + 1 // no need to carry 
// need to carry 
let set_low_zero be applied & ~low_order_mask 
let carry be 1 << (fls(mask) + 1) 
return set_low_zero + carry

fls和ffs由POSIX提供，但其他系统可能不这样做。如果你需要的话，SO上有答案。

太棒了，这看起来很合理。我将扩展我的实现并使用完整版本更新答案。 'fls'和'ffs'是整洁的，我从来没有见过。对于'any_low_zero = value^low_order_mask;如果没有任何低零，那么' - 可以简化为'如果value == low_order_mask'，对不对？因此，整个分支可以成为'如果应用== val == low_order_mask然后返回应用+ 1'。或者我误解了？ –

@PatrickCollins你的结论是合理的，但它唤醒我的事实，我的代码是越野车。重点是测试低阶位是否为零，并忽略休息。有一个掩码操作丢失。 – user2079303

@PatrickCollins现在应该会更好。此外，我的ffs使用情况缺乏重要的轮班操作。 – user2079303

答

是计算出的问题LARGEST或SMALLEST下一个值？最大的价值似乎很奇怪。如果要求是计算最小值，我认为这种代码应该工作：（上GCC 7.1测试，假设64位目标，的sizeof（无效*）==的sizeof（为size_t）==的sizeof（uint64_t中））

size_t next_smallest_value (size_t mask, size_t pattern, size_t x) { 
    assert(pattern & mask == pattern); 
    // only change bits within mask range to meet the requirement 
    auto y = x & ~mask | pattern; 
    if (y > x) { 
     // if the operation increased the value 
     // mask off all the lower bits 
     auto lsb_mask = __builtin_ctzll(mask); 
     return y & ~ones(lsb_mask); 
    } else { 
     // otherwise, the operation decreased or didn't change the value 
     // need to increase the fraction higher than the mask 
     auto msb_mask = 63 - __builtin_clzll(mask); 
     // higher part cannot be empty if the masked part decrease 
     assert(msb_mask < 63); 
     auto higher = ((y >> msb_mask) + 1) << msb_mask; 
     // also higher part cannot overflow 
     assert(higher != 0); 
     return y & mask | higher; 
    } 
}

的想法是很简单的：将所述位分成3个部分：较高的部分，遮蔽部分，下部。掩蔽部分可以直接从中导出，并且通过mask和pattern确定的，它不能是其它值。

计算掩码位后，如果该值增加，只是屏蔽掉所有位在下部。否则，将高位部分增加1（并且屏蔽掉所有低位）。

上面的代码不与形成不良的输入处理，它会触发断言，但检查没有用尽。

不幸的是，我在我的用例中有一个要求，我发现下一个最大的而不是下一个最小的。尽管感谢你的工作。 –

我不明白你的意思是术语*次最大值*？你的榜样是我也不清楚，好像在讨论的第一个例子：给定'面膜= 0xff00'和'模式= 0x0100'，你说'NextLargest（面具，模式，0x00000）=> 0x00100'，我相信（32位）*最大* 0xffff01ff是* NOT *你想要的，但不会'0x01ff'大于'0x0100'并且仍然符合这个意义上的要求？对于第二个例子，它应该是“0x0100”还是“0x01ff”？而第三个例子根本不会大于输入。这就是为什么我很困惑。或者我错过了什么？ –

答

这个有点令人困惑的问题有两个函数第一个函数给出了满足结果要求的最大下一个整数。第二个给出SMALLEST下一个值。

1：获取满足result & mask == pattern和result > val的最大整数：

unsigned NextLargest (unsigned mask, unsigned pattern, unsigned val) { 

    // zero "mask" bits and set "pattern" bits in largest (unsigned) int 
    unsigned const x = ~mask | pattern; 

    // if result is not greater than val, we can't satisfy requirements 
    if (x <= val) { 
     ... report error, return error code or throw something 
    } 

    return x; 
}

显然，这只是返回符合要求result & mask == pattern和result > val最高（无符号）的整数值。 if子句检查结果是否不会大于val，并且该函数将失败。

2：获取val后最小的下一个值满足要求：

unsigned NextSmallest (unsigned mask, unsigned pattern, unsigned val) { 

    unsigned const x = (val + mask + 1) & ~mask | pattern; 

    if (x <= val) { 
     ... increment wrapped, can't give greater value 
    } 

    return x; 
}

编辑：改变(val|mask)到val+mask因为其结果必然是仍然比val更大。

该函数计算val + 1并通过mask'd位传送溢出位。下面是几个例子的功能是什么，如果mask = 0x0ff00和pattern = 0x00500：

val  +mask +1  &~mask  |pattern == result 

0x00000 0x0ff00 0x0ff01 0x00001 0x00501 
0x00001 0x0ff01 0x0ff02 0x00002 0x00502 
0x000fe 0x0fffe 0x0ffff 0x000ff 0x005ff 
0x000ff 0x0ffff 0x10000 0x10000 0x10500 
0x00100 0x10000 0x10001 0x10001 0x10501 
0x0f000 0x1ef00 0x1ef01 0x10001 0x10501 
0x0ff00 0x1fe00 0x1fe01 0x10001 0x10501 
0x0ffff 0x1feff 0x1ff00 0x10000 0x10500 
0x10000 0x1ff00 0x1ff01 0x10001 0x10501 
0x10001 0x1ff01 0x1ff02 0x10002 0x10502 
0x100ff 0x1ffff 0x20000 0x20000 0x20500

经过长期的编辑和重写我仍然不能给出这个问题足够好的答案。它的例子有奇怪的结果。如果有人发现这些功能或其中的一部分功能有用，我仍然留在这里。此外，我没有实际测试电脑上的功能。

中间位与模式匹配的下一个最大整数？

相关推荐