Lably
Skip to content

Bitwise operation

Computer operation which manipulates invidual bits of data

  • 18 min read
  • 5 chapters
  • 2 labs on Lably

Learn it on Lably

Lab · Class 11Binary and Logic GatesLab · Class 9–11Python Sandbox

On simple low-cost processors, typically, bitwise operations are substantially faster than division, several times faster than multiplication, and sometimes significantly faster than addition. While modern processors usually perform addition and multiplication just as fast as bitwise operations due to their longer instruction pipelines and other architectural design choices, bitwise operations do commonly use less power because of the reduced use of resources.

Bitwise operators

In the explanations below, any indication of a bit's position is counted from the right (least significant) side, advancing left. For example, the binary value 0001 (decimal 1) has zeroes at every position but the first (i.e., the rightmost) one.

NOT

The bitwise NOT, or bitwise complement, is a unary operation that performs logical negation on each bit, forming the ones' complement of the given binary value. Bits that are 0 become 1, and those that are 1 become 0. For example:

NOT <b id="mwIg">0</b>111 (decimal 7) = <b id="mwIw">1</b>000 (decimal 8)
NOT 10101011 (decimal 171) = 01010100 (decimal 84)

The result is equal to the two's complement of the value minus one. If two's complement arithmetic is used, then NOT x = -x − 1.

For unsigned integers, the bitwise complement of a number is the "mirror reflection" of the number across the half-way point of the unsigned integer's range. For example, for 8-bit unsigned integers, NOT x = 255 - x, which can be visualized on a graph as a downward line that effectively "flips" an increasing range from 0 to 255, to a decreasing range from 255 to 0. A simple but illustrative example use is to invert a grayscale image where each pixel is stored as an unsigned integer.

AND

A bitwise AND is a binary operation that takes two equal-length binary representations and performs the logical AND operation on each pair of the corresponding bits. Thus, if both bits in the compared position are 1, the bit in the resulting binary representation is 1 (1 × 1 = 1); otherwise, the result is 0 (1 × 0 = 0 and 0 × 0 = 0). For example:

010<b id="mwPQ">1</b> (decimal 5) AND 001<b id="mwPg">1</b> (decimal 3) = 000<b id="mwPw">1</b> (decimal 1)

The operation may be used to determine whether a particular bit is set (1) or cleared (0). For example, given a bit pattern 0011 (decimal 3), to determine whether the second bit is set we use a bitwise AND with a bit pattern containing 1 only in the second bit:

00<b id="mwRA">1</b>1 (decimal 3) AND 00<b id="mwRQ">1</b>0 (decimal 2) = 00<b id="mwRg">1</b>0 (decimal 2)

Because the result 0010 is non-zero, we know the second bit in the original pattern was set. This is often called bit masking. (By analogy, the use of masking tape covers, or masks, portions that should not be altered or portions that are not of interest. In this case, the 0 values mask the bits that are not of interest.)

The bitwise AND may be used to clear selected bits (or flags) of a register in which each bit represents an individual Boolean state. This technique is an efficient way to store a number of Boolean values using as little memory as possible.

For example, 0110 (decimal 6) can be considered a set of four flags numbered from right to left, where the first and fourth flags are clear (0), and the second and third flags are set (1). The third flag may be cleared by using a bitwise AND with the pattern that has a zero only in the third bit:

0<b id="mwUQ">1</b>10 (decimal 6) AND 1<b id="mwUg">0</b>11 (decimal 11) = 0<b id="mwUw">0</b>10 (decimal 2)

Because of this property, it becomes easy to determine the even/odd status of a binary number by checking the value of the lowest valued bit. Using the example above:

011<b id="mwVg">0</b> (decimal 6) AND 000<b id="mwVw">1</b> (decimal 1) = 000<b id="mwWA">0</b> (decimal 0)

Because 6 AND 1 is zero, 6 is divisible by two and therefore even.

OR

A bitwise OR is a binary operation that takes two bit patterns of equal length and performs the logical inclusive OR operation on each pair of corresponding bits. The result in each position is 0 if both bits are 0, while otherwise the result is 1. For example:

0<b id="mwZA">101</b> (decimal 5) OR 0<b id="mwZQ">011</b> (decimal 3) = 0<b id="mwZg">111</b> (decimal 7)

The bitwise OR may be used to set to 1 the selected bits of the register described above. For example, the fourth bit of 0010 (decimal 2) may be set by performing a bitwise OR with the pattern with only the fourth bit set:

<b id="mwaQ">0</b>0<b id="mwag">1</b>0 (decimal 2) OR <b id="mwaw">1</b>0<b id="mwbA">0</b>0 (decimal 8) = <b id="mwbQ">1</b>0<b id="mwbg">1</b>0 (decimal 10)

XOR

A bitwise XOR is a binary operation that takes two bit patterns of equal length and performs the logical exclusive OR operation on each pair of corresponding bits. The result in each position is 1 if only one of the bits is 1, but will be 0 if both are 0 or both are 1. In this we perform the comparison of two bits, being 1 if the two bits are different, and 0 if they are the same. For example:

0<b id="mweQ">10</b>1 (decimal 5) XOR 0<b id="mweg">01</b>1 (decimal 3) = 0<b id="mwew">11</b>0 (decimal 6)

The bitwise XOR may be used to invert selected bits in a register (also called toggle or flip). Any bit may be toggled by XORing it with 1. For example, given the bit pattern 0010 (decimal 2) the second and fourth bits may be toggled by a bitwise XOR with a bit pattern containing 1 in the second and fourth positions:

<b id="mwfg">0</b>0<b id="mwfw">1</b>0 (decimal 2) XOR <b id="mwgA">1</b>0<b id="mwgQ">1</b>0 (decimal 10) = <b id="mwgg">1</b>0<b id="mwgw">0</b>0 (decimal 8)

This technique may be used to manipulate bit patterns representing sets of Boolean states.

Assembly language programmers and optimizing compilers sometimes use XOR as a short-cut to setting 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 clock cycles and less memory than loading a zero value and saving it to the register.

If the set of bit strings of fixed length n (i.e. machine words) is thought of as an n-dimensional vector space F2n over the field F2, then vector addition corresponds to the bitwise XOR.

Mathematical equivalents

Assuming ⁠x≥y⁠, for non-negative integers, the bitwise operations can be written as follows:

NOT⁡(x)=∑n=0⌊log2⁡x⌋2n((⌊x2n⌋mod2+1)mod2)=(2⌊log2⁡x⌋+1−1)−xxAND⁡y=∑n=0⌊log2⁡x⌋2n(⌊x2n⌋mod2)(⌊y2n⌋mod2)xOR⁡y=∑n=0⌊log2⁡x⌋2n(⌊x2n⌋mod2+⌊y2n⌋mod2−(⌊x2n⌋mod2)(⌊y2n⌋mod2))xXOR⁡y=∑n=0⌊log2⁡x⌋2n((⌊x2n⌋+⌊y2n⌋)mod2)

Truth table for all binary logical operators

There are 16 possible truth functions of two binary variables; this defines a truth table, termed a LUT2 lookup table, a.k.a. a Boolean function order k=2 (2 inputs). Some vendors use the term connective for instructions with a 4-bit field identifying the specific binary connective; some vendors use the term Boolean operation for 16 distinct opcodes.

Here are the bitwise equivalent operations of two bits P and Q:

The ternary equivalent is a LUT3 boolean function of order k=3 (three inputs), resulting in a table of 256 operations, and in computing is termed a Bitwise ternary logic instruction.

Sign in to keep reading

4 more chapters are free with a Lably account.

More in Computing and communication

ISBNUnique numeric book identifier since 1970X (social network)American social networking serviceWayback MachineDigital archive by the Internet ArchivePython (programming language)General-purpose programming languageMacOSOperating system for Apple computersUnicodeCharacter encoding standard