Rerversing AND Bitwise.

Question

Hey all,

Here's the following algorithm:

int encryption(int a, int b) {
    short int c, c2;
    uint8_t d;

    c = a ^ b;
    c2 = c;

    d = 0;
    while(c) {
        c &= c - 1;
        d++;
    }

    return d;
}

How can I find which variable a and b I should send in that function to decide of the output value of d?

In other words, how can I reverse the algoritm to let's say if I want d=11?

Answer 1

d is just the number of "1" bits in c, see http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan.

Therefore, you just need to find a and b such that their bitwise-XOR value has exactly 11 bits, e.g. a = 0 and b = 2047.

(This is not encryption. This is a very weak one-way hashing. An encryption have to provide a way to get back the original value (decryption).)

Answer 2

I see it counts SET bits in a XOR b?

Ok, then let's say a==0, b==4095.

Answer 3

This:

while(c) {
    c &= c - 1;
    d++;
}

counts the number of 1-bits in c. So for example, if c = 10110, d will be 3.

This:

c = a ^ b;

Does an exclusive or between a and b. This means that all the 1-bits that share the same position in both a and b will be zeroes, and all the positions that have different values in a and b will become 1. For example:

101110 ^
011010
========
110100

So basically, the algorithm finds the number of 1-bits in a ^ b. To force it to output a certain value, just make a = 0 then b = number with d 1-bits.

To get a number with d 1-bits, consider b = (2 to the power of d) - 1.

So if you want d = 11, then a = 0 and b = (2 to the power of 11) - 1 = 2048 - 1 = 2047.

To efficiently compute 2 to a certain power programmatically, use this formula:

2 to the power of k == 1 << k

So, basically: encryption(a, b) == d if a = 0 and b = (1 << d) - 1.