Here's the following algorithm:
int encryption(int a, int b) {
short int c;
uint8_t d;
c = a ^ b;
d = 0;
while(c) {
c &= c - 1;
d++;
}
return d;
}
How can I find which values a and b I should send to that function to decide the output value of d?
In other words, how can I reverse the algorithm if, let's say, I wanted d == 11?
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.