HOME

TheInfoList



OR:

In the
C programming language C (''pronounced'' '' – like the letter c'') is a general-purpose programming language. It was created in the 1970s by Dennis Ritchie and remains very widely used and influential. By design, C's features cleanly reflect the capabilities of ...
, operations can be performed on a bit level using
bitwise operators In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral (considered as a bit string) at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic opera ...
. Bitwise operations are contrasted by byte-level operations which characterize the bitwise operators' logical counterparts, the AND, OR, 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 In computing, a memory address is a reference to a specific memory location in memory used by both software and hardware. These addresses are fixed-length sequences of digits, typically displayed and handled as unsigned integers. This numeric ...
). 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++, and many C-family languages.


Bitwise operators

C provides six
operators Operator may refer to: Mathematics * A symbol indicating a mathematical operation * Logical operator or logical connective in mathematical logic * Operator (mathematics), mapping that acts on elements of a space to produce elements of another ...
for
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 error correction, corr ...
. Regarded by many to be the authoritative reference on C.


Bitwise AND &

The bitwise AND operator is a single ampersand: &. It is just a representation of AND which does its work on the bits of the operands rather than the truth value of the operands. Bitwise binary AND performs
logical conjunction In logic, mathematics and linguistics, ''and'' (\wedge) is the Truth function, truth-functional operator of conjunction or logical conjunction. The logical connective of this operator is typically represented as \wedge or \& or K (prefix) or ...
(shown in the table above) of the bits in each position of a number in its binary form. For instance, working with a byte (the char type): 11001000 & 10111000 -------- = 10001000 The
most significant bit In computing, bit numbering is the convention used to identify the bit positions in a binary numeral system, binary number. Bit significance and indexing In computing, the least significant bit (LSb) is the bit position in a Binary numeral sy ...
of the first number is 1 and that of the second number is also 1 so the most significant
bit The bit is the most basic unit of information in computing and digital communication. 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 represented as ...
of the result is 1; in the second most significant bit, the bit of second number is zero, so we have the result as 0.


Bitwise OR ,

Similar to bitwise AND, bitwise OR performs
logical disjunction In logic, disjunction (also known as logical disjunction, logical or, logical addition, or inclusive disjunction) is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is ...
at the bit level. Its result is a 1 if either of the bits is 1 and zero only when both bits are 0. Its symbol is , which can be called a pipe. 11001000 , 10111000 -------- = 11111000


Bitwise XOR ^

The bitwise XOR (exclusive or) performs an
exclusive disjunction Exclusive or, exclusive disjunction, exclusive alternation, logical non-equivalence, or Logical_equality#Inequality, logical inequality is a Logical connective, logical operator whose negation is the logical biconditional. With two inputs, X ...
, which is equivalent to adding two bits and discarding the carry. The result is zero only when we have two zeroes or two ones. XOR can be used to toggle the bits between 1 and 0. Thus i = i ^ 1 when used in a loop toggles its values between 1 and 0. 11001000 ^ 10111000 -------- = 01110000


Shift operators

There are two bitwise shift operators. They are *Right shift (>>) *Left shift (<<)


Right shift >>

The symbol of right shift operator is >>. For its operation, it requires two
operand In mathematics, an operand is the object of a mathematical operation, i.e., it is the object or quantity that is operated on. Unknown operands in equalities of expressions can be found by equation solving. Example The following arithmetic expres ...
s. It shifts each bit in its left operand to the right. The number following the operator decides the number of places the bits are shifted (i.e. the right operand). Thus by doing ch >> 3 all the bits will be shifted to the right by three places and so on. However, do note that a shift operand value which is either a negative number or is greater than or equal to the total number of bits in this value results in
undefined behavior In computer programming, a program exhibits undefined behavior (UB) when it contains, or is executing code for which its programming language specification does not mandate any specific requirements. This is different from unspecified behavior, ...
. For example, when shifting a 32 bit unsigned integer, a shift amount of 32 or higher would be undefined. Example: :If the variable ch contains the bit pattern 11100101, then ch >> 1 will produce the result 01110010, and ch >> 2 will produce 00111001. Here blank spaces are generated simultaneously on the left when the bits are shifted to the right. When performed on an unsigned type or a non-negative value in a signed type, the operation performed is a
logical shift 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 v ...
, causing the blanks to be filled by 0s (zeros). When performed on a negative value in a signed type, the result is technically implementation-defined (compiler dependent), however most compilers will perform an
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 ...
, causing the blank to be filled with the set sign bit of the left operand. Right shift can be used to divide a bit pattern by 2 as shown: i = 14; // Bit pattern 00001110 j = i >> 1; // here we have the bit pattern shifted by 1 thus we get 00000111 = 7 which is 14/2


Right shift operator usage

Typical usage of a right shift operator in C can be seen from the following code. Example: #include void showbits( unsigned int x ) int main( void ) The output of the above program will be 5225 in binary 00000000000000000001010001101001 5225 right shift 0 gives 00000000000000000001010001101001 5225 right shift 1 gives 00000000000000000000101000110100 5225 right shift 2 gives 00000000000000000000010100011010 5225 right shift 3 gives 00000000000000000000001010001101 5225 right shift 4 gives 00000000000000000000000101000110 5225 right shift 5 gives 00000000000000000000000010100011


Left shift <<

The symbol of left shift operator is <<. It shifts each bit in its left-hand operand to the left by the number of positions indicated by the right-hand operand. It works opposite to that of right shift operator. Thus by doing ch << 1 in the above example (11100101) we have 11001010. Blank spaces generated are filled up by zeroes as above. However, do note that a shift operand value which is either a negative number or is greater than or equal to the total number of bits in this value results in
undefined behavior In computer programming, a program exhibits undefined behavior (UB) when it contains, or is executing code for which its programming language specification does not mandate any specific requirements. This is different from unspecified behavior, ...
. This is defined in the standard a
ISO 9899:2011 6.5.7 Bit-wise shift operators
For example, when shifting a 32 bit unsigned integer, a shift amount of 32 or higher would be undefined. Left shift can be used to multiply an integer by powers of 2 as in int i = 7; // Decimal 7 is Binary (2^2) + (2^1) + (2^0) = 0000 0111 int j = 3; // Decimal 3 is Binary (2^1) + (2^0) = 0000 0011 k = (i << j); // Left shift operation multiplies the value by 2 to the power of j in decimal // Equivalent to adding j zeros to the binary representation of i // 56 = 7 * 2^3 // 0011 1000 = 0000 0111 << 0000 0011


Example: a simple addition program

The following program adds two operands using AND, XOR and left shift (<<). #include int main( void )


Bitwise assignment operators

C provides a compound assignment operator for each
binary Binary may refer to: Science and technology Mathematics * Binary number, a representation of numbers using only two values (0 and 1) for each digit * Binary function, a function that takes two arguments * Binary operation, a mathematical op ...
arithmetic and bitwise operation. Each operator accepts a left operand and a right operand, performs the appropriate binary operation on both and stores the result in the left operand. The bitwise assignment operators are as follows.


Logical equivalents

Four of the bitwise operators have equivalent logical operators. They are equivalent in that they have the same truth tables. However, logical operators treat each operand as having only one value, either true or false, rather than treating each bit of an operand as an independent value. Logical operators consider zero false and any nonzero value true. Another difference is that logical operators perform
short-circuit evaluation Short-circuit evaluation, minimal evaluation, or McCarthy evaluation (after John McCarthy) is the semantics of some Boolean operators in some programming languages in which the second argument is executed or evaluated only if the first argumen ...
. The table below matches equivalent operators and shows a and b as operands of the operators. != has the same truth table as ^ but unlike the true logical operators, by itself != is not strictly speaking a logical operator. This is because a logical operator must treat any nonzero value the same. To be used as a logical operator != requires that operands be normalized first. A logical not applied to both operands will not change the truth table that results but will ensure all nonzero values are converted to the same value before comparison. This works because ! on a zero always results in a one and ! on any nonzero value always results in a zero. Example: /* Equivalent bitwise and logical operator tests */ #include void testOperator(char* name, unsigned char was, unsigned char expected); int main( void ) void testOperator( char* name, unsigned char was, unsigned char expected ) The output of the above program will be Bitwise AND passed, was: 8 expected: 8 Bitwise OR passed, was: E expected: E Bitwise XOR passed, was: 6 expected: 6 Bitwise NOT passed, was: FE expected: FE Logical AND passed, was: 1 expected: 1 Logical AND passed, was: 0 expected: 0 Logical AND passed, was: 0 expected: 0 Logical AND passed, was: 0 expected: 0 Logical OR passed, was: 1 expected: 1 Logical OR passed, was: 1 expected: 1 Logical OR passed, was: 1 expected: 1 Logical OR passed, was: 0 expected: 0 Logical XOR passed, was: 0 expected: 0 Logical XOR passed, was: 1 expected: 1 Logical XOR passed, was: 1 expected: 1 Logical XOR passed, was: 0 expected: 0 Logical NOT passed, was: 1 expected: 1 Logical NOT passed, was: 0 expected: 0


See also

*
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 error correction, corr ...
*
Bitwise operation In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral (considered as a bit string) at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic operatio ...
*
Find first set In computer software and hardware, find first set (ffs) or find first one is a bit operation that, given an unsigned Word (computer architecture), machine word, designates the index or position of the least significant bit set to one in the word c ...
*
Operators in C and C++ This is a list of operators in the C and C++ programming languages. All listed operators are in C++ and lacking indication otherwise, in C as well. Some tables include a "In C" column that indicates whether an operator is also in C. Note tha ...
*
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 d ...
*
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 denot ...
* XOR swap algorithm * XOR linked list


References

{{Reflist


External links


Bitwise OperatorsDemystifying bitwise operations, a gentle C tutorial
Binary arithmetic C (programming language) Articles with example C code