In digital computer programming, a bitwise operation operates on one or more bit patterns or binary numerals at the level of their individual bits. It is a fast and simple action, directly supported by the processor, and is used to manipulate values for comparisons and calculations.
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.
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 one.
The bitwise NOT, or 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 0111 (decimal 7) = 1000 (decimal 8)
NOT 10101011 (decimal 171) = 01010100 (decimal 84)
The bitwise complement 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.
A bitwise AND takes two equal-length binary representations and performs the logical AND operation on each pair of the corresponding bits, which is equivalent to multiplying them. 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 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, 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 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.
A bitwise OR 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)
A bitwise XOR 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 the first bit is 1 or only the second bit 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 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 memory than loading a zero value and saving it to the register.
Assuming , for the non-negative integers, the bitwise operations can be written as follows:
Here is the bitwise equivalent operations of two bits P and Q:
(p OR q)
|p XOR q||NOT
(p AND q)
|p AND q||NOT
(p XOR q)
|p OR q||1|
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. Registers 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.
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 (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:
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), 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 2n (provided the value does not overflow), while a right arithmetic shift by n of a two's complement value is equivalent to dividing by 2n and rounding toward negative infinity. If the binary number is treated as ones' complement, then the same right-shift operation results in division by 2n and rounding toward zero.
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 binary numbers.
Another form of shift is the circular shift, bitwise rotation or bit rotation.
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.
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, 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 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;
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, 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.
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.
The C-family of languages lack a rotate operator, but one can be synthesized from the shift operators. Care must be taken to ensure the statement is well formed to avoid undefined behavior and timing attacks in software with security requirements. For example, a naive implementation that left rotates a 32-bit unsigned value
n positions is simply:
unsigned int x = ..., n = ...; unsigned int 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 is outside the range
[0 - 31] inclusive. A second try might result in:
unsigned int x = ..., n = ...; unsigned int y = n ? (x << n) | (x >> (32 - n)) : x;
where the shift amount is tested to ensure 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, the following is recommended. The pattern is recognized by many compilers, and the compiler will emit a single rotate instruction:
unsigned int x = ..., n = ...; unsigned int y = (x << n) | (x >> (-n & 31));
There are also compiler-specific intrinsics implementing circular shifts, like _rotl8, _rotl16, _rotr8, _rotr16 in Microsoft Visual C++. Clang provides some rotate intrinsics for Microsoft compatibility that suffers the problems above. GCC does not offer rotate intrinsics. Intel also provides x86 Intrinsics.
In Java, 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:
>>(signed right shift), and
>>>(unsigned right shift) are called the shift operators.
aByte >>> 2is equivalent to
((int) aByte) >>> 2.
n >>> sis n right-shifted s bit positions with zero-extension.
byteis 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
byte b1 = -5; int i = b1 | 0x0200;will give
i == -5as result.
In Pascal, as well as in all its dialects (such as Object Pascal and Standard Pascal), the left and right shift operators are "
shl" and "
shr", respectively. 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;
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 implementation of ancient Egyptian multiplication showing how to multiply two arbitrary integers
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
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
In digital circuits, an adder–subtractor is a circuit that is capable of adding or subtracting numbers (in particular, binary). Below is a circuit that does adding or subtracting depending on a control signal. It is also possible to construct a circuit that performs both addition and subtraction at the same time.Arithmetic shift
In computer programming, an arithmetic shift is a shift operator, sometimes termed a signed shift (though it is not restricted to signed operands). The two basic types are the arithmetic left shift and the arithmetic right shift. For binary numbers it is a bitwise operation that shifts all of the bits of its operand; every bit in the operand is simply moved a given number of bit positions, and the vacant bit-positions are filled in. Instead of being filled with all 0s, as in logical shift, when shifting to the right, the leftmost bit (usually the sign bit in signed integer representations) is replicated to fill in all the vacant positions (this is a kind of sign extension).
Some authors prefer the terms sticky right-shift and zero-fill right-shift for arithmetic and logical shifts respectively.Arithmetic shifts can be useful as efficient ways to perform multiplication or division of signed integers by powers of two. Shifting left by n bits on a signed or unsigned binary number has the effect of multiplying it by 2n. Shifting right by n bits on a two's complement signed binary number has the effect of dividing it by 2n, but it always rounds down (towards negative infinity). This is different from the way rounding is usually done in signed integer division (which rounds towards 0). This discrepancy has led to bugs in more than one compiler.For example, in the x86 instruction set, the SAR instruction (arithmetic right shift) divides a signed number by a power of two, rounding towards negative infinity. However, the IDIV instruction (signed divide) divides a signed number, rounding towards zero. So a SAR instruction cannot be substituted for an IDIV by power of two instruction nor vice versa.Bit flipping
In computing, bit flipping may refer to:
Bit manipulation, algorithmic manipulation of binary digits (bits)
Bitwise operation NOT, performing logical negation to a single bit, or each of several bits, switching state 0 to 1, and vice versa
Memory error or soft error, an unintentional state switch from 0 to 1, or vice versa, of a bit stored to random access memory or other mediumBit 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, data compression, encryption algorithms, and optimization. For most other tasks, modern programming languages allow the programmer to work directly with abstractions instead of bits that represent those abstractions. Source code that does bit manipulation makes use of the bitwise operations: AND, OR, XOR, NOT, and bit shifts.
Bit manipulation, in some cases, can obviate or reduce the need to loop over a data structure and can give many-fold speed ups, as bit manipulations are processed in parallel, but the code can become more difficult to write and maintain.Bitwise operations in C
In the C programming language, operations can be performed on a bit level using bitwise operators.
Bitwise operations are contrasted by byte-level operations which characterize the bitwise operators' logical counterparts, the AND, OR and NOT operators. Instead of performing on individual bits, byte-level operators perform on strings of eight bits (known as bytes) at a time. The reason for this is that a byte is normally the smallest unit of addressable memory (i.e. data with a unique memory address.)
This applies to bitwise operators as well, which means that even though they operate on only one bit at a time they cannot accept anything smaller than a byte as their input.
All of these operators are also available in C++.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 operation. A circular shift is a special kind of cyclic permutation, which in turn is a special kind of permutation. Formally, a circular shift is a permutation σ of the n entries in the tuple such that either
The result of repeatedly applying circular shifts to a given tuple are also called the circular shifts of the tuple.
For example, repeatedly applying circular shifts to the four-tuple (a, b, c, d) successively gives
and then the sequence repeats; this four-tuple therefore has four distinct circular shifts. However, not all n-tuples have n distinct circular shifts. For instance, the 4-tuple (a, b, a, b) only has 2 distinct circular shifts. In general the number of circular shifts of an n-tuple could be any divisor of n, depending on the entries of the tuple.
In computer programming, a bitwise rotation, also known as a circular shift, is a bitwise operation that shifts all bits of its operand. Unlike an arithmetic shift, a circular shift does not preserve a number's sign bit or distinguish a floating-point number's exponent from its significand. Unlike a logical shift, the vacant bit positions are not filled in with zeros but are filled in with the bits that are shifted out of the sequence.Exclusive or
Exclusive or or exclusive disjunction is a logical operation that outputs true only when inputs differ (one is true, the other is false).It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, ⊻, ⩒, ⩛, ⊕, ↮, and ≢. The negation of XOR is logical biconditional, which outputs true only when both inputs are the same.
It gains the name "exclusive or" because the meaning of "or" is ambiguous when both operands are true; the exclusive or operator excludes that case. This is sometimes thought of as "one or the other but not both". This could be written as "A or B, but not, A and B".
More generally, XOR is true only when an odd number of inputs are true. A chain of XORs—a XOR b XOR c XOR d (and so on)—is true whenever an odd number of the inputs are true and is false whenever an even number of inputs are true.GF(2)
GF(2) (also F2, Z/2Z or Z2) is the Galois field of two elements. It is the smallest field.Involution (mathematics)
In mathematics, an involution, or an involutory function, is a function f that is its own inverse,
f(f(x)) = xfor all x in the domain of f.The term anti-involution refers to involutions based on antihomomorphisms (see below the section on Quaternion algebra, groups, semigroups)
f(xy) = f(y) f(x)such that
xy = f(f(xy)) = f( f(y) f(x) ) = f(f(x)) f(f(y)) = xy.LSL
LSL is a three letter abbreviation, which may refer to:
SportsLeicestershire Senior League, a football competition
Leinster Senior League (association football), an amateur football league
Leinster Senior League (Men's hockey), a field hockey league in Ireland
Leinster Senior League (rugby), an Irish rugby union competitionComputersLeisure Suit Larry, a series of adult adventure games
Linden Scripting Language, a scripting language
Logical shift left, a type of bitwise operation
Larch Shared Language, a language for algebraic specification of abstract data typesFinanceLending Solutions, also known as LSL Properties, a UK-based company
Lincoln Savings and Loan Association, the financial institution at the heart of the Keating Five scandal
LSL, the ISO 4217 Code for the Lesotho loti, the currency of the Kingdom of LesothoOtherLSL, Laurent Salvador Lamothe, former Prime Minister of Haiti, and founder of LSL World Initiative
Lisa Scott-Lee (born 1975), Welsh singer
LSL (gene), a human gene
Lake Shore Limited, an Amtrak railroad line
Lake Shore Limited (NYC train), the predecessor of the above line
Landing Ship Logistics, an amphibious warfare vessel of the United Kingdom
Lycée Saint-Louis, a French higher education establishment and Classe préparatoire aux grandes écoles
Laminated strand lumber, a type of engineered wood
Liberty Shoes Limited, an Indian footwear manufacturer
Locomotive Services Limited, train operator in England
Long Service Leave, an employee vacation payable after long service in Australia and New ZealandList of computers with on-board BASIC
This is a list of computers with on-board BASIC. They shipped standard with a version of BASIC that was installed in the computer. The computers can access the BASIC language without the user inserting cartridges or loading software from external media.
BASICs with Bitwise Ops use -1 as true and the AND and OR operators perform a bitwise operation on the arguments.
FOR/NEXT skip means that body of the loop is skipped if the initial value of the loop times the sign of the step exceeds the final value times the sign of the step (such as 2 TO 1 STEP 1 or 1 TO 2 STEP -1). The statements inside the FOR/NEXT loop will not be executed at all.Numeric support indicates if a BASIC supports Integers and/or Floating Point.
Variable Name Length is how many characters of a variable name are used to determine uniqueness.
Full tokenization means that all keywords are converted to tokens and all extra space characters are removed. Partial tokenization leaves extra space characters in the source. None means that no tokenization is done. How to test for full tokenization:
If it is fully tokenized it should return 10 PRINT "HELLO" without all the extra spaces that were entered.Logical disjunction
In logic and mathematics, or is the truth-functional operator of (inclusive) disjunction, also known as alternation; the or of a set of operands is true if and only if one or more of its operands is true. The logical connective that represents this operator is typically written as ∨ or +.
is true if is true, or if is true, or if both and are true.
In logic, or by itself means the inclusive or, distinguished from an exclusive or, which is false when both of its arguments are true, while an "or" is true in that case.
An operand of a disjunction is called a disjunct.
Related concepts in other fields are:Logical shift
See also: Shift left testing about enabling testing early (left) in the development chain of software
In computer science, a logical shift is a bitwise operation that shifts all the bits of its operand. The two base variants are the logical left shift and the logical right shift. This is further modulated by the number of bit positions a given value shall be shifted, such as shift left by 1 or shift right by n. Unlike an arithmetic shift, a logical shift does not preserve a number's sign bit or distinguish a number's exponent from its significand (mantissa); every bit in the operand is simply moved a given number of bit positions, and the vacant bit-positions are filled, usually with zeros, and possibly ones (contrast with a circular shift).
A logical shift is often used when its operand is being treated as a sequence of bits instead of as a number.
Logical shifts can be useful as efficient ways to perform multiplication or division of unsigned integers by powers of two. Shifting left by n bits on a signed or unsigned binary number has the effect of multiplying it by 2n. Shifting right by n bits on an unsigned binary number has the effect of dividing it by 2n (rounding towards 0).
The programming languages C, C++, and Go, however, have only one right shift operator, >>. Most C and C++ implementations, and Go, choose which right shift to perform depending on the type of integer being shifted: signed integers are shifted using the arithmetic shift, and unsigned integers are shifted using the logical shift.
All currently relevant C standards (ISO/IEC 9899:1999 to 2011) leave a definition gap for cases where the number of shifts is equal to or bigger than the number of bits in the operands in a way that the result is undefined. This helps allow C compilers to emit efficient code for various platforms by allowing direct use of the native shift instructions which have differing behavior. For example, shift-left-word in PowerPC chooses the more-intuitive behavior where shifting by the bit width or above gives zero, whereas SHL in x86 chooses to mask the shift amount to the lower bits to reduce the maximum execution time of the instructions, and as such a shift by the bit width doesn't change the value.Some languages, such as the .NET Framework and LLVM, also leave shifting by the bit width and above unspecified (.NET) or undefined (LLVM). Others choose to specify the behavior of their most common target platforms, such as C# which specifies the x86 behavior.Mask (computing)
In computer science, a mask or bitmask is data that is used for bitwise operations, particularly in a bit field. Using a mask, multiple bits in a byte, nibble, word etc. can be set either on, off or inverted from on to off (or vice versa) in a single bitwise operation.Material nonimplication
Material nonimplication or abjunction (Latin ab = "from", junctio =–"joining") is the negation of material implication. That is to say that for any two propositions and , the material nonimplication from to is true if and only if the negation of the material implication from to is true. This is more naturally stated as that the material nonimplication from to is true only if is true and is false.
It may be written using logical notation as , , or "Lpq" (in Bocheński notation), and is logically equivalent to , and .Palace of Magic
Palace of Magic is a computer game released on 1 November 1987 for the Acorn Electron and BBC Micro by Superior Software. Combining platform elements with problem solving, it uses extremely similar gameplay principles to that of the earlier and better known game, Citadel. As with that game, it is an early example of the Metroidvania genre.
The game begins with your character in a palace, having been shrunk and taken out of your normal place and time by an evil wizard called Caldeti (an anagram of Citadel).
The overall objective is to magically restore your character to his original size and to find the teleporter to their home world. This involves guiding your character through the Palace and other external locations, such as a church, woods and a dungeon, overcoming various obstacles and enemies along the way.SHR
SHR can refer to:
The IATA code for Sheridan County Airport
"Shift right", SHR is a logical shift, a bitwise operation that shifts all the bits of its operand.
SHR (instruction), the x86 command for logical shift right (unsigned divide)
Shrewsbury railway station has the station code SHR
Sierra High Route, an off-trail route in California's High Sierras
Society for Human Rights, an early gay rights organization
Spontaneously hypertensive rat, an animal model of human cardiovascular disorders and human psychiatric disorders.
SHR, a Linux distribution for smartphones
Stewart-Haas Racing, NASCAR Sprint Cup race team
School House Rock, a Television Show
Supplementary Homicide Reports, a United States database of homicides
Synology Hybrid RAID, similar to RAIDValue numbering
Value numbering is a technique of determining when two computations in a program are equivalent and eliminating one of them with a semantics preserving optimization.XOR swap algorithm
In computer programming, the XOR swap is an algorithm that uses the XOR bitwise operation to swap values of distinct variables having the same data type without using a temporary variable. "Distinct" means that the variables are stored at different, non-overlapping, memory addresses; the actual values of the variables do not have to be different.