From Wikipedia, the free encyclopedia - View original article

Operations on bits at individual levels can be carried out using **Bitwise operations in the C programming language**.

Bits come together to form a byte which is the lowest form of data that can be accessed in digital hardwares. The whole representation of a number is considered while applying a bitwise operator.

C provides six operators for bit manipulation.^{[1]}

Symbol | Operator |
---|---|

& | bitwise AND |

| | bitwise inclusive OR |

^ | bitwise exclusive OR |

<< | left shift |

>> | right shift |

~ | bitwise NOT (one's complement) (unary) |

bit a | bit b | a & b (a AND b) |
---|---|---|

0 | 0 | 0 |

0 | 1 | 0 |

1 | 0 | 0 |

1 | 1 | 1 |

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 does the logical **AND** (as 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):

11001110 & 10011000 = 10001000

The most significant bit of the first number is 1 and that of the second number is also 1 so the most significant bit 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. ^{[2]}

bit a | bit b | a | b (a OR b) |
---|---|---|

0 | 0 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 1(0 with carry 1) |

Similar to bitwise AND, bitwise OR only operates at the bit level. Its result is a 1 if one of the either bits is 1 and zero only when both bits are 0. Its symbol is '|' which can be called a **pipe**.

11001110 | 10011000 = 11011110

^{[2]}

bit a | bit b | a ^ b (a XOR b) |
---|---|---|

0 | 0 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 0 |

The Bitwise EX-OR (Exclusive Or) performs a logical EX-OR function, equivalent to adding two bits, discarding the carry. The result is zero only when we have 2 zeroes or ones to perform on.^{[3]} EX-OR 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. ^{[4]}

bit a | ~a (complement of a) |
---|---|

0 | 1 |

1 | 0 |

The one's complement (~) or the bitwise complement gets us the complement of a given number. Thus we get the bits inverted, for every bit 1 the result is bit 0 and conversely for every bit 0 we have a bit 1. This operation should not be confused with logical negation "!".

bit a | bit b | a & b (a AND b) | a | b (a OR b) | a ^ b (a XOR b) |
---|---|---|---|---|

0 | 0 | 0 | 0 | 0 |

0 | 1 | 0 | 1 | 1 |

1 | 0 | 0 | 1 | 1 |

1 | 1 | 1 | 1 | 0 |

There are two bitwise shift operators. They are:

- Right shift (>>)

- Left shift (<<)

The symbol of right shift operator is **>>**. For its operation, it requires two operands. 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.

Example:

If the variable ch contains the bit pattern 11100101, thench >> 1will give the output as01110010, andch >> 2will give00111001.

Here blank spaces are generated simultaneously on the left when the bits are shifted to the right. When performed on an unsigned type, the operation performed is a logical shift, causing the blanks to be filled by 0s (zeros). When performed on a signed type, an arithmetic shift is performed, causing the blank to be filled with the sign bit of the left operand.

Right shift can be used to divide a bit pattern by 2 as shown:

i = 14; // Bit pattern 1110 j = i >> 1; // here we have the bit pattern shifted by 1 thus we get 111 = 7 which is 14/2

Typical usage of a right shift operator in C can be seen from the following code.

Example:

#include <stdio.h> void showbits(unsigned int x) { int i; for(i=(sizeof(int)*8)-1; i>=0; i--) (x&(1<<i))?putchar('1'):putchar('0'); printf("\n"); } int main() { int j = 5225, m, n; printf("The decimal %d is equal to binary - ", j); /* assume we have a function that prints a binary string when given a decimal integer */ showbits(j); /* the loop for right shift operation */ for ( m = 0; m <= 5; m++ ) { n = j >> m; printf("%d right shift %d gives ", j, m); showbits(n); } return 0; }

The output of the above program will be:

The decimal 5225 is equal to binary - 0001010001101001 5225 right shift 0 gives 0001010001101001 5225 right shift 1 gives 0000101000110100 5225 right shift 2 gives 0000010100011010 5225 right shift 3 gives 0000001010001101 5225 right shift 4 gives 0000000101000110 5225 right shift 5 gives 0000000010100011

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 we have 111001010. Blank spaces generated are filled up by zeroes as above.

Left shift can be used to multiply an integer in multiples of 2 as in:

int i = 4; /* bit pattern equivalent is 100 */ int j = i << 2; /* makes it 10000 a multiple of 2 i.e. 16 */

The following program adds 2 operands using AND, EX-OR and left shift (<<).

#include <stdio.h> int main() { unsigned int x = 3, y = 1, sum, carry; sum = x ^ y; // Ex - OR x and y carry = x & y; // AND x and y while (carry != 0) { carry = carry << 1; // left shift the carry x = sum; // initialize x as sum y = carry; // initialize y as carry sum = x ^ y; // sum is calculated carry = x & y; /* carry is calculated, the loop condition is evaluated and the process is repeated until carry is equal to 0. */ } printf("%d\n", sum); // the program will print 4 return 0; }

C provides a compound assignment operator for each binary arithmetic and bitwise operation (i.e. each operation which accepts two operands). Each of the compound bitwise assignment operators perform the appropriate binary operation and store the result in the left operand.^{[5]}

The bitwise assignment operators are as follows:

Symbol | Operator |
---|---|

&= | bitwise AND assignment |

|= | bitwise inclusive OR assignment |

^= | bitwise exclusive OR assignment |

<<= | left shift assignment |

>>= | right shift assignment |

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 non zero true. Another difference is that logical operators perform Short-circuit evaluation.

The table below matches equivalent operators and shows a and b as operands of the operators.

Bitwise | Logical |
---|---|

a & b | a && b |

a | b | a || b |

a ^ b | !a != !b |

~a | !a |

!= 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 non zero value the same. To be used as a logical operator != requires that operands be normalized first. A logical not applied to both operands won't change the truth table that results but will ensure all non zero values are converted to the same value before comparison. This works because ! on a zero always results in a one and ! on any non zero always results in a zero.

The example below shows that the truth tables for these Bitwise and Logical operators are identical but also demonstrates how they act on their operands differently. The need to normalize operands for != can be demonstrated by introducing a char T2 = 0x02 and packing it in an array. Mixing T2 with T will show them being treated the same unless the operand NOTs around != are removed.

Example:

/* Equivalant bitwise and logical operator tests */ void testOperator(char* name, unsigned char was, unsigned char expected); main() { // -- Bitwise operators -- // //Truth tables packed in bits const unsigned char operand1 = 0x0A; //0000 1010 const unsigned char operand2 = 0x0C; //0000 1100 const unsigned char expectedAnd = 0x08; //0000 1000 const unsigned char expectedOr = 0x0E; //0000 1110 const unsigned char expectedXor = 0x06; //0000 0110 const unsigned char operand3 = 0x01; //0000 0001 const unsigned char expectedNot = 0xFE; //1111 1110 testOperator("Bitwise AND", operand1 & operand2, expectedAnd); testOperator("Bitwise OR", operand1 | operand2, expectedOr); testOperator("Bitwise XOR", operand1 ^ operand2, expectedXor); testOperator("Bitwise NOT", ~operand3, expectedNot); printf("\n"); // -- Logical operators -- // const unsigned char F = 0x00; //Zero const unsigned char T = 0x01; //Any non zero //Truth tables packed in arrays const unsigned char operandArray1[4] = {T, F, T, F}; const unsigned char operandArray2[4] = {T, T, F, F}; const unsigned char expectedArrayAnd[4] = {T, F, F, F}; const unsigned char expectedArrayOr[4] = {T, T, T, F}; const unsigned char expectedArrayXor[4] = {F, T, T, F}; const unsigned char operandArray3[2] = {F, T}; const unsigned char expectedArrayNot[2] = {T, F}; int i; for (i = 0; i < 4; i++) { testOperator("Logical AND", operandArray1[i] && operandArray2[i], expectedArrayAnd[i]); } printf("\n"); for (i = 0; i < 4; i++) { testOperator("Logical OR", operandArray1[i] || operandArray2[i], expectedArrayOr[i]); } printf("\n"); for (i = 0; i < 4; i++) { //Needs ! on operand's in case non zero values are different testOperator("Logical XOR", !operandArray1[i] != !operandArray2[i], expectedArrayXor[i]); } printf("\n"); for (i = 0; i < 2; i++) { testOperator("Logical NOT", !operandArray3[i], expectedArrayNot[i]); } printf("\n"); } void testOperator(char* name, unsigned char was, unsigned char expected) { char* result = (was == expected) ? "passed" : "failed"; printf("%s %s test, was: %X expected: %X \n", name, result, was, 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

- Bit manipulation
- Bitwise operation
- Operators in C and C++
- Bitboard
- Boolean algebra (logic)
- XOR swap algorithm
- XOR linked list

**^**Kernighan; Dennis M. Ritchie (March 1988).*The C Programming Language*(2nd ed.). Englewood Cliffs, NJ: Prentice Hall. ISBN 0-13-110362-8. Regarded by many to be the authoritative reference on C.- ^
^{a}^{b}http://www.cprogramming.com/tutorial/bitwise_operators.html **^**http://www.electronics-tutorials.ws/logic/logic_7.html**^**http://www.fredosaurus.com/notes-cpp/expressions/bitops.html**^**"C/C++ Compound assignment operators".*XL C/C++ V8.0 for AIX*(in EN-US). IBM. Retrieved 11 November 2013.