Bitwise operation

In computer programming, a bitwise operation operates on one or two bit patterns or binary numerals at the level of their individual bits. On most microprocessors, bitwise operations are sometimes slightly faster than addition and subtraction operations and usually significantly faster than multiplication and division operations.

Bitwise operators

NOT

The bitwise NOT, or complement, is a unary operation which performs logical negation on each bit, forming the ones' complement of the given binary value. Digits which were 0 become 1, and vice versa. For example:

NOT 0111 = 1000

In many programming languages (including those in the C family), the bitwise NOT operator is "~" (tilde). This operator must not be confused with the "logical not" operator, "!" (exclamation point), which treats the entire value as a single Boolean — changing a true value to false, and vice versa. The "logical not" is not a bitwise operation.

OR

A bitwise 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 inclusive 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 (or both), and otherwise the result is 0. For example:

"' 0101 OR 0011 = 0111 "

In the C programming language family, the bitwise OR operator is "|" (pipe). Again, this operator must not be confused with its Boolean "logical or" counterpart, which treats its operands as Boolean values, and is written "||" (two pipes).

The bitwise 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 bitwise 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 bitwise OR to this value, along with another value in which only the first flag is set:

0010 OR 1000 = 1010

This technique is often used to conserve memory in programs dealing with large numbers of Boolean values.

XOR

A bitwise 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 the C programming language family, the bitwise XOR operator is "^" (caret).

Assembly language programmers sometimes use the XOR operation as a short-cut to set the value of a register to zero. Performing XOR on a value against itself always yields zero, and on many architectures, this 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.

The bitwise XOR may also be used to toggle flags in a set of bits. Given a bit patterns:

0010

The first and third bits may be toggled simultaneously by a bitwise 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.

ee also

*Xor swap algorithm
*Xor linked list

AND

A bitwise AND takes two binary representations of equal length and performs the logical AND operation 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 0. For example:

0101 AND 0011 = 0001

In the C programming language family, the bitwise AND operator is "&" (ampersand). Again, this operator must not be confused with its Boolean "logical and" counterpart, which treats its operands as Boolean values, and is written "&&" (two ampersands).

The bitwise 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:

0011

To determine whether the third bit is 1, a bitwise AND is applied to it and another bit pattern containing 1 in the third bit:

0011 AND 0010 = 0010

Since the result is 0010 (non-zero), the third bit in the original pattern was 1. Using bitwise 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. In this case, the 0 values mask the bits that are not of interest.

The bitwise AND can also be combined with the bitwise NOT to "clear" bits. For example:

0110

The second bit may be "cleared" (i.e. set to 0) by applying the bitwise AND to this value, along with the complement (i.e. NOT) of another value in which only the second bit is set:

NOT 0100 = 1011 0110 AND 1011 = 0010

Bit shifts

The bit shifts are sometimes considered bitwise operations, since they operate on the binary representation of an integer instead of its numerical value; however, the bit shifts do not operate on pairs of corresponding bits, and therefore cannot properly be called "bit-wise" operations. 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 will be "shifted out" of the register at one end, while the same number of bits are "shifted in" from the other end; the differences between bit shift operators lie in how they compute the values of those shifted-in bits.

Arithmetic shift

In an "arithmetic shift", the bits that are shifted out of either end are discarded. In a left arithmetic shift, zeros are shifted in on the right; in a right arithmetic shift, the sign bit is shifted in on the left, thus preserving the sign of the operand. This example uses an 8-bit register:

00010111 LEFT-SHIFT = 00101110

00010111 RIGHT-SHIFT = 00001011

In the first case, the leftmost digit was shifted past the end of the register, and a new 0 was shifted into the rightmost position. In the second case, the rightmost 1 was shifted out (perhaps into the carry flag), and a new 0 was copied into the leftmost position, preserving the sign of the number. Multiple shifts are sometimes shortened to a single shift by some number of digits. For example:

00010111 LEFT-SHIFT-BY-TWO = 01011100

A left arithmetic shift by "n" is equivalent to multiplying by 2^"n" (provided the value does not overflow), while a right arithmetic shift by "n" of a two's complement value is equivalent to dividing by 2^"n" and rounding toward negative infinity. If the binary number is treated as ones' complement, then the same right-shift operation results in division by 2^"n" and rounding toward zero.

Logical shift

"Rotate through carry" is similar to the "rotate no carry" operation, but the two ends of the register are considered to be separated by the carry flag. The bit that is shifted in (on either end) is the old value of the carry flag, and the bit that is shifted out (on the other end) becomes the new value of the carry flag.

A single "rotate through carry" can simulate a logical or arithmetic shift of one position by setting up the carry flag beforehand. For example, if the carry flag contains 0, then x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE is a logical right-shift, and if the carry flag contains a copy of the sign bit, then x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE is an arithmetic right-shift. For this reason, some microcontrollers such as PICs just have "rotate" and "rotate through carry", and don't bother with arithmetic or logical shift instructions.

Rotate through carry is especially useful when performing shifts on numbers larger than the processor's native word size, because if a large number is stored in two registers, the bit that is shifted off the end of the first register must come in at the other end of the second. With rotate-through-carry, that bit is "saved" in the carry flag during the first shift, ready to shift in during the second shift without any extra preparation.

hifts in C, C++ and Java

In C-inspired languages, the left and right shift operators are "<<" and ">>", respectively. The number of places to shift is given as the second argument to the shift operators. For example,

x = y << 2;

assigns "x" the result of shifting "y" to the left by two digits.

In C and C++, computations with the left operand as an unsigned integer use logical shifts. In C, the results with the left operand as a signed integer are [ [http://std.dkuug.dk/JTC1/SC22/WG14/www/docs/n843.htm JTC1/SC22/WG14 N843 "C programming language"] , section 6.5.7#5] :
*for "<<": left×2^right (undefined if an overflow occurs);
*for ">>": implementation-defined (most often the result of the arithmetic shift: left/2^right).

In Java, all integer types are signed, and the "<<" and ">>" operators perform arithmetic shifts. Java adds the operator ">>>" to perform logical right shifts, but since the logical and arithmetic left-shift operations are identical, there is no "<<<" operator in Java. These general rules are affected in several ways by the default type promotions; for example, since the eight-bit type byte is promoted to int in shift-expressions, ["The Java Language Specification, Second Edition", sections [http://java.sun.com/docs/books/jls/second_edition/html/expressions.doc.html#5121 15.19] (shift operators) and [http://java.sun.com/docs/books/jls/second_edition/html/conversions.doc.html#170952 5.6.1] (unary numeric promotion)] the expression "b >>> 2" effectively performs an arithmetic shift of the byte value b instead of a logical shift. Such effects can be mitigated by judicious use of casts or bitmasks; for example, "(b & 0xFF) >>> 2" effectively results in a logical shift.

Applications

Bitwise operations are necessary for much low-level programming, such as writing device drivers, low-level graphics, communications protocol packet assembly and decoding.

Although machines often have efficient built-in instructions for performing arithmetic and logical operations, in fact all these operations can be performed just by combining the bitwise operators and zero-testing in various ways.

For example, here is a pseudocode example showing how to multiply two arbitrary integers a and b using only bitshifts and addition:

c := 0 while b ≠ 0 if (b and 1) ≠ 0 c := c + a shift a left by one shift b right by one return c

This implementation of ancient Egyptian multiplication, like most multiplication algorithms, involves bitshifts.

ee also

*Bit manipulation
*Bitboard
*Boolean algebra (logic)
*Double dabble
*Logic gate
*Logical operator
*Karnaugh map

References

External links

* [http://www.cs.uiowa.edu/~jones/bcd/divide.html Division using bitshifts]
* " [http://demonstrations.wolfram.com/BitwiseOperationsModN/ Bitwise Operations Mod N] " by Enrique Zeleny, The Wolfram Demonstrations Project.
* " [http://demonstrations.wolfram.com/PlotsOfCompositionsOfBitwiseOperations/ Plots Of Compositions Of Bitwise Operations] " by Enrique Zeleny, The Wolfram Demonstrations Project.