Bit Manipulation
Introduction to Bits:
Binary and Bits: At their fundamental level, computers use a numeral system whose
digits consist of only two possible values. These digits can either be zeros or ones. This
system is known as Binary. It may seem limiting at first, but any number can be
represented in Binary. In most cases, you simply need more zeros and ones. Binary
digits have been given the nickname of Bits : a term built from combining the two words
“Binary” and “digITS“.
for example:
Decimal Value Binary Value
2 10
3 11
Decimals: Having ten fingers (or digits) on our hands, humans have made decimal the
most popular numeral system in use by modern civilizations. Decimal consists of ten
digits that we are all familiar with : 0,1,2,3,4,5,6,7,8 and 9.
Bytes: A Byte consists of 8 bits and can represent any of 256 different values. Bytes
were originally used as a convenient and Human-friendly way to represent text
characters rather than having to use Binary.
Bitwise Operators and Operations:
In arithmetic-logic unit (which is within the CPU), mathematical operations like: addition,
subtraction, multiplication and division are done in bit-level. To perform bit-level
operations in C programming, bitwise operators are used. Following are some Bitwise
operators available:
& Bitwise AND
| Bitwise OR
^ Bitwise XOR
~ Bitwise complement
<< Shift left
>> Shift right
Following is a truth table for AND, OR and XOR:
1. Bitwise AND: The output of bitwise AND is 1 if the corresponding bits of two operands
is 1. If either bit of an operand is 0, the result of corresponding bit is evaluated to 0. Let
us suppose the bitwise AND operation of two integers 12 and 25.
12 = 00001100 (In Binary)
25 = 00011001 (In Binary)
Bit Operation of 12 and 25
00001100 & 00011001 = 00001000 = 8 (In decimal)
2. Bitwise OR: The output of bitwise OR is 1 if at least one corresponding bit of two
operands is 1. In C Programming, bitwise OR operator is denoted by |.
12 = 00001100 (In Binary)
25 = 00011001 (In Binary)
Bitwise OR Operation of 12 and 25
00001100 | 00011001 = 00011101 = 29 (In decimal)
3. Bitwise XOR: The result of bitwise XOR operator is 1 if the corresponding bits of two
operands are opposite. It is denoted by ^.
12 = 00001100 (In Binary)
25 = 00011001 (In Binary)
Bitwise XOR Operation of 12 and 25
00001100 ^ 00011001 = 00010101 = 21 (In decimal)
4. Bitwise complement: Bitwise compliment operator is an unary operator (works on
only one operand). It changes 1 to 0 and 0 to 1. It is denoted by ~.
35 = 00100011 (In Binary)
Bitwise complement Operation of 35
~ 00100011 = 11011100 = 220 (In decimal)
5. There are two shift operators in C programming:
Right shift operator
Left shift operator.
Right Shift Operator
Right shift operator shifts all bits towards right by certain number of specified bits. It is
denoted by >>.
212 = 11010100 (In binary)
212>>2 = 00110101 (In binary) [Right shift by two bits]
212>>7 = 00000001 (In binary)
212>>8 = 00000000
212>>0 = 11010100 (No Shift)
Left Shift Operator
Left shift operator shifts all bits towards left by certain number of specified bits. It is
denoted by <<.
212 = 11010100 (In binary)
212<<1 = 110101000 (In binary) [Left shift by one bit]
212<<0 =11010100 (Shift by 0)
212<<4 = 110101000000 (In binary) =3392(In decimal)
Bit Masking:
Literary meaning of Mask means to hide, and in programming it does the same thing. In
programming masking is used at bit level. means mostly data is used in terms of bytes
like char holds 1 byte, int hold 2 bytes. 1 byte = 8 bits.
So masking is used at bit level. say we have 8 LED connected through some circuit.
now to control 8 LED ON/OFF we will use bit level programming, say initially all LEDS
were ON, now I want to put OFF first 4 LED, so lets C how this works in C
programming.
Say we have variable LED = 0b11111111 ——-> ALL LED ON
now to turn OFF first 4 LED we will mask 4 initial bits. Here bitwise AND operation will
help us, as 0 AND 1 = 0, 1 AND 1 = 1, so lets say we use this
LED = LED & 0b00001111 ;
LED = 0b00001111 (output) now our result is achieved, first four LED get turned OFF
Similarly we can use XOR to toggle these LED means if it ON, make it OFF, and vice a
versa.
Lets see how it toggles, Lets say I have LED = 0b01010101
now XOR functions 0 XOR 1 = 0, 1 XOR 1 = 0, 0 XOR 0 = 0, so here we use LED XOR
with all 1’s
It should be 0 XOR 1 = 1
LED = LED XOR 0b11111111 (Remember LED new values)
LED = 0b10101010
So why we need masking, this is useful in electronics, image processing, data
processing where we need bit manipulation, like in checksums. etc
Masking is also used in image inversion, where you can convert black pixels to white
and vice - a - versa.
Applications of bitwise operators:
The low-level use case for the bitwise operators is to perform base 2 math. There is the
well known trick to test if a number is a power of 2:
if ((x & (x - 1)) == 0) {
printf("%d is a power of 2\n", x);
But, it can also serve a higher level function: set manipulation. You can think if a
collection of bits as a set. To explain, let each bit in a byte to represent 8 distinct items,
say the planets in our solar system (Pluto is no longer considered a planet, so 8 is
enough!):
#define Mercury (1 << 0)
#define Venus (1 << 1)
#define Earth (1 << 2)
#define Mars (1 << 3)
#define Jupiter (1 << 4)
#define Saturn (1 << 5)
#define Uranus (1 << 6)
#define Neptune (1 << 7)
Then, we can form a collection of planets (a subset) like using |:
unsigned char Giants = (Jupiter|Saturn|Uranus|Neptune);
unsigned char Visited = (Venus|Earth|Mars);
unsigned char BeyondTheBelt = (Jupiter|Saturn|Uranus|Neptune);
unsigned char All = (Mercury|Venus|Earth|Mars|Jupiter|Saturn|Uranus|Neptune);
Now, you can use a & to test if two sets have an intersection:
if (Visited & Giants) {
puts("we might be giants");
}
The ^ operation is often used to see what is different between two sets (the union of the
sets minus their intersection):
if (Giants ^ BeyondTheBelt) {
puts("there are non-giants out there");
}
So, think of | as union, & as intersection, and ^ as union minus the intersection.
Once you buy into the idea of bits representing a set, then the bitwise operations are
naturally there to help manipulate those sets.
===========================================
One application of bitwise ANDs is checking if a single bit is set in a byte. This is useful
in networked communication, where protocol headers attempt to pack as much
information into the smallest area as is possible in an effort to reduce overhead.
For example, the IPv4 header utilizes the first 3 bits of the 6th byte to tell whether the
given IP packet can be fragmented, and if so whether to expect more fragments of the
given packet to follow. If these fields were the size of ints (1 byte) instead, each IP
packet would be 21 bits larger than necessary. This translates to a huge amount of
unnecessary data through the internet every day.
To retrieve these 3 bits, a bitwise AND could be used along side a bit mask to
determine if they are set.
char mymask = 0x80;
if(mymask & (ipheader + 48) == mymask)
//the second bit of the 6th byte of the ip header is set
Mapping with Bits:
Suppose your C program contains a number of TRUE/FALSE variables grouped in a
structure called status, as follows −
struct {
unsigned int widthValidated;
unsigned int heightValidated;
} status;
This structure requires 8 bytes of memory space but in actual, we are going to store
either 0 or 1 in each of the variables. The C programming language offers a better way
to utilize the memory space in such situations.
If you are using such variables inside a structure then you can define the width of a
variable which tells the C compiler that you are going to use only those number of
bytes. For example, the above structure can be re-written as follows −
struct {
unsigned int widthValidated : 1;
unsigned int heightValidated : 1;
} status;
The above structure requires 4 bytes of memory space for status variable, but only 2
bits will be used to store the values.
If you will use up to 32 variables each one with a width of 1 bit, then also the status
structure will use 4 bytes. However as soon as you have 33 variables, it will allocate
the next slot of the memory and it will start using 8 bytes. Let us check the following
example to understand the concept −
Live Demo
#include <stdio.h>
#include <string.h>
/* define simple structure */
struct {
unsigned int widthValidated;
unsigned int heightValidated;
} status1;
/* define a structure with bit fields */
struct {
unsigned int widthValidated : 1;
unsigned int heightValidated : 1;
} status2;
int main( ) {
printf( "Memory size occupied by status1 : %d\n", sizeof(status1));
printf( "Memory size occupied by status2 : %d\n", sizeof(status2));
return 0;
}
When the above code is compiled and executed, it produces the following result −
Memory size occupied by status1 : 8
Memory size occupied by status2 : 4
Bit Field Declaration
The declaration of a bit-field has the following form inside a structure −
struct {
type [member_name] : width ;
};
The following describes the variable elements of a bit field −
1. type - An integer type that determines how a bit-field's value is interpreted. The type
may be int, signed int, or unsigned int.
2. member_name - The name of the bit-field.
3. width - The number of bits in the bit-field. The width must be less than or equal to the
bit width of the specified type.
The variables defined with a predefined width are called bit fields. A bit field can hold
more than a single bit; for example, if you need a variable to store a value from 0 to 7,
then you can define a bit field with a width of 3 bits as follows −
struct {
unsigned int age : 3;
} Age;
The above structure definition instructs the C compiler that the age variable is going to
use only 3 bits to store the value. If you try to use more than 3 bits, then it will not allow
you to do so. Let us try the following example −
Live Demo
#include <stdio.h>
#include <string.h>
struct {
unsigned int age : 3;
} Age;
int main( ) {
[Link] = 4;
printf( "Sizeof( Age ) : %d\n", sizeof(Age) );
printf( "[Link] : %d\n", [Link] );
[Link] = 7;
printf( "[Link] : %d\n", [Link] );
[Link] = 8;
printf( "[Link] : %d\n", [Link] );
return 0;
When the above code is compiled it will compile with a warning and when executed, it
produces the following result −
Sizeof( Age ) : 4
[Link] : 4
[Link] : 7
[Link] : 0