In
computer programming
Computer programming is the process of performing a particular computation (or more generally, accomplishing a specific computing result), usually by designing and building an executable computer program. Programming involves tasks such as ana ...
, a bitwise operation operates on a
bit string
A bit array (also known as bitmask, bit map, bit set, bit string, or bit vector) is an array data structure that compactly stores bits. It can be used to implement a simple set data structure. A bit array is effective at exploiting bit-level pa ...
, a
bit array
A bit array (also known as bitmask, bit map, bit set, bit string, or bit vector) is an array data structure that compactly stores bits. It can be used to implement a simple set data structure. A bit array is effective at exploiting bit-level p ...
or a
binary numeral
A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method of mathematical expression which uses only two symbols: typically "0" (zero) and "1" ( one).
The base-2 numeral system is a positional notatio ...
(considered as a bit string) at the level of its individual
bit
The bit is the most basic unit of information in computing and digital communications. The name is a portmanteau of binary digit. The bit represents a logical state with one of two possible values. These values are most commonly represente ...
s. It is a fast and simple action, basic to the higher-level arithmetic operations and directly supported by the
processor
Processor may refer to:
Computing Hardware
* Processor (computing)
**Central processing unit (CPU), the hardware within a computer that executes a program
*** Microprocessor, a central processing unit contained on a single integrated circuit (I ...
. Most bitwise operations are presented as two-operand instructions where the result replaces one of the input operands.
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 pipeline
In computer engineering, instruction pipelining or ILP is a technique for implementing instruction-level parallelism within a single processor. Pipelining attempts to keep every part of the processor busy with some instruction by dividing inco ...
s and other
architectural
Architecture is the art and technique of designing and building, as distinguished from the skills associated with construction. It is both the process and the product of sketching, conceiving, planning, designing, and constructing buildings o ...
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
In mathematics, an unary operation is an operation with only one operand, i.e. a single input. This is in contrast to binary operations, which use two operands. An example is any function , where is a set. The function is a unary operation on ...
that performs
logical negation
In logic, negation, also called the logical complement, is an operation that takes a proposition P to another proposition "not P", written \neg P, \mathord P or \overline. It is interpreted intuitively as being true when P is false, and false ...
on each bit, forming the
ones' complement
The ones' complement of a binary number is the value obtained by inverting all the bits in the binary representation of the number (swapping 0s and 1s). The name "ones' complement" (''note this is possessive of the plural "ones", not of a sing ...
of the given binary value. Bits that are 0 become 1, and those that are 1 become 0. For example:
NOT 0111 (decimal 7)
= 1000 (decimal 8)
NOT 10101011 (decimal 171)
= 01010100 (decimal 84)
The result is equal to the
two's complement
Two's complement is a mathematical operation to reversibly convert a positive binary number into a negative binary number with equivalent (but negative) value, using the binary digit with the greatest place value (the leftmost bit in big- endian ...
of the value minus one. If two's complement arithmetic is used, then
NOT x = -x − 1
.
For unsigned
integers
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language o ...
, 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
![0](https://upload.wikimedia.org/wikipedia/commons/4/48/0...15_AND.svg)
A bitwise AND is a
binary operation
In mathematics, a binary operation or dyadic operation is a rule for combining two elements (called operands) to produce another element. More formally, a binary operation is an operation of arity two.
More specifically, an internal binary op ...
that takes two equal-length binary representations and performs the
logical AND
In logic, mathematics and linguistics, And (\wedge) is the truth-functional operator of logical conjunction; the ''and'' of a set of operands is true if and only if ''all'' of its operands are true. The logical connective that represents this ...
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:
0101 (decimal 5)
AND 0011 (decimal 3)
= 0001 (decimal 1)
The operation may be used to determine whether a particular bit is ''set'' (1) or ''clear'' (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:
0011 (decimal 3)
AND 0010 (decimal 2)
= 0010 (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
Masking tape, also known as painter's tape, is a type of pressure-sensitive tape made of a thin and easy-to-tear paper, and an easily released pressure-sensitive adhesive. It is available in a variety of widths. It is used mainly in painting, to ...
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
A flag is a piece of fabric (most often rectangular or quadrilateral) with a distinctive design and colours. It is used as a symbol, a signalling device, or for decoration. The term ''flag'' is also used to refer to the graphic design employ ...
) of a register in which each bit represents an individual
Boolean
Any kind of logic, function, expression, or theory based on the work of George Boole is considered Boolean.
Related to this, "Boolean" may refer to:
* Boolean data type, a form of data with only two possible values (usually "true" and "false" ...
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, 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:
0110 (decimal 6)
AND 1011 (decimal 11)
= 0010 (decimal 2)
Because of this property, it becomes easy to check the
parity
Parity may refer to:
* Parity (computing)
** Parity bit in computing, sets the parity of data for the purpose of error detection
** Parity flag in computing, indicates if the number of set bits is odd or even in the binary representation of the r ...
of a binary number by checking the value of the lowest valued bit. Using the example above:
0110 (decimal 6)
AND 0001 (decimal 1)
= 0000 (decimal 0)
Because 6 AND 1 is zero, 6 is divisible by two and therefore even.
OR
![0](https://upload.wikimedia.org/wikipedia/commons/b/ba/0...15_OR.svg)
A bitwise OR is a
binary operation
In mathematics, a binary operation or dyadic operation is a rule for combining two elements (called operands) to produce another element. More formally, a binary operation is an operation of arity two.
More specifically, an internal binary op ...
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:
0101 (decimal 5)
OR 0011 (decimal 3)
= 0111 (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:
0010 (decimal 2)
OR 1000 (decimal 8)
= 1010 (decimal 10)
XOR
![Z2^4; Cayley table; binary](https://upload.wikimedia.org/wikipedia/commons/d/d6/Z2%5E4%3B_Cayley_table%3B_binary.svg)
A bitwise XOR is a
binary operation
In mathematics, a binary operation or dyadic operation is a rule for combining two elements (called operands) to produce another element. More formally, a binary operation is an operation of arity two.
More specifically, an internal binary op ...
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:
0101 (decimal 5)
XOR 0011 (decimal 3)
= 0110 (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:
0010 (decimal 2)
XOR 1010 (decimal 10)
= 1000 (decimal 8)
This technique may be used to manipulate bit patterns representing sets of Boolean states.
Assembly language
In computer programming, assembly language (or assembler language, or symbolic machine code), often referred to simply as Assembly and commonly abbreviated as ASM or asm, is any low-level programming language with a very strong correspondence be ...
programmers and optimizing
compiler
In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs that ...
s sometimes use XOR as a short-cut to setting the value of a
register
Register or registration may refer to:
Arts entertainment, and media Music
* Register (music), the relative "height" or range of a note, melody, part, instrument, etc.
* ''Register'', a 2017 album by Travis Miller
* Registration (organ), the ...
to zero. Performing XOR on a value against itself always yields zero, and on many architectures this operation requires fewer clock cycles and 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
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called ''vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but can ...
over the
field
Field may refer to:
Expanses of open ground
* Field (agriculture), an area of land used for agricultural purposes
* Airfield, an aerodrome that lacks the infrastructure of an airport
* Battlefield
* Lawn, an area of mowed grass
* Meadow, a grass ...
, then vector addition corresponds to the bitwise XOR.
Mathematical equivalents
Assuming , for the non-negative integers, the bitwise operations can be written as follows:
:
Truth table for all binary logical operators
There are 16 possible
truth functions of two
binary variables
Binary data is data whose unit can take on only two possible states. These are often labelled as 0 and 1 in accordance with the binary numeral system and Boolean algebra.
Binary data occurs in many different technical and scientific fields, wher ...
; this defines a
truth table
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional argumen ...
.
Here is the bitwise equivalent operations of two bits P and Q:
Bit shifts
The bit shifts are sometimes considered bitwise operations, because they treat a value as a series of bits rather than as a numerical quantity. In these operations, the digits are moved, or ''shifted'', to the left or right.
Register
Register or registration may refer to:
Arts entertainment, and media Music
* Register (music), the relative "height" or range of a note, melody, part, instrument, etc.
* ''Register'', a 2017 album by Travis Miller
* Registration (organ), the ...
s in a computer processor have a fixed width, 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 determine the values of the shifted-in bits.
Bit addressing
If the width of the register (frequently 32 or even 64) is larger than the number of bits (usually 8) of the smallest addressable unit, frequently called byte, the shift operations induce an addressing scheme from the bytes to the bits.
Thereby the orientations "left" and "right" are taken from the standard writing of numbers in a
place-value notation
Positional notation (or place-value notation, or positional numeral system) usually denotes the extension to any base of the Hindu–Arabic numeral system (or decimal system). More generally, a positional system is a numeral system in which the ...
, such that a left shift increases and a right shift decreases the value of the number ― if the left digits are read first, this makes up a
big-endian
In computing, endianness, also known as byte sex, is the order or sequence of bytes of a word of digital data in computer memory. Endianness is primarily expressed as big-endian (BE) or little-endian (LE). A big-endian system stores the most sig ...
orientation.
Disregarding the boundary effects at both ends of the register, arithmetic and logical shift operations behave the same, and a shift by 8 bit positions transports the bit pattern by 1 byte position in the following way:
:
Arithmetic shift
![Rotate right arithmetically](https://upload.wikimedia.org/wikipedia/commons/3/37/Rotate_right_arithmetically.svg)
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
In computer science, the sign bit is a bit in a signed number representation that indicates the sign of a number. Although only signed numeric data types have a sign bit, it is invariably located in the most significant bit position, so the term ...
(the MSB in two's complement) is shifted in on the left, thus preserving the sign of the operand.
This example uses an 8-bit register, interpreted as two's complement:
00010111 (decimal +23) LEFT-SHIFT
= 00101110 (decimal +46)
10010111 (decimal −105) RIGHT-SHIFT
= 11001011 (decimal −53)
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
In computer processors the carry flag (usually indicated as the C flag) is a single bit in a system status register/flag register used to indicate when an arithmetic carry or borrow has been generated out of the most significant arithmetic logic ...
), and a new 1 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 (decimal +23) LEFT-SHIFT-BY-TWO
= 01011100 (decimal +92)
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
Two's complement is a mathematical operation to reversibly convert a positive binary number into a negative binary number with equivalent (but negative) value, using the binary digit with the greatest place value (the leftmost bit in big- endian ...
value is equivalent to taking the
floor
A floor is the bottom surface of a room or vehicle. Floors vary from simple dirt in a cave to many layered surfaces made with modern technology. Floors may be stone, wood, bamboo, metal or any other material that can support the expected load ...
of division by 2
''n''. If the binary number is treated as
ones' complement
The ones' complement of a binary number is the value obtained by inverting all the bits in the binary representation of the number (swapping 0s and 1s). The name "ones' complement" (''note this is possessive of the plural "ones", not of a sing ...
, then the same right-shift operation results in division by 2
''n'' and
rounding toward zero.
Logical shift
In a ''logical shift'', zeros are shifted in to replace the discarded bits. Therefore, the logical and arithmetic left-shifts are exactly the same.
However, as the logical right-shift inserts value 0 bits into the most significant bit, instead of copying the sign bit, it is ideal for unsigned binary numbers, while the arithmetic right-shift is ideal for signed
two's complement
Two's complement is a mathematical operation to reversibly convert a positive binary number into a negative binary number with equivalent (but negative) value, using the binary digit with the greatest place value (the leftmost bit in big- endian ...
binary numbers.
Circular shift
Another form of shift is the ''circular shift'', ''bitwise rotation'' or ''bit rotation''.
Rotate
In this operation, sometimes called ''rotate no carry'', the bits are "rotated" as if the left and right ends of the register were joined. The value that is shifted into the right during a left-shift is whatever value was shifted out on the left, and vice versa for a right-shift operation. This is useful if it is necessary to retain all the existing bits, and is frequently used in digital
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
.
Rotate through carry
''Rotate through carry'' is a variant of the rotate operation, where 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 low end
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
In computing, a word is the natural unit of data used by a particular processor design. A word is a fixed-sized datum handled as a unit by the instruction set or the hardware of the processor. The number of bits or digits in a word (the ''word si ...
, because if a large number is stored in two registers, the bit that is shifted off one 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.
In high-level languages
C-family and Python
In
C-family languages, the logical shift operators are "
<<
" for left shift and "
>>
" for right shift. The number of places to shift is given as the second argument to the operator. For example,
x = y << 2;
assigns
x
the result of shifting
y
to the left by two bits, which is equivalent to a multiplication by four.
Shifts can result in implementation-defined behavior or
undefined behavior
In computer programming, undefined behavior (UB) is the result of executing a program whose behavior is prescribed to be unpredictable, in the language specification to which the computer code adheres. This is different from unspecified behavior, ...
, so care must be taken when using them. The result of shifting by a bit count greater than or equal to the word's size is undefined behavior in C and C++.
Right-shifting a negative value is implementation-defined and not recommended by good coding practice; the result of left-shifting a signed value is undefined if the result cannot be represented in the result type.
[JTC1/SC22/WG14 N843 "C programming language"](_blank)
section 6.5.7
In C#, the right-shift is an arithmetic shift when the first operand is an int or long. If the first operand is of type uint or ulong, the right-shift is a logical shift.
=Circular shifts
=
The C-family of languages lack a rotate operator (although C++20 provides
std::rotl
and
std::rotr
), but one can be synthesized from the shift operators. Care must be taken to ensure the statement is well formed to avoid
undefined behavior
In computer programming, undefined behavior (UB) is the result of executing a program whose behavior is prescribed to be unpredictable, in the language specification to which the computer code adheres. This is different from unspecified behavior, ...
and
timing attack
In cryptography, a timing attack is a side-channel attack in which the attacker attempts to compromise a cryptosystem by analyzing the time taken to execute cryptographic algorithms. Every logical operation in a computer takes time to execute, and ...
s in software with security requirements.
For example, a naive implementation that left-rotates a 32-bit unsigned value
x
by
n
positions is simply
uint32_t x = ..., n = ...;
uint32_t y = (x << n) , (x >> (32 - n));
However, a shift by
0
bits results in undefined behavior in the right-hand expression
(x >> (32 - n))
because
32 - 0
is
32
, and
32
is outside the range 0–31 inclusive. A second try might result in
uint32_t x = ..., n = ...;
uint32_t y = n ? (x << n) , (x >> (32 - n)) : x;
where the shift amount is tested to ensure that it does not introduce undefined behavior. However, the branch adds an additional code path and presents an opportunity for timing analysis and attack, which is often not acceptable in high-integrity software.
In addition, the code compiles to multiple machine instructions, which is often less efficient than the processor's native instruction.
To avoid the undefined behavior and branches under
GCC and
Clang
Clang is a compiler front end for the C, C++, Objective-C, and Objective-C++ programming languages, as well as the OpenMP, OpenCL, RenderScript, CUDA, and HIP frameworks. It acts as a drop-in replacement for the GNU Compiler Collection (GCC), ...
, the following is recommended. The pattern is recognized by many compilers, and the compiler will emit a single rotate instruction:
uint32_t x = ..., n = ...;
uint32_t y = (x << n) , (x >> (-n & 31));
There are also compiler-specific
intrinsics implementing
circular shift
In combinatorial mathematics, a circular shift is the operation of rearranging the entries in a tuple, either by moving the final entry to the first position, while shifting all other entries to the next position, or by performing the inverse oper ...
s, lik
_rotl8, _rotl16_rotr8, _rotr16in Microsoft
Visual C++
Microsoft Visual C++ (MSVC) is a compiler for the C, C++ and C++/CX programming languages by Microsoft. MSVC is proprietary software; it was originally a standalone product but later became a part of Visual Studio and made available in both tria ...
. Clang provides some rotate intrinsics for Microsoft compatibility that suffers the problems above.
GCC does not offer rotate intrinsics. Intel also provides x8
intrinsics
Java
In
Java
Java (; id, Jawa, ; jv, ꦗꦮ; su, ) is one of the Greater Sunda Islands in Indonesia. It is bordered by the Indian Ocean to the south and the Java Sea to the north. With a population of 151.6 million people, Java is the world's List ...
, all integer types are signed, so 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 for signed integer, there is no "
<<<
" operator in Java.
More details of Java shift operators:
* The operators
<<
(left shift),
>>
(signed right shift), and
>>>
(unsigned right shift) are called the ''shift operators''.
* The type of the shift expression is the promoted type of the left-hand operand. For example,
aByte >>> 2
is equivalent to .
* If the promoted type of the left-hand operand is int, only the five lowest-order bits of the right-hand operand are used as the shift distance. It is as if the right-hand operand were subjected to a bitwise logical AND operator & with the mask value 0x1f (0b11111).
The shift distance actually used is therefore always in the range 0 to 31, inclusive.
* If the promoted type of the left-hand operand is long, then only the six lowest-order bits of the right-hand operand are used as the shift distance. It is as if the right-hand operand were subjected to a bitwise logical AND operator & with the mask value 0x3f (0b111111).
The shift distance actually used is therefore always in the range 0 to 63, inclusive.
* The value of is ''n'' right-shifted ''s'' bit positions with zero-extension.
* In bit and shift operations, the type
''byte''
is implicitly converted to
''int''
. If the byte value is negative, the highest bit is one, then ones are used to fill up the extra bytes in the int. So will result in .
JavaScript
JavaScript
JavaScript (), often abbreviated as JS, is a programming language that is one of the core technologies of the World Wide Web, alongside HTML and CSS. As of 2022, 98% of Website, websites use JavaScript on the Client (computing), client side ...
uses bitwise operations to evaluate each of two or more
units place
A numerical digit (often shortened to just digit) is a single symbol used alone (such as "2") or in combinations (such as "25"), to represent numbers in a positional numeral system. The name "digit" comes from the fact that the ten digits (Latin ...
to 1 or 0.
Pascal
In Pascal, as well as in all its dialects (such as
Object Pascal
Object Pascal is an extension to the programming language Pascal (programming language), Pascal that provides object-oriented programming (OOP) features such as Class (computer programming), classes and Method (computer programming), methods.
...
and
Standard Pascal), the logical left and right shift operators are "
shl
" and "
shr
", respectively. Even for signed integers,
shr
behaves like a logical shift, and does not copy the sign bit. The number of places to shift is given as the second argument. For example, the following assigns ''x'' the result of shifting ''y'' to the left by two bits:
x := y shl 2;
Other
*
popcount
The Hamming weight of a string is the number of symbols that are different from the zero-symbol of the alphabet used. It is thus equivalent to the Hamming distance from the all-zero string of the same length. For the most typical case, a string of ...
, used in cryptography
*
count leading zeros
In computer software and hardware, find first set (ffs) or find first one is a bit operation that, given an unsigned machine word, designates the index or position of the least significant bit set to one in the word counting from the least signifi ...
Applications
Bitwise operations are necessary particularly in lower-level programming such as 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, all these operations can be performed by combining the bitwise operators and zero-testing in various ways. For example, here is a
pseudocode
In computer science, pseudocode is a plain language description of the steps in an algorithm or another system. Pseudocode often uses structural conventions of a normal programming language, but is intended for human reading rather than machine re ...
implementation of
ancient Egyptian multiplication
In mathematics, ancient Egyptian multiplication (also known as Egyptian multiplication, Ethiopian multiplication, Russian multiplication, or peasant multiplication), one of two multiplication methods used by scribes, is a systematic method for mul ...
showing how to multiply two arbitrary integers
a
and
b
(
a
greater than
b
) using only bitshifts and addition:
c ← 0
while b ≠ 0
if (b and 1) ≠ 0
c ← c + a
left shift a by 1
right shift b by 1
return c
Another example is a pseudocode implementation of addition, showing how to calculate a sum of two integers
a
and
b
using bitwise operators and zero-testing:
while a ≠ 0
c ← b and a
b ← b xor a
left shift c by 1
a ← c
return b
Boolean algebra
Sometimes it is useful to simplify complex expressions made up of bitwise operations, for example when writing compilers. The goal of a compiler is to translate a
high level programming language
In computer science, a high-level programming language is a programming language with strong abstraction from the details of the computer. In contrast to low-level programming languages, it may use natural language ''elements'', be easier to use, ...
into the most efficient
machine code
In computer programming, machine code is any low-level programming language, consisting of machine language instructions, which are used to control a computer's central processing unit (CPU). Each instruction causes the CPU to perform a very ...
possible. Boolean algebra is used to simplify complex bitwise expressions.
AND
*
x & y = y & x
*
x & (y & z) = (x & y) & z
*
x & 0xFFFF = x
[Throughout this article, 0xFFFF means that all the bits in your data type need to be set to 1. The exact number of bits depends on the width of the data type.]
*
x & 0 = 0
*
x & x = x
OR
*
x , y = y , x
*
x , (y , z) = (x , y) , z
*
x , 0 = x
*
x , 0xFFFF = 0xFFFF
*
x , x = x
NOT
*
~(~x) = x
XOR
*
x ^ y = y ^ x
*
x ^ (y ^ z) = (x ^ y) ^ z
*
x ^ 0 = x
*
x ^ y ^ y = x
*
x ^ x = 0
*
x ^ 0xFFFF = ~x
Additionally, XOR can be composed using the 3 basic operations (AND, OR, NOT)
*
a ^ b = (a , b) & (~a , ~b)
*
a ^ b = (a & ~b) , (~a & b)
Others
*
x , (x & y) = x
*
x & (x , y) = x
*
~(x , y) = ~x & ~y
*
~(x & y) = ~x , ~y
*
x , (y & z) = (x , y) & (x , z)
*
x & (y , z) = (x & y) , (x & z)
*
x & (y ^ z) = (x & y) ^ (x & z)
*
x + y = (x ^ y) + ((x & y) << 1)
*
x - y = ~(~x + y)
Inverses and solving equations
It can be hard to solve for variables in boolean algebra, because unlike regular algebra, several operations do not have inverses. Operations without inverses lose some of the original data bits when they are performed, and it is not possible to recover this missing information.
* Has inverse
** NOT
** XOR
** Rotate left
** Rotate right
* No inverse
** AND
** OR
** Shift left
** Shift right
Order of operations
Operations at the top of this list are executed first. See the main article for a more complete list.
*
( )
*
~ -
*
* / %
*
+ -
[- is subtraction here, not negation]
*
<< >>
*
&
*
^
*
,
See also
*
Arithmetic logic unit
In computing, an arithmetic logic unit (ALU) is a Combinational logic, combinational digital circuit that performs arithmetic and bitwise operations on integer binary numbers. This is in contrast to a floating-point unit (FPU), which operates on ...
*
Bit manipulation
Bit manipulation is the act of algorithmically manipulating bits or other pieces of data shorter than a word. Computer programming tasks that require bit manipulation include low-level device control, error detection and correction algorithms, ...
*
Bitboard
A bitboard is a specialized bit array data structure commonly used in computer systems that play board games, where each bit corresponds to a game board space or piece. This allows parallel bitwise operations to set or query the game state, or de ...
*
Bitwise operations in C
*
Boolean algebra (logic)
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variable (mathematics), variables are the truth values ''true'' and ''false'', usually denote ...
*
Double dabble
In computer science, the double dabble algorithm is used to convert binary numbers into binary-coded decimal (BCD) notation. It is also known as the shift-and-add-3 algorithm, and can be implemented using a small number of gates in computer hardwa ...
*
Find first set
In computer software and hardware, find first set (ffs) or find first one is a bit operation that, given an unsigned machine word, designates the index or position of the least significant bit set to one in the word counting from the least signific ...
*
Karnaugh map
The Karnaugh map (KM or K-map) is a method of simplifying Boolean algebra expressions. Maurice Karnaugh introduced it in 1953 as a refinement of Edward W. Veitch's 1952 Veitch chart, which was a rediscovery of Allan Marquand's 1881 ''logica ...
*
Logic gate
A logic gate is an idealized or physical device implementing a Boolean function, a logical operation performed on one or more binary inputs that produces a single binary output. Depending on the context, the term may refer to an ideal logic gate, ...
*
Logical operator
In logic, a logical connective (also called a logical operator, sentential connective, or sentential operator) is a logical constant. They can be used to connect logical formulas. For instance in the syntax of propositional logic, the binary co ...
*
Primitive data type
In computer science, primitive data types are a set of basic data types from which all other data types are constructed. Specifically it often refers to the limited set of data representations in use by a particular processor, which all compiled pr ...
References
External links
Online Bitwise Calculatorsupports Bitwise AND, OR and XOR
XORcat a tool for bitwise-XOR files/streams
*
Bitwise Operations Mod N by Enrique Zeleny,
Wolfram Demonstrations Project
The Wolfram Demonstrations Project is an organized, open-source collection of small (or medium-size) interactive programs called Demonstrations, which are meant to visually and interactively represent ideas from a range of fields. It is hos ...
.
*
Plots Of Compositions Of Bitwise Operations by Enrique Zeleny, The Wolfram Demonstrations Project.
{{DEFAULTSORT:Bitwise Operation
Binary arithmetic
Operators (programming)
Articles with example pseudocode
Boolean algebra