I am trying to find the bitshift operators required to do a specific transformation

50381044488375 > 630
50376749521075 > 629
50398224357551 > 628
50389636520755 > 632

All of these transformations are done with the same bithift/bitoperator. 50389636520755L >> 3 & 0x7FF was suppose to work but it is giving me 870. Am I able to find the proper bitshift between these numbers?

CodePudding user response：

Most of the bits for these numbers are the same, so let's start by writing them out in binary, and highlighting all the bits where they are different:

1011011101001001000000010000101001100010110111 → 1001110110 1011011101000101000000010000101001100010110011 → 1001110101 1011011101011001000000010000101001100010101111 → 1001110100 1011011101010001000000011000101001101100110011 → 1001111000

We would like to find shifts which map columns from the left onto columns on the right. The first and second columns on the right (01,01,01,10) can be found on the left, as can the fourth column on the right (0,1,0,0), but the third column on the right (1,0,0,0) does not exist on the left, so we will need to form it by some operation on two columns on the left. Fortunately we can find two columns (1,1,0,1) and (1,0,1,0) whose bitwise & is what we require.

So a full solution is like this:

long mapping(long x) {
    return 0b1001110000                // the constant output bits
        | (x >> 5) & 0b1100            // first two output bits
        | (x >> 3) & (x >> 1) & 0b0010 // third output bit
        | (x >> 32) & 0b0001;          // fourth output bit
}

CodePudding user response：

If you need a Boolean Expression, you simply could derive the truth table (one for every output bit) using some library as LogicNG. The process to follow is

• name every input bit x0, x1, ... (for long values up to x63).
• for every output bit r0, r1, ... get a boolean expression as follows
  • use every input number N to form a row of the Truth Table
  • the bit result for that row is the r-th bit for the result value for the input N
• once you get every r-th boolean expression from the truth tables, join all of them using OR replacing every x-th variable with (x << th) and you'll get one unique boolean expression.

Note: your example is 0x270L | (15 & (n / 449 - n / 763)), yes, dividing by a constant is "directly" transformable to a bit operation https://embeddedgurus.com/stack-overflow/2009/06/division-of-integers-by-constants/