How to randomize number under constrains

I have a parser which should take as an input a string of constrains (one or more), and as output it should randomize some number that hold the constrain (the constrain should be zero after the variable are randomized).

For example, if the constrain is: "x & 1" the output should be randomization of x with the first bit clear, for instance: "x = 0x2".

Another example if the constrain is: "x & (y | 1)" then x and y can't have the same bit position set, and also bit 0 of x can't be set, so output can be: "x = 0x2, y = 0x1"

The first solution I implemented was to randomize the variables and check if the constrains hold in a loop, something like:

for (i=0; i<MAX_ITERATION; i++) {
    foreach var in variables {
        randomize var
    }
    if (variables hold constrain){
        return variables
    }
}

the problem is that for a constrain like: `x & 0xfffffffe" this can take too much time.

Does anyone have better idea of how to approach this?

Any idea will be appreciated.