All geek questions in one place

The next largest integer with some middle bits matching the pattern?

My input:

  • maskwidth mask bit nand some offset k> = 0
  • bit pattern patternwith 1s in some (but not necessarily all) positions, where the bit bit has 1s.
  • integer val

I want to find the following largest integer resultsuch that:

  • result > val
  • result & mask == pattern

For example, suppose mask = 0xFF00and pattern = 0x0100. Then we expect the following result:

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

Another example is say mask = 0xFand pattern = 0xF. Then we expect:

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

- " , mask , , pattern ", . - .

(runnable link: 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;
}
+4
4

value, 3. , . H(value), M(value), L(value).

M(result)==pattern. .

C1 - H(value)+pattern+0.

C2 H(value)+pattern+L(value)+1

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,0x01230,0x01231,0x01232);
    errors+=check_next_masked(0x0FFF0,0x01230,0x41237,0x41238);
    errors+=check_next_masked(0x0FFF0,0x01230,0x4123F,0x51230);


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

, ():

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 , , .

+3

- LARGEST 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 ( ).

, , .

0

, . 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;
}

edit: (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

. . , - . , .

0

Source: https://habr.com/ru/post/1685118/

More articles:


All Articles