中位のビットがパターンに一致する次の整数。

Question

私の入力がある：

• ビット幅nのmaskをマスクし、いくつかはk一部に1Sと> = 0
• ビットパターンpattern（必ずしも全てではない）のビットマスクが有する位置をオフセット1s。
• 私はresultような次の最大の整数を見つけたいval

整数：例えば

• 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; 
} 

Answer 1

valueを3に分割して考えてください。 マスクの上、マスクの下、マスクの下のビット。 H(value),M(value),L(value)。

われわれはM(result)==patternを知っています。 私たちは3人の候補者を持っています。

C1は、H(value)+pattern+0である。

C2は​​

C3はH(value)+pattern+X

X==(mask<<1)&~maskです。それはmaskの上の最下位ビットです。

pattern>M(value)の場合、C1を使用できます。 上位ビットを減らすと、数字は<valueになり、下位ビットを設定すると数字が大きくなります。

pattern==M(value)の場合、実際にはvalue+1であるC2を試すことができます。 パターンビットにオーバーフローが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; 
} 

Answer 2

が、私はこれをテストしていないが、次のアルゴリズムが動作するはずです：

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の回答があります。

Answer 3

は最大又はSMALLEST次の値を計算する問題です？最大値は奇妙に見える。最小の値を計算する必要がある場合、このコードは動作するはずです：（gcc 7.1で、64ビットのターゲットを想定し、sizeof（void *）== 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だけ増やします（また、すべての下位ビットをマスクします）。

上記のコードは不正な入力を処理しませんが、アサーションをトリガーしますが、チェックは使い果たされません。

Answer 4

ここではちょっと混乱しやすい質問の2つの関数 最初の関数は結果の要件を満たす次の最大の整数を返します。 2番目の値は、次のSMALLEST値を示します。

---

1：明らか

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を満たす最高（符号なし）整数値を返す：result & mask == patternとresult > valを満たす最大の整数を取得します。 if節は、結果がvalより大きくないかどうかをチェックし、関数は失敗します。

---

2：

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より大きくなければなりませんのでval+maskに(val|mask)を変更された要件を満たしているval後SMALLEST次の値を取得します。

この関数は、val + 1を計算し、オーバーフロービットをmaskのdビット以上に渡します。長い編集後

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 

と私はまだ質問には十分に良い答えを与えることはできません書き換え：mask = 0x0ff00場合とpattern = 0x00500ここ は、関数が何をするか、いくつかの例です。その例には奇妙な結果があります。もし誰かがこれらの機能やその一部を役に立つと思ったら、私はまだここに残しておきます。また、私は実際にコンピュータ上の関数をテストしませんでした。