# Lesson 21

### Summary

Bit Manipulation
Bit Manipulation Operators
AND Operator
OR Operator
Exclusive OR Operator
NOT Operator
Bit Flags
Unsigned Integers
Sample Program
Shift Operators
Bit Manipulation

We have so far been dealing with bytes using different data types. In this lecture, we will
see what a bit is? Bit is the basic unit of memory. Eight bits form a byte. As you know
that data is stored in computers in 0’s and 1’s form. An integer uses four bytes and the
integer calculations occur in four bytes. Thus, we are manipulating bytes while using
different data types. Now we will try to understand the process of ‘bit manipulation’.
Now we will deal with each bit in a byte and explore how to do on or off each bit. A bit,
having 1 is said on while the one with 0 is called off. Here we will discuss different
operators to manipulate bits.
The concept of bit manipulation means that we can do work with a bit, the smallest unit
of memory. Bit manipulations utilize very small memory. Thus, we can make an efficient
use of the memory. The bit fields are of great use in operating systems and files
attributes. The bit manipulations are useful while working at operating system level.
Let’s have a look on different operators, used for bit manipulations.
Page 259
Bit Manipulation Operators

The following table shows different operators used for bit manipulation.

### Operator Operator Sign

Bitwise AND Operator &
Bitwise OR Operator |
Bitwise Exclusive OR
Operator

^
NOT Operator ~
Left Shift Operator <<
Right Shift Operator >>
Here & is the bit-wise AND operator. Don’t confuse it with the logical AND operator
&&. Similarly | is the bit-wise OR operator. Don’t confuse it with the logical OR operator
||.
Now let’s talk about these operators in detail.

### AND Operator ( & )

The AND operator (&) works just like the logical AND operator (&&) but on bits. It
compares two bits and returns 1 if both bits are 1. If any of the two bits being compared is
0, the result will be 0.
Following table, also called truth table, will further explain the operation of & operator.

### Bit1 Bit2 Bit1 & Bit2

1 1 1
1 0 0
0 1 0
0 0 0
We know that when a number is stored in memory, it gets stored in bit pattern which has
binary representation (only 1 and 0 ). So we can use & to AND two numbers bit-wise. To
understand this, consider the following example.
Suppose we have two numbers - 12 and 8 and want to apply & on these ones. Here we
will make use of the binary number system. The binary representation (base 2 system) of
12 and 8 are as 12 = (1100)2 and 8 = (1000) 2. Now we apply the & operator on these
numbers and get the result as follows
12 = 1 1 0 0
&
8 = 1 0 0 0
Page 260
-----------------------------
1 0 0 0
Thus 12 & 8 = (1000) 2 = 8. Don’t think 12 & 8 as an arithmetic operation. It is just a bit
manipulation or a pattern matching issue. Each bit of first number is matched (compared)
with corresponding bit of the second number. The result of & is 1 if both bits are 1.
Otherwise, it will be 0. The & operator is different from the && operator. The &&
operator operates on two conditions (expressions) and returns true or false while the &
operator works on bits (or bit pattern) and returns a bit (or bit pattern) in 1 or 0.

### Example 1

We want to determine whether in a number a specific bit is 1 or 0. Suppose we want to
determine whether the fourth bit (i.e. 23) of a number is 1 or 0. We will pick the number
whose fourth bit is 1 and the remaining are zero. It is 23 (i.e. 8). Now we will take AND
of the given number with 8 (i.e 1000 in bit pattern.). In bit manipulation, the number is
written in hexadecimal form. In the C language, we put 0x or 0X before the number to
write a number in hexadecimal. Here we will write 8 as 0x8 in our code. Now all the bits
of 8 are zero except the fourth one which is 1. The result of the number being ANDed
with 8 will be non-zero if the fourth bit of the number is 1. As the fourth bit of 8 is also 1,
& of these two bits will result 1. We call the result non-zero just due to the fact that we
are not concerned with the numbers like 1,2,3 or whatsoever. We will write this in the
form of a statement as under

### if (number & 0x8)

instead of if ( (number & ox8) > =1)
The if looks for a true or false. Any non-zero value is considered true and a zero is
considered false. When we do bit-wise AND of two numbers if the result is non-zero (not
1 only, it may be 1 or any other number), this if statement will be true. Otherwise, it will
be false.
By a non-zero value we simply conclude that the fourth bit of the number is set (i.e. 1). A
bit is said to be set in case it is 1 and ‘not set’ if it is 0. This way, we can set any bit
pattern in the power of 2, to determine whether a specific bit of a number is set or not.
For example, to determine bit no. 3 of a number we can AND it with 22 (4).
Following is the code of the example finding out whether the fourth bit of a number is set
(1) or not set (0).
//This program determines whether the fourth bit of a number entered by user is set or not
#include <iostream.h>
main()
{
int number ;
cout << “Please enter a number “ ;
cin >> number ;
if (number & 0x8 ) //8 is written in hexadecimal form
cout << "The fourth bit of the number is set" << endl;
Page 261
else
cout << "The fourth bit of the number is not set" << endl;
}
Sample output of the program.
The fourth bit of the number is set

### OR Operator ( | )

The OR operator, represented by ‘|’ works just like the & operator with the only
difference that it returns 1 if any one of the bits is 1. In other words, it returns 0 only if
both the input bits are 0. The | (bit-wise OR) operator is different from the || (logical OR)
operator. The || operator operates on two conditions (expressions) and returns true or false
while the | operator works on bits (bit pattern) and returns a bit (or bit pattern) in 1 or 0.
The truth table of OR operator is given below.

### Bit1 Bit2 Bit1 | Bit2

1 1 1
1 0 1
0 1 1
0 0 0
We can make it sure that a specific bit in a number should be 1 with the help of | operator.
For this purpose, we take OR of this number with another number whose bit pattern has 1
in that specific bit. Then OR will produce 1 as the bit at that position in second number is
1 and OR gives 1 if any one bit is one. Thus in the output that specific bit will have 1.
Let us consider the following example in which we apply OR operator on two numbers
12 and 8.
12 = 1 1 0 0
|
8 = 1 0 0 0
-----------------------------
1 1 0 0
Hence we get 12 | 8 = 12.
In case, x = 8 | 1, the OR operation will be as under.
8 = 1 0 0 0
|
1 = 0 0 0 1
-------------------------
1 0 0 1
Page 262
Thus x = 8 | 1 = 9.
Don’t take the statement in mathematical or arithmetical terms. Rather consider it from
the perspective of pattern matching.
The & operator is used to check whether a specific bit is set or not while the | operator is
used to set a specific bit.

### Exclusive OR Operator ( ^ )

Exclusive OR operator uses the sign ^ . This operator returns 1 when one input is zero
and the second is 1. It returns 0 if both bits are same i.e. both are either 0 or 1. The truth
table of exclusive OR, also called xor (zor) , is given below.

### Bit1 Bit2 Bit1 ^ Bit2

1 1 0
1 0 1
0 1 1
0 0 0
To understand exclusive OR, let’s work out exclusive OR of 8 and 1.
In the following statement, the pattern matching is shown for 8 ^ 1.
8 = 1 0 0 0

^
1 = 0 0 0 1
-------------------------------
1 0 0 1
This shows that 8 ^ 1 = 9. If we take again exclusive OR of 9 with 1. The result will be 8
again as shown below.
9 = 1 0 0 1

^
1 = 0 0 0 1
----------------------------
1 0 0 0
While taking ^ (exclusive OR) of a number with a second number and then ^ of the
result with the second number, we get the first number again. This is a strength of the ^
operator that is very useful.

### NOT Operator ( ~ )

This is a unary operator. It inverts the bits of the input number, meaning that if a bit of
the input number is 1, the operator will change it to 0 and vice versa. The sign ~ is used
for the NOT operator. Following is the truth table of the NOT operator.
Page 263

### Bit1 ~ Bit1

1 0
0 1
Let’s take NOT of the number 8. This will be as follows
8 = 1 0 0 0
Now ~8 will invert the bits from 1 to 0 and from 0 to 1. Thus ~8 will be
~8 = 0 1 1 1
which is 7.
The bit manipulation operators are very useful. Let’s consider some examples to see the
usefulness of these operators.

### Example (Bit Flags)

The first example relates to operating system. In Windows, you can view the properties
of a file. You can get the option properties by right clicking the mouse on the file name in
any folder structure. You will see a window showing the properties of the file. This will
show the name of the file, the date of creation/modification of the file etc. In the below
part of this window, you will see some boxes with check marks. These include read only
and archive etc. While looking at a check mark, you feel of having a look at a bit. If there
is a check mark, it means 1. Otherwise, it will be 0. So we are looking at bit flags which
will depict the status of the file. If the file is marked read-only, a specific bit is set to 1 in
the operating system. This 1 indicates that the status of the file is read-only.
When we look for directory in UNIX operating system, rwx, rx or rw are seen before the
name of a file. The rwx are actually symbols used for read, write and execute permissions
of the file. These are the attributes of the file.
In operating systems, the attributes of a file are best get as bit fields. The 1 in a bit means
the attribute is set and 0 means the attribute is not set (or cleared).

Let’s see how ^ operator works. Whenever you log on to a system or server or to a web
site like yahoo or hotmail, you enter your user name and then the password. The system
database of the system/server. When you enter the password, the system compares it with
the one earlier stored in its database. If it matches, the system allows you to access the
system. But there may be a problem at this stage from the security perspective. If the
password is stored in the database as it is, then the administrative (or any person having
password. To prevent this and make the password secure, most of the operating systems
keep the password in an encrypted fashion. It codes the passwords to a different bit
pattern before storing it in its database so that no body can read it. Now when a user
earlier stored in the database. Under the first method, on entering the password, the
Page 264
entered. This is not a best way because of two reasons. If there is a method to decrypt a
method is that when you enter a password, it travels through wires to go to somewhere
for comparison. While it is traveling on wire, someone can get it. Another reason to
compare the password in encrypted form is that it is very easy to do encryption but the
decryption process is very difficult. Therefore, to make this process secure and easy, the
password entered is encrypted and compared to the password in the database, which is
The Exclusive OR operator ( ^ ) can be used to encrypt and decrypt the password.
Suppose there are two numbers a and b. We take c = a ^ b. Now if we take ^ of the result

### c with b (i.e. c ^ b), the result will be a. Similarly, if we take Exclusive OR of the result c

with a (c ^ a) , the answer will be b. You can do exercise this phenomenon by taking any
values of a and b. This phenomenon of Exclusive OR can be used to secure a password.
You can take Exclusive OR of the password with a secret number and save it to the
database. Now when it is needed to be compared with entered password, you again take
Exclusive OR of the saved password with the same secret number and get the original
password back. If someone else wants to get the password, it is very difficult for him/her
to get that because the original password will be got by taking Exclusive OR of the saved
password with the same secret number.
Here is another example of Exclusive OR. Sometimes, there are bad sectors in a hard
disk, which bring it to a halt. We cannot access our data from it. This is worst situation.
In large systems like servers, there is a requirement that these should work twenty four
hours a day, seven days a week. In such systems, we cannot take the risk. To avoid this
and meet the requirements, we use a technique which is called RAID. RAID stands for
Redundant Array of Inexpensive Devices. In this technique, we use many disks instead of
one. Suppose we have nine disks. Now when we say write a byte on the disk, The RAID
will write a bit on first disk then second bit on the second disk and so on. Thus 8 bits (one
byte) are written on 8 disks. Now what will be written on the ninth disk? We take
exclusive OR of these 8 bits pair by pair and write the result on the ninth disk. The
benefit of this process that in case one disk stops working, we may place a new disk in its
place. And to write a bit on this disk, we again take Exclusive OR of eight bits on the
other disks and write the result on this disk. This will be the same bit that was written in
the damaged disk.
You can prove it by the doing the following exercise on paper.
Write eight bits, take their Exclusive OR one by one and write it at ninth position. Now
erase any one bit and take Exclusive OR of the remaining eight bits. You will get the
same bit which was erased. Thus it is a useful technique for recovering the lost data
without shutting down the system. We replace the bad disk with a new one while the
system is on. The system using the RAID technique, writes the data to the new disk. This
technique of replacing a disk is known as Hot Plug.
We have read the technique of swapping two numbers. In this method, we use a third
temporary place to swap two numbers. Suppose a and b are to be swapped. We store a in
a temporary place c. Then we store b in a and put the value of c (which has the value of

### Unsigned Integers

The bit manipulations are done with unsigned integers. The most significant bit is used as
a sign bit. If this bit is zero, the number is considered positive. However, if it is 1, the
number will be considered negative. Normally these bit manipulations are done with
unsigned integers. The unsigned integers are declared explicitly by using the word
‘unsigned’ as follow.
unsigned int i, j, k ;
By this declaration the integers i, j and k will be treated as positive numbers only.

### Sample Program

The following program demonstrate the encryption and decryption of a password. The
program takes a password from user, encrypts it by using Exclusive OR ( ^) with a
number. It displays the encrypted password. Then it decrypts the encrypted password
using Exclusive OR ( ^ ) with the same number and we get the original password again.
Following is the code of the program.
//This program demonstrate the encryption by using ^ operator
# include<iostream.h>
main ()
{
char *passptr ;
//now encrypting the password by using ^ with 3
while (*passptr != '\0' )
{
*passptr = (*passptr ^ 3);
++passptr ;
}
//now decrypting the encrypted password by using ^ with 3
Page 266
while (*passptr != '\0' )
{
*passptr = (*passptr ^ 3);
++passptr ;
}
}
The following is a sample output of the program.

### Shift Operators

Shifting the binary numbers is similar to shifting the decimal numbers. Suppose we have
1 in decimal system and want to shift it left in a way that zero is put at the ending place.
Thus 1 becomes 10. Mathematically, it is a multiplication by 10. Now if we shift 10 to
left and place 0 at the last place, we get 100. It is again a multiplication by 10. In pictorial
terms, we can show this as under.
(In decimal system)
The value is 1
Shift Left, The value is 10 (i.e. multiplication by 10)
Shift Left, The value is 100 (i.e. multiplication by 10)
1000 100 10 1
0 0 0 1
0 0 1 0
0 1 0 0
The same thing applies when we do bit shifts. If we shift a bit to the left in the binary
system, it is multiplied by 2. If we do left shift again we are multiplying by 2 again.
Same applies in the other direction. By shifting to the right, we will be dividing by 2 in
the binary system and dividing by 10 in decimal system. In this process, the shifted
digit/bit is discarded. When we do left shift, zeroes are inserted in the right side bits. The
same applies to right shift, as zeros are inserted in the left side bits. But the situation will
be different if we use signed numbers. As we know that in signed numbers the most
significant bit is 1. Now you have to see that what happens while right shifting the signed
number? If zero is inserted at the left most bit, the negative number will become a
positive number. Normally the operating systems or compilers treat it differently.
The following figures show the shift operations.
Shift Left:
(In binary system, bits representation)
The value is 2
8 4 2 1
0 0 1 0
Page 267
Shift Left , The value is 4 (i.e. multiplication by 2)
Shift Left, The value is 8 (i.e. multiplication by 2)
0 1 0 0
1 0 0 0
Shift Right:
(In binary system, bits representation)
The value is 12
Shift Right , The value is 6 (i.e. division by 2)
Shift Right, The value is 3 (i.e. division by 2)
8 4 2 1
1 1 0 0
0 1 1 0
0 0 1 1
We have specific operators for left and right shifts. The left shift operator is << and right
shift operator is >>. These are the same signs as used with cout and cin. But these are
shift operators. We can give a number with these operators to carry out shift operation for
that number of times. The following program demonstrates the left and right shift
operators.
//This program demonstrate the left and right shift
# include <iostream.h>
main()
{
int number, result ;
cout << "Please enter a number: " ;
cin >> number ;
result = number << 1 ;
cout << "The number after left shift is " << result << endl ;
cout << "The number after left shift again is " << (result << 1) << endl ;
cout << "Now applying right shift" << endl ;
result = number >> 1 ;
cout << "The number after right shift is " << result << endl ;
cout << "The number after right shift again is " << (result >> 1) << endl ;
}
Here is the out put of the program.
The number after left shift is 24
The number after left shift again is 48
Now applying right shift
Page 268
The number after right shift is 6
The number after right shift again is 3
In the output, we see that the left shift operator (<<) has multiplied the number by 2 and
the right shift operator (>>) has divided the number by 2. The shift operator is more
efficient than direct multiplication and division.

### Exercises

Write different programs to demonstrate the use of bit manipulation operators.
Write a program which takes two numbers, displays them in binary numbers and then
displays the results of AND, OR and Exclusive OR of these numbers in binary
numbers so that operations can be clearly understood.
Write a program which swaps two numbers without using a temporary third variable.
Write a program, which takes a password from the user, saves it to a file in encrypted
form. Then allow the user to enter the password again and compare it with the stored