When input quantities contain uncertainty, how those uncertainties are propagated to the output for operations of addition, subtraction, multiplication and division can be found in literature defined using various rules.

However for bitwise operations such as shift left, arithmetic shift right, logical shift right, bitwise and, bitwise or, bitwise xor, such rules are not readily provided.

How does uncertainty propagation happen in the case of bitwise operators? Are there any literature relating to the uncertainty propagation of bitwise operations?

  • $\begingroup$ Can you specify whether the errors you have in mind are of the type "this value is $x \pm \varepsilon$", or of the type "each bit of this message is correct with probability $p$"? For the former type, I think things can be arbitrarily bad (imagine rotating bits to the right when our error term is larger than the least significant bit). $\endgroup$ – Eric Tressler Jul 17 '17 at 3:28
  • $\begingroup$ The values and errors I'm looking at, are of the type x ± ε. $\endgroup$ – Himeshi Jul 17 '17 at 3:58
  • $\begingroup$ The shift operations are equivalent to one or two arithmetic operations. For example logical right shift is conversion from signed to unsigned, followed by division by 2 (assuming $x$ is an integer, vs floating point, BCD, etc.) Arithmetic right shift is division by two with rounding towards negative infinity (versus division w rounding towards 0). $\endgroup$ – Χpẘ Jul 20 '17 at 16:17
  • $\begingroup$ @Himeshi any comment about my answer? $\endgroup$ – trying Jul 23 '17 at 15:51

As you correctly state at the begining of your question "When input quantities contain uncertanty [...]". Now, do you think that operands of bitwise operators are quantities, or rather simple strings of bits?

Of course, you can say that a quantity being a number can always be given its binary positional representation. But a generic string of bit is not qualifiable as being a number.

If you want anyway to treat it as a number, are you going to interpret it as a binary positional representation of a number? (Note that this is not immediate, you can also choose other criteria, like interpreting it as a decimal positional represenation of a number or as one among the multitude of binary codes: two's complement, BCD, ...).

Are you going to perform arithmetic operations on the same variables that are output by or that will be input in bitwise operations in the course of your algorithms? I think no. And as such you could not even ask whether a variable of this kind is more or less near to a true value, because does not make sense performe subtraction on it.

Wanting to go on anyway trying to treat operands as numbers (but I repeat, going on is a non sense) you see soon that it is even not possible.

For instance the bitwise NOT operator applied to the bit string $10$ that we need to treat as a number as it were $(10)_2$ (having arbitrarily chosen the criterion whereby the bit string is the binary positional representation of the number) that is $(2)_{10}$ gives the string bit $01$ that must be treated as a number $(01)_2$ that is $(1)_{10}$. But the same operator applied on the bit string $010$ that again must be treated as a number, that is $(10)_2$ = $(2)_{10}$ gives the bit string $101$ that treated as a number is $(101)_2 = (5)_{10}$. That is,

$$f_{NOT}(2)=1$$ $$f_{NOT}(2)=5$$

So bitwise operators are not functions on reals.

What do you think if we stop proceeding any further with this analysis?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.