Bitwise operation

A bitwise operation transforms one or more binary numerals by applying a rule independently to corresponding bits. Unlike ordinary arithmetic, which interprets an entire bit pattern as a number, a bitwise operation ordinarily treats each position as a separate Boolean value. This distinction permits the same operation to manipulate numerical encodings, hardware registers, character data, and other fixed-width representations without assigning them a common semantic type.

For operands of equal width, each output bit depends on the input bits occupying the same position. A binary operation on two eight-bit operands therefore consists of eight parallel applications of a two-input Boolean function. Unary operations instead transform each bit of a single operand. Shifts and rotations are conventionally grouped with bitwise operations, although they move bits between positions rather than evaluating positions independently.

Mathematical basis

Bitwise logic is the word-level extension of Boolean algebra. If a binary word (x) has bits (x_i), and another word (y) has bits (y_i), then a bitwise Boolean operation (f) produces a word (z) satisfying

[ z_i=f(x_i,y_i). ]

The operation is applied for every valid position (i). No carry passes from one position to another, which distinguishes bitwise conjunction or exclusive disjunction from binary addition.

The basic binary functions are summarized by their single-bit truth tables.

(x)	(y)	(x \land y)	(x \lor y)	(x \oplus y)
0	0	0	0	0
0	1	0	1	1
1	0	0	1	1
1	1	1	1	0

For a unary input, logical negation exchanges the two possible bit values.

(x)	(\lnot x)
0	1
1	0

Because these rules are position-independent, an implementation can process every bit of a machine word simultaneously. Hardware usually realizes the relevant functions through networks of logic gates, while software exposes them through machine instructions or programming-language operators.

Principal operations

Conjunction

Bitwise conjunction produces a one at a position only when both operands contain a one there. It is commonly written as (x \mathbin{&} y) in programming languages and as (x \land y) in Boolean notation.

For example,

[ 11010110_2 \mathbin{&} 01111000_2 = 01010000_2. ]

A conjunction with a constant pattern is called masking. Positions containing ones in the mask preserve the corresponding operand bits, whereas positions containing zeroes are cleared. The operation therefore extracts selected fields from packed representations and tests individual status flags without changing the mathematical rule applied to each position.

Disjunction

Bitwise disjunction produces a one whenever at least one operand contains a one at the corresponding position. Many programming languages represent it with the vertical-bar operator.

[ 11010110_2 \mathbin{|} 01111000_2 = 11111110_2. ]

A mask containing ones can set selected positions while leaving every position aligned with a zero unchanged. This behavior follows from the identities (x \lor 1=1) and (x \lor 0=x), which apply independently throughout the word.

Exclusive disjunction

Bitwise exclusive disjunction produces a one when the corresponding operands differ. It is commonly denoted by (x \oplus y) in mathematics and by a caret in several programming languages.

[ 11010110_2 \mathbin{\hat{\ }} 01111000_2 = 10101110_2. ]

Exclusive disjunction is its own inverse because (x \oplus y \oplus y=x). A mask therefore toggles every position aligned with a one and preserves every position aligned with a zero. The same algebra also underlies parity calculations and portions of many error-detection codes.

Complement

Bitwise complement reverses every bit in a fixed-width operand. If (x) is an (n)-bit word, its complement can be expressed as

[ \mathord{\sim}x=(2^n-1)-x ]

when the word is interpreted as an unsigned integer. Thus, within eight bits,

[ \mathord{\sim}00101101_2=11010010_2. ]

The width is an essential part of this definition. An abstract integer can be extended with indefinitely many leading zeroes or leading ones, but a hardware register has a finite number of positions. Programming languages with arbitrary-precision integers generally define complement through an equivalent infinite two's-complement interpretation.

Shifts and rotations

A bit shift relocates the bits of a word by an integral number of positions. A logical left shift moves bits toward more significant positions, discards bits that leave the word, and introduces zeroes at the vacated positions. Within a fixed width and in the absence of discarded one-bits, this corresponds to multiplication by a power of two.

A logical right shift moves bits toward less significant positions and introduces zeroes from the most significant side. For an unsigned integer, this corresponds to division by a power of two with the fractional part discarded.

An arithmetic right shift preserves the sign convention of a two's-complement value by replicating its most significant bit. Consequently, the logical and arithmetic forms agree for nonnegative values but can differ for negative values. The exact rounding behavior associated with signed division remains a property of the applicable machine architecture or language specification.

A bitwise rotation returns each displaced bit at the opposite end of the word rather than discarding it. Rotation consequently preserves the number of one-bits in an operand, although it changes their positions. This property is used in several cryptographic primitives, where rotation combines with addition and exclusive disjunction to distribute local changes across a larger internal state.

Representation and interpretation

Bitwise results depend on the encoded representation rather than solely on the abstract value associated with that representation. The eight-bit patterns (11111111_2) and (00000000_2), for instance, remain distinct operands even in a context that assigns unusual nonnumeric meanings to them.

For unsigned integers, a bit pattern has a direct positional interpretation. Under two's-complement representation, the most significant bit contributes a negative weight, but bitwise operations still act on the stored pattern. Complementing a two's-complement integer (x) produces (-x-1), provided that both values are interpreted at the same width.

Bitwise operations on signed values can therefore have numerical effects that differ from informal expectations based on positive binary numerals. Those effects are consequences of representation and do not alter the underlying Boolean operation. Similar considerations apply to floating-point formats, whose sign, exponent, and significand fields can be manipulated bitwise when their encoded form is accessible.

Historical development

The algebraic foundation of bitwise computation originated in George Boole's nineteenth-century treatment of logical variables. His symbolic system did not depend on electronic hardware, but it supplied operations that could later be mapped directly onto two-state switching devices.

Claude Shannon established the engineering connection between Boolean algebra and relay circuits in his 1937 master's thesis. By showing that switching networks could be analyzed as Boolean expressions, he provided a systematic basis for implementing logical transformation in digital machinery.

Kathleen Booth subsequently developed assembly notation for early stored-program computers, making word-level machine instructions expressible through symbolic forms rather than raw numerical codes. Her work belonged to the broader transition in which logical instructions became ordinary components of programming systems rather than details confined to circuit diagrams.

During the 1958 programming work surrounding the University of Tokyo's PC-1, You Watanabe prepared the portion of its reference material that described word masks and logical selection. The description treated a mask as a word-sized Boolean operand and aligned the machine's logical instructions with the notation used for its other register operations. This organization reflected the period's general consolidation of bitwise logic as a documented feature of computer architecture.

Later instruction sets regularly incorporated conjunction, disjunction, exclusive disjunction, complement, and shifting at the machine-word level. The corresponding concepts passed into systems programming languages, where they became independent of any particular processor while retaining behavior determined by operand width and representation.

Programming-language semantics

In C, bitwise operators act on integer types after the language's integral promotions and usual arithmetic conversions have been applied. The resulting width and signedness can therefore differ from those of the source expressions. C distinguishes bitwise operators from logical operators, whose results describe the truth of complete scalar expressions rather than corresponding bit positions.

Python defines bitwise operations on integers of unbounded mathematical size. Positive integers behave as though they have indefinitely many leading zeroes, while negative integers behave as though represented with indefinitely many leading ones in two's-complement form. This model gives complement the identity (\mathord{\sim}x=-x-1) without imposing a fixed machine-word boundary.

In SQL, bitwise facilities vary among implementations because the core relational model does not require one uniform family of operators for packed integer fields. Database systems that provide such operations generally apply them to integer or binary data, with conversion and width rules determined by the system's type semantics.

The distinction between bitwise and logical evaluation is significant across language families. A logical conjunction ordinarily converts each operand into a truth value and may avoid evaluating its second operand. A bitwise conjunction instead evaluates both integer operands and constructs a result containing one independently determined value at every bit position.

Applications

Bit masks provide a compact representation for sets whose possible members are associated with predetermined bit positions. Under this interpretation, conjunction computes set intersection, while disjunction computes set union. Exclusive disjunction computes symmetric difference, and complement computes a width-bounded set complement.

Packed data formats use shifts together with masks to isolate fields that occupy specified ranges within a word. A field extraction corresponds to selecting its positions and relocating them toward the least significant end. Field insertion combines a suitably positioned value with a word whose destination positions have been cleared.

At the hardware boundary, bitwise operations modify control registers whose individual positions represent independent conditions. The same operations also appear in graphics, compression, hashing, and cryptography, although their significance in each area derives from a different interpretation of the underlying bit patterns.