Excerpted and modified as needed for Java language from the free & un copyrighted Wikipedia: http://en.wikipedia.org
A bit wise NOT or complement is a unary operation which performs logical negation on each bit. 0 digits become 1, and vice versa. For example:
NOT 0111 = 1000
In Java, the NOT operator is "~" (tilde). For example:
x = ~y;
assigns x the result of "NOT y". This is different from the C logical "not" operator, "!" (exclamation point),
which treats the entire numeral as a single Boolean value.
Bit wise NOT is useful in finding the one's complement of a binary number, and may be an intermediate step in finding the two's complement of the same number.
A bit wise OR takes two bit patterns of equal length, and produces another one of the same length by matching up corresponding bits (the first of each; the second of each; and so on) and performing the logical OR operation on each pair of corresponding bits. In each pair, the result is 1 if the first bit is 1 OR the second bit is 1. Otherwise, the result is zero. For example:
0101 OR 0011 = 0111
In Java the bit wise OR operator is "|" (vertical bar). For example:
x = y | z;
assigns x the result of "y OR z". This is different from the C and C++ logical
"or" operator, "||" (two vertical bars), which treats its operands as Boolean values,
and results in "true" or "false".
The bit wise OR may be used in situations where a set of bits are used as flags; the bits in a single binary numeral may each represent a distinct Boolean variable. Applying the bit wise OR operation to the numeral along with a bit pattern containing 1 in some positions will result in a new numeral with those bits set. For example:
0010
can be considered as a set of four flags. The first, second, and fourth flags are not set (0); the third flag is set (1). The first flag may be set by applying the bit wise OR to this value, along with another value in which only the first flag is set:
0010 OR 1000 = 1010
This technique may be employed by programmers who are working under restrictions of memory space; one bit pattern can represent the states of several independent variables at once.
A bit wise AND takes two binary representations of equal length and performs the logical AND on each pair of corresponding bits. In each pair, the result is 1 if the first bit is 1 AND the second bit is 1. Otherwise, the result is zero. For example:
0101
AND 0011
= 0001
In Java the bit wise AND operator is "&" (ampersand). For example:
x = y & z;
assigns x the result of "y AND z". This is different from the C and C++ logical "and"
operator, "&&", which takes two logical operands as input and produces a result of "true" or "false".
The bit wise AND may be used to perform a bit mask operation. This operation may be used
to isolate part of a string of bits, or to determine whether a particular bit is 1 or 0.
For example, given a bit pattern:
0101
To determine whether the third bit is 1, a bit wise AND is applied to it along with another bit pattern containing 1 in the third bit, and 0 in all other bits:
0101
AND 0010
= 0000
Since the result is zero, the third bit in the original pattern was 0. Using bit wise AND in this manner is called bit masking, by analogy to the use of masking tape to cover, or mask, portions that should not be altered, or are not of interest. The 0 values mask the bits that are not of concern, in this case.
The bit shift is sometimes considered a bit wise operation, since it operates on a set of bits. Unlike the above, the bit shift operates on the entire numeral, rather than on individual bits. In this operation, the digits are moved, or shifted, to the left or right. Registers in a computer processor have a fixed number of available bits for storing numerals, so some bits may be shifted past the "end" of the register; the different kinds of shift typically differ in what they do with the bits that are shifted past the end.
0111 LEFT-SHIFT = 1110 0111 RIGHT-SHIFT = 0011
In the first case, the leftmost 0 was shifted past the end of the register, and a new 0 was shifted into the rightmost position. Where possible you should avoid signed values as the left arg of RIGHT shift because when you RIGHT shift an unsigned value you are guaranteed to put a zero in the left most bit(s). If you RIGHT shift a signed value the sign bit will be replicated into the space on the left side vacted by the bits moving to the right. If you dont want the sign bit to be the replacement value for all the new bits on the left then use a triple right shift >>> and this will brin in all zeros on the left to replace the bits that were pushed to the right.
0111 LEFT-SHIFT-BY-TWO = 1100
In Java, the left and right shift operators are "<<" and ">>", respectively. The number of places to shift is given as an argument to the shift operators. For example:
x = y << 2;
assigns x the result of shifting y to the left by two digits, using the arithmetic shift.
A left arithmetic shift is equivalent to multiplying by two (provided the value does not overflow), while a right arithmetic shift is equivalent to dividing by two and rounding down.
A bit wise exclusive OR takes two bit patterns of equal length and performs the logical XOR operation on each pair of corresponding bits. The result in each position is 1 if the two bits are different, and 0 if they are the same. For example:
0101
XOR 0011
= 0110
In Java, the bit wise XOR operator is "^" (circumflex). For example:
x = y ^ z;
assigns x the result of "y XOR z".
Assembly language programmers sometimes use the XOR operation as a short-cut to set the value of a register to zero. On many architectures, the XOR operation requires fewer CPU clock cycles than the sequence of operations that may be required to load a zero value and save it to the register. Using a given value as input to both sides of the bit wise XOR operation always results in an output of zero; by XORing a register with itself, that register can be easily set to zero.
The bit wise XOR may also be used to toggle flags in a set of bits. Given a bit pattern:
0010
The first and third bits may be toggled simultaneously by a bit wise XOR with another bit pattern containing 1 in the first and third positions:
0010
XOR 1010
= 1000
This technique may be used to manipulate bit patterns representing sets of Boolean variables.
Standard swapping algorithms require the use of temporary storage. Here is one such algorithm to swap x and y:
Copy the value of y to temporary storage: temp ? y
Assign y to get the value of x: y ? x
Assign x to get the temporary storage value: x ? temp
Or, if given two variables x and y of type integer, an arithmetic algorithm to swap them is as follows:
x = x + y y = x - y x = x - y
The above algorithm breaks down on systems that trap integer overflow.
Also, when x and y are aliased to the same storage location the result is
to zero out that location. Using the XOR swap algorithm, however,
neither temporary storage nor overflow detection are needed. The algorithm is as follows:
x = x XOR y y = x XOR y x = x XOR y
(However, the problem still remains that if x and y use the same storage location, the values will be zeroed out.) The algorithm typically corresponds to three machine code instructions. For example, in IBM System/370 assembly code:
XOR R1, R2 XOR R2, R1 XOR R1, R2
where R1 and R2 are registers and the operation XOR leaves the result in the first argument. This algorithm is particularly attractive to assembler programmers due to its performance and efficiency. It eliminates the use of the intermediate register, which is a limited resource in machine language programming. It also eliminates two memory access cycles, which would be expensive compared to a register operation.
Explanation
For example, let's say we have two values X = 12 and Y = 10. In binary, we have
X = 1 1 0 0 Y = 1 0 1 0 Now, we XOR X and Y to get 0 1 1 0 and store in X. We now have X = 0 1 1 0 Y = 1 0 1 0 XOR X and Y again to get 1 1 0 0 - store in Y, and we now have X = 0 1 1 0 Y = 1 1 0 0 XOR X and Y again to get 1 0 1 0 - store in X, and we have X = 1 0 1 0 Y = 1 1 0 0 The values are swapped, and the algorithm has indeed worked in this instance.
In general, however, if we call the initial value of X = x and the initial value of Y = y, then performing the above steps, using ? for XOR for clarity, and remembering that a ? a = 0 and b ? 0 = b, yields:
X = x ? y, Y = y X = x ? y, Y = x ? y ? y = x X = x ? y ? x = y, Y = x
/* Java code to implement an xor swap: */
if (x != y)
{
*x ^= *y;
*y ^= *x;
*x ^= *y;
}