C++ bitwise operation reverse

Question

I got the following operation:

uint8_t input = 10;
uint8_t output = ((0x190 - (input * 8)) & 0xFF);

// newInput should be 10 again, but is 255
uint8_t newInput = (((output * 8) + 0x190) | 0xFF);

How can I correct the operation setting newInput so that it will result back in 10?

`| (0 & 0x07)` does nothing! tried it and got 200 for 25. and what's the type of `my_value` ? — Jean-François Fabre, Dec 03 '16 at 22:06
@Alex parenthesis are not even balanced, did you copy it correctly? — FranMowinckel, Dec 03 '16 at 22:21
Multiplication by even numbers (so also 8) is not invertable — harold, Dec 04 '16 at 15:19
Wait, you are ORing a byte wide number with 0xFF and getting surprised that the result is 0xFF? AND and OR are different, but not the 'reverse' of each other — infixed, Dec 05 '16 at 13:56
But put a NOT operation in there, then then you get a reverse like in ` | ~0xff` But that's just ORing with zero, and doing nothing. (odd, code markup is not working here) — infixed, Dec 05 '16 at 14:03

The Vee · Accepted Answer · 2016-12-05T14:40:52.693

You want to invert the transformation that got you output from input but unfortunately the logic is flawed. | is not an inverse of & and * 8 is absolutely not inverse to another * 8. Also, if you want to reverse the action of y = 0x190 - x, it's not a + but rather another x = 0x190 - y (try it on paper!) Finally, if you had all the operations all right, the order of the operations would need to be reversed in order to undo them (first in, last out).

In fact, your transformation can not be inverted, because it loses part of the information that defines input. (Mathematically speaking, it is not injective.) Consider:

uint8_t input = 10;
uint8_t output = ((0x190 - (input * 8)) & 0xFF); /* 0x40 */

uint8_t input2 = 42;
uint8_t output2 = ((0x190 - (input2 * 8)) & 0xFF); /* also 0x40! */

If you had a function that would undo the operation, what would it be expected to return for an output of 0x40, 10 or 42? This has no solution. If you want the original input you'll need to keep a copy of that variable somewhere.

Examples of operations that can be undone in unsigned 8-bit calculations are

addition and subtraction OF a constant: y = x + a ⇔ x = y - a,
subtraction FROM a constant: y = c - x ⇔ x = c - y, including plain negation (c = 0),
XOR: y = x ^ p ⇔ x = y ^ p, including ~x (that's x ^ 0xFF),
multiplication by a constant in some cases (by odd numbers), but the inverse is not obvious.

An inverse operation to a compound like y = -((x + 0x17) ^ 0x15) would look like x = ((-y) ^ 0x15) - 0x17, notice the reverse order in which the steps are undone.

On the other hand, these are not invertible:

AND,
OR,
multiplication by an even number,
bit shifts,
etc.

Sometimes you can find an inverse if that's workable for you. Here, if you are guaranteed that input is between 0 and 18 (that is 0x90 / 8), you can try

uint8_t input = 10;
uint8_t output = 0x90 - (input * 8); // spot two differences
uint8_t newInput = (0x90 - output) / 8;

But if input is larger, for example 20, it will instead give some other value that happens to produce the same output.

Also, even assuming you had a sequence of injective operations, you would in general need to apply the reverse operations in the reverse order to get back to the original value — Caleth, Dec 05 '16 at 14:13
e.g. ( ( ( output | ( magic & 0xFF00 ) ) + 0x190 ) / 8 ), for some value of magic — Caleth, Dec 05 '16 at 14:14
@Caleth I added such sentence at some point in the first paragraph but maybe you were displayed the previous edit. — The Vee, Dec 05 '16 at 14:19
Indeed you did! Do you agree with my example nearly-inverse? — Caleth, Dec 05 '16 at 14:23
@Caleth Not really, `0x190 - x` is self-inverse. So even the honest attempt at the `+` was a mistake actually :-) I should also mention that. — The Vee, Dec 05 '16 at 14:25

izlin · Answer 2 · 2016-12-05T14:24:04.547

There are several problems why your code won't work, let me explain some of them:

You have an unsigned 8 bit integer, so you can use values between 0x00 and 0xFF. 0x190 - (10 *8) = 0x190 - 0x50 = 0x140 can be done but afterwards you cut of the leading 1 with the &FF, so you lose information that can't be restored afterwards.
The | FF is a bitwise OR, which turns every bit of your calculation to 1, so you will always get 0xFF = 255 , regardless of your output.
Your calculation is wrong.
It is dangerous to use decimal numbers (10) and hexadecimal numbers (0x190) in one calculation. It can be confusing.

I recommend to ensure that you won't overflow you variables. Use other constants so you will stay in the range of unit8_t or use another Type like int16_t which wont overflow with those little numbers. Be aware of your bitwise operators. Like I said the last OR will always make newInput=255.

Here is an example which will work for the given parameters:

int16_t input = 10; // int16_t wont overflow
int16_t output = ((0x190 - (input * 8)) ); // without &FF there is no
                                            // loss of information

int16_t newInput = (0x190- output) / 8; // Reshape of the line obove

score 1 · Answer 3 · edited May 23 '17 at 10:30

Several points here:

You appear to be trying to use & 0xFF to truncate to 8-bits, you should get rid of that since the standard already guarantees this will happen for unsigned integers: https://stackoverflow.com/a/36234166/2642059
You should be doing (0x190 - output) / 8U to recover input, so even if the sizes permitted your math is wrong:

o = 400 - 8x
o - 400 = -8x
(o - 400) / -8 = x

400 in binary is 0b1'1001'0000 so since the downcast is truncating the most significant bit it may and may not be set, thus you will always have 2 potential answers (where output is positive):

const uint8_t newInputSmall = (0x190 - (output | 0b1'0000'0000)) / 8U;
cosnt uint8_t newInputLarge = (0x190 - output) / 8U;

You'll need to handle the possibility that output is negative because input * 8U is larger than 400

C++ bitwise operation reverse

3 Answers3