Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Bitwise AND operation backwards

  1. Aug 5, 2011 #1
    1. The problem statement, all variables and given/known data

    At my company we calculate a product's serial number from a MAC address provided with the unit. One of the equations is done with a bitwise AND operation of two integers. I have tried to run that equation backwards but with no result.

    Variables and data:

    V = The source value to do the bitwise AND operation with
    C = A known constant to use in the bitwise AND operation
    S = Result of bitwise AND operation

    Let say: V = 10, C = 6

    2. Relevant equations

    The equation forward is: V & C = S => 10 & 6 = 2

    In binary:

    1010 = 10
    0110 = 6
    -----
    0010 = 2


    Now I just want to reverse that process and calculate 10 from 6 and 2 in some way.

    Don't try with: C + 2S (6 + (2*2)) works just in this case.

    3. The attempt at a solution

    I tried the opposite way by changing V for S:

    2 & 6 = 2

    In binary:

    0010 = 2
    0110 = 6
    -----
    0010 = 2


    The problem occurs when one of the bits in the V is 1 and the equivalent bit in C is 0. The bit in S will then be 0 and V's bit can never return to 1.

    Any suggestions?

    /Mc_Topaz
     
  2. jcsd
  3. Aug 5, 2011 #2

    uart

    User Avatar
    Science Advisor

    Unfortunately that's just not possible as it's a many to one mapping. Of the three main two input binary operators (AND OR XOR) only XOR is invertible like that.
     
  4. Aug 5, 2011 #3
    It would be possible if you also knew V & ~C, though. Since A & B only has ones where both A and B have ones, and ~B has ones only where B has zeros, V & ~C has the 'missing ones' from the other calculation.
     
  5. Aug 5, 2011 #4

    uart

    User Avatar
    Science Advisor

    Actually "V" is the thing he's trying to find (given S and C). Knowledge of ~C provides no new information and doesn't help with the original problem. Since he knows C then he already knows ~C anyway.
     
    Last edited: Aug 5, 2011
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook