Thursday, August 27, 2015

Bitwise Operators

We know about arithmetic operators. The operators $+,-,/$ and $\times$ adds, subtracts, divides and multiplies respectively. We also have another operator $\%$ which finds the modulus.

Today, we going to look at $6$ more operators called "Bitwise Operators". Why are they called "Bitwise Operators"? That's because they work using the binary numerals (bits, which are the individual digits of the binary number) of their operands. Why do we have such operators? That's because in computers all information is stored as strings of bits, that is, binary numbers. Having operators that work directly on them is pretty useful.

We need to have a good idea how Binary Number System works in order to understand how these operators work. Read more on number system in [1]Introduction to Number Systems. Use the $decimalToBase()$ function from [1] to convert the decimal numbers to binary and see how they are affected.

Bitwise AND ($\&$) Operator

The $\&$ operator is a binary operator. It takes two operands and returns single integer as the result. Here is how it affects the bits.

$0 \: \& \: 0 = 0$
$0 \: \& \:  1 = 0$
$1 \: \& \:  0 = 0$
$1 \: \& \:  1 = 1$

It takes two bits and returns another bit. The $\&$ operator will take two bits $a, b$ and return $1$ only if both $a$ AND $b$ are $1$. Otherwise, it will return $0$.

But that's only for bits. What happens when we perform $\&$ operation on two integer number?

For example, what is the result of  $A \: \& \:  B$ when $A = 12$ and  $ B =10$?

Since $\&$ operator works on bits of binary numbers we have to convert $A$ and $B$ to binary numbers.

$A = (12)_{10} = (1100)_2$
$B = (10)_{10} = (1010)_2$

We know how to perform $\&$ on individual bits, but how do we perform $\&$ operation on strings of bits? Simple, take each position of the string and perform and operations using bits of that position.

$1100$
$\underline{1010}\: \&$
$1000$

Therefore, $12 \: \& \:  10 = 8$.

In C++, it's equivalent code is:
printf ("%d\n", 12 & 10 );

Bitwise OR ($|$) Operator

The $|$ operator is also a binary operator. It takes two operands and returns single integer as the result. Here is how it affects the bits:

$0 \: | \: 0 = 0$
$0 \: | \: 1 = 1$
$1 \: | \: 0 = 1$
$1 \: | \: 1 = 1$

The $|$ operator takes two bits $a, b$ and return $1$ if $a$ OR $b$ is $1$. Therefore, it return $0$ only when both $a$ and $b$ are $0$.

What is the value of $A\:|\:B$ if $A=12$ and $B=10$? Same as before, convert them into binary numbers and apply $|$ operator on both bits of each position.

$1100$
$\underline{1010}\: |$
$1110$

Therefore $12\:|\:10 = 14$.
printf ( "%d\n", 12 | 10 );

Bitwise XOR ($\wedge$) Operator

Another binary operator that takes two integers as operands and returns integer. Here is how it affects two bits:

$0 \: \wedge \: 0 = 0$
$0 \: \wedge \: 1 = 1$
$1 \: \wedge \: 0 = 1$
$1 \: \wedge \: 1 = 0$

XOR stands for Exclusive-OR. This operator returns $1$ only when both operand bits are not same. Otherwise, it returns $0$.

What is the value of $A\:\wedge\:B$ if $A=12$ and $B=10$?

$1100$
$\underline{1010}\: \wedge$
$0110$

Therefore, $12\:\wedge\:10 = 6$.

In mathematics, XOR is represented with $\oplus $, but I used $\wedge$ cause in C++ XOR is performed with $\wedge$.
printf ( "%d\n", 12 ^ 10 );

Bitwise Negation ($\sim$) Operator

This is a unary operator. It works on a single integer and flips all its bits. Here is how it affects individual bits:

$\sim\:0 = 1$
$\sim\: 1 = 0$

What is the value of $\sim \: A$ if $A = 12$?

$\sim \: (1100)_2 = (0011)_2 = (3)_{10}$

But this will not work in code cause $12$ in C++ is not $1100$, it is $0000...1100$. Each integer is $32$ bits long. So when each of the bits of the integer is flipped it becomes $11111...0011$. If you don't take unsigned int, the value will even come out negative.
printf ( "%d\n", ~12 );

Bitwise Left Shift ($<<$) Operator

The left shift operator is a binary operator. It takes two integers $a$ and $b$ and shifts the bits of $a$ towards LEFT $b$ times and adds $b$ zeroes to the end of $a$ in its binary system.

For example, $(13)_{10} << 3 = (1101)_2 << 3 = (110100)_2$.

Shifting the bits of a number $A$ left once is same as multiplying it by $2$. Shifting it left three times is same as multiplying the number by $2^3$.

Therefore, the value of $A << B = A \times 2^B$.
printf ( "%d\n", 1 << 3 );

Bitwise Right Shift ($>>$) Operator

The $>>$ Operator does opposite of $<<$ operator. It takes two integer $a$ and $b$ and shifts the bits of $a$ towards RIGHT $b$ times. The rightmost $b$ bits are lost and $b$ zeroes are added to the left end.

For example, $(13)_{10} >> 3 = (1101)_2 >> 3 = (1)_2$.

Shifting the bits of a number $A$ right once is same as dividing it by $2$. Shifting it right three times is same as dividing the number by $2^3$.

Therefore, the value of $A >> B = \lfloor \frac{A}{2^B} \rfloor$.
printf ( "%d\n", 31 >> 3 );

Tips and Tricks

  1. When using $<<$ operator, careful about overflow. If $A << B$ does not fit into $int$, make sure you type cast $A$ into $long\:long$. Typecasting $B$ into $long\:long$ does not work.
  2. $A \:\&\:B \leq MIN(A,B)$ 
  3. $A\:|\:B \geq MAX(A,B)$



That's all about bitwise operations. These operators will come useful during "Bits Manipulation". We will look into it on next post.

Resource

2 comments:

  1. In bitwise left shift operator, there should be another 0 in $ (13)_10 << 3 $

    ReplyDelete

Leave comments for Queries, Bugs and Hugs.