# Bit Operators
A bit wise OR operates on the bit level and uses the following Boolean truth table:
true OR true = true true OR false = true false OR false = false When the binary value for a ( 0101 ) and the binary value for b ( 1100 ) are OR ‘ed together we get the binary value of 1101 :
int a = 0 1 0 1 int b = 1 1 0 0 | --------- int c = 1 1 0 1 The bit wise OR does not change the value of the original values unless specifically assigned to using the bit wise assignment compound operator |= :
int a = 5; // 0101b (0x05) a |= 12; // a = 0101b | 1101b # ^ — bitwise XOR (exclusive OR)
int a = 5; // 0101b (0x05) int b = 9; // 1001b (0x09) int c = a ^ b; // 1100b (0x0C) std::cout "a = " a ", b = " b ", c = " c std::endl; A bit wise XOR (exclusive or) operates on the bit level and uses the following Boolean truth table:
true OR true = false true OR false = true false OR false = false Notice that with an XOR operation true OR true = false where as with operations true AND/OR true = true , hence the exclusive nature of the XOR operation.
Using this, when the binary value for a ( 0101 ) and the binary value for b ( 1001 ) are XOR ‘ed together we get the binary value of 1100 :
int a = 0 1 0 1 int b = 1 0 0 1 ^ --------- int c = 1 1 0 0 The bit wise XOR does not change the value of the original values unless specifically assigned to using the bit wise assignment compound operator ^= :
int a = 5; // 0101b (0x05) a ^= 9; // a = 0101b ^ 1001b The bit wise XOR can be utilized in many ways and is often utilized in bit mask operations for encryption and compression.
Note: The following example is often shown as an example of a nice trick. But should not be used in production code (there are better ways std::swap() to achieve the same result).
You can also utilize an XOR operation to swap two variables without a temporary:
int a = 42; int b = 64; // XOR swap a ^= b; b ^= a; a ^= b; std::cout "a = " a ", b = " b "\n"; To productionalize this you need to add a check to make sure it can be used.
void doXORSwap(int& a, int& b) // Need to add a check to make sure you are not swapping the same // variable with itself. Otherwise it will zero the value. if (&a != &b) // XOR swap a ^= b; b ^= a; a ^= b; > > So though it looks like a nice trick in isolation it is not useful in real code. xor is not a base logical operation,but a combination of others: a^c=~(a&c)&(a|c)
also in 2015+ compilers variables may be assigned as binary:
# & — bitwise AND
int a = 6; // 0110b (0x06) int b = 10; // 1010b (0x0A) int c = a & b; // 0010b (0x02) std::cout "a = " a ", b = " b ", c = " c std::endl; A bit wise AND operates on the bit level and uses the following Boolean truth table:
TRUE AND TRUE = TRUE TRUE AND FALSE = FALSE FALSE AND FALSE = FALSE When the binary value for a ( 0110 ) and the binary value for b ( 1010 ) are AND ‘ed together we get the binary value of 0010 :
int a = 0 1 1 0 int b = 1 0 1 0 & --------- int c = 0 0 1 0 The bit wise AND does not change the value of the original values unless specifically assigned to using the bit wise assignment compound operator &= :
int a = 5; // 0101b (0x05) a &= 10; // a = 0101b & 1010b int a = 1; // 0001b int b = a 1; // 0010b std::cout "a = " a ", b = " b std::endl; The left bit wise shift will shift the bits of the left hand value ( a ) the number specified on the right ( 1 ), essentially padding the least significant bits with 0’s, so shifting the value of 5 (binary 0000 0101 ) to the left 4 times (e.g. 5
int a = 7; while (a 200) std::cout <"a = " :: endl; a 1; > a = 7; while (a 200) std::cout <"a = " :: endl; a *= 2; > But it should be noted that the left shift operation will shift all bits to the left, including the sign bit, example:
int a = 2147483647; // 0111 1111 1111 1111 1111 1111 1111 1111 int b = a 1; // 1111 1111 1111 1111 1111 1111 1111 1110 std::cout "a = " a ", b = " b std::endl; Possible output: a = 2147483647, b = -2
While some compilers will yield results that seem expected, it should be noted that if you left shift a signed number so that the sign bit is affected, the result is undefined. It is also undefined if the number of bits you wish to shift by is a negative number or is larger than the number of bits the type on the left can hold, example:
int a = 1; int b = a -1; // undefined behavior char c = a 20; // undefined behavior The bit wise left shift does not change the value of the original values unless specifically assigned to using the bit wise assignment compound operator
int a = 5; // 0101b a 1; // a = a # >> — right shift
int a = 2; // 0010b int b = a >> 1; // 0001b std::cout "a = " a ", b = " b std::endl; The right bit wise shift will shift the bits of the left hand value ( a ) the number specified on the right ( 1 ); it should be noted that while the operation of a right shift is standard, what happens to the bits of a right shift on a signed negative number is implementation defined and thus cannot be guaranteed to be portable, example:
int a = -2; int b = a >> 1; // the value of b will be depend on the compiler It is also undefined if the number of bits you wish to shift by is a negative number, example:
int a = 1; int b = a >> -1; // undefined behavior The bit wise right shift does not change the value of the original values unless specifically assigned to using the bit wise assignment compound operator >>= :
int a = 2; // 0010b a >>= 1; // a = a >> 1; # ~ — bitwise NOT (unary complement)
unsigned char a = 234; // 1110 1010b (0xEA) unsigned char b = ~a; // 0001 0101b (0x15) std::cout "a = " static_castint>(a) ", b = " static_castint>(b) std::endl; A bit wise NOT (unary complement) operates on the bit level and simply flips each bit. If it’s a 1 , it’s changed to a 0 , if it’s a 0 , it’s changed to a 1 . The bit wise NOT has the same effect as XOR’ing a value against the max value for a specific type:
unsigned char a = 234; // 1110 1010b (0xEA) unsigned char b = ~a; // 0001 0101b (0x15) unsigned char c = a ^ ~0; The bit wise NOT can also be a convenient way to check the maximum value for a specific integral type:
unsigned int i = ~0; unsigned char c = ~0; std::cout "max uint = " i std::endl "max uchar = " static_castshort>(c) std::endl; The bit wise NOT does not change the value of the original value and does not have a compound assignment operator, so you can not do a ~= 10 for example.
The bit wise NOT ( ~ ) should not be confused with the logical NOT ( ! ); where a bit wise NOT will flip each bit, a logical NOT will use the whole value to do its operation on, in other words (!1) != (~1)
# Remarks
Bit shift operations are not portable across all processor architectures, different processors can have different bit-widths. In other words, if you wrote
This value would be different on a 64 bit machine vs. on a 32 bit machine, or from an x86 based processor to a PIC based processor.
Endian-ness does not need to be taken into account for the bit wise operations themselves, that is, the right shift ( >> ) will shift the bits towards the least significant bit and an XOR will perform an exclusive or on the bits. Endian-ness only needs to be taken into account with the data itself, that is, if endian-ness is a concern for your application, it’s a concern regardless of bit wise operations.
Boolean Operations
A bit is the minimum amount of information that we can imagine, since it only stores either value 1 or 0, which represents either YES or NO, activated or deactivated, true or false, etc. that is: two possible states each one opposite to the other, without possibility of any shades. We are going to consider that the two possible values of a bit are 0 and 1.
Several operations can be performed with bits, either in conjunction with other bits or themselves alone. These operations receive the name of boolean operations, a word that comes from the name of one of the mathematicians who contributed the more to this field: George Boole (1815-1864).
All these operations have an established behavior and all of them can be applied to any bit no matter which value they contain (either 0 or 1). Next you have a list of the basic boolean operations and a table with the behavior of that operation with every possible combination of bits.
AND
This operation is performed between two bits, which we will call a and b. The result of applying this AND operation is 1 if both a and b are equal to 1, and 0 in all other cases (i.e., if one or both of the variables is 0).
AND (&)
| a | b | a&b |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
OR
This operation is performed between two bits (a and b). The result is 1 if either one of the two bits is 1, or if both are 1. If none is equal to 1 the result is 0.
OR (|)
| a | b | a|b |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
XOR (Exclusive Or)
This operation is performed between two bits (a and b). The result is 1 if either one of the two bits is 1, but not in the case that both are. There for, if neither or both of them are equal to 1 the result is 0.
XOR (^)
| a | b | a^b |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
NOT
This operation is performed on a single bit. Its result is the inversion of the actual value of the bit: if it was set to 1 it becomes 0, and if it was 0 it becomes 1:
NOT (~)
| a | ~a |
|---|---|
| 0 | 1 |
| 1 | 0 |
These are the 4 basic boolean operations (AND, OR, XOR and NOT). Combining these operations we can obtain any possible result from two bits.
In C++, these operators can be used with variables of any integer data type; the boolean operation is performed to all of the bits of each variable involved. For example, supposing two variables: a and b, both of type unsigned char, where a contains 195 (11000011 in binary) and b contains 87 (or 01010111 in binary). If we write the following code:
unsigned char a=195; unsigned char b=87; unsigned char c; c=a&b;That means, that we conducted a bitwise AND operation between a and b. The operation is performed between the bits of the two variables that are located at the same position: The rightmost bit of c will contain the result of conducting the AND operation between the rightmost bits of a and b:
The same operation is also performed between the second bits of both variables, and the third, and so on, until the operation is performed between all bits of both variables (each one only with the same bit of the other variable).
The final binary value of c is 01000011, that is 67 in decimal numbers. So 195&87 is equal to 67.
Bitwise Operators in C/C++
The following program uses bitwise operators to perform bit operations in C.
C
C++
a = 5, b = 9 a & b = 1 a | b = 13 a ^ b = 12 ~a = -6 b > 1 = 4
Time Complexity: O(1)
Auxiliary Space: O(1)
Interesting Facts About Bitwise Operators
1. The left-shift and right-shift operators should not be used for negative numbers.
If the second operand(which decides the number of shifts) is a negative number, it results in undefined behavior in C. For example results of both 1 > -1 is undefined. Also, if the number is shifted more than the size of the integer, the behavior is undefined. For example, 1 Note: In C++, this behavior is well-defined.
2. Interestingly!! The bitwise OR of two numbers is just the sum of those two numbers if there is no carry involved, otherwise, you just add their bitwise AND.
Let’s say, we have a=5(101) and b=2(010), since there is no carry involved, their sum is just a|b. Now, if we change ‘a’ to 6 which is 110 in binary, their sum would change to a|b + a&b since there is a carry involved.
3. The bitwise XOR operator is the most useful operator from a technical interview perspective.
It is used in many problems. A simple example could be “Given a set of numbers where all elements occur an even number of times except one number, find the odd occurring number” This problem can be efficiently solved by just doing XOR to all numbers.