Bit Manipulation in C
C provides six bitwise operators for bit manipulation.
These operators act on integral operands (char, short, int and
long) represented as a string of binary digits.
Bit Manipulation Bitwise Operators
logical operators:
in C
(unary) bitwise complement: ~
bitwise and: & &=
bitwise or: | |=
bitwise exclusive or: ^ ^=
shift operators:
left shift: << <<=
right shift: >> >>=
ICT106_Prac_Week_6 1 ICT106_Prac_Week_6 2
Examples of application of bitwise
operators on 8 bit representations of
integers x and y
x y ~x x&y x|y x^y
0 0 1 0 0 0 int x, y, result;
0 1 1 0 1 1 x = 15; /* 00001111 */
y = -10; /* 11110110 */
1 0 0 0 1 1 result = x & y;
1 1 0 1 1 0
/* result now has the value decimal 6, i.e.,
00000110 */
ICT106_Prac_Week_6 3 ICT106_Prac_Week_6 4
Expression Representation Value The bitwise AND operator & is often used to
mask off some set of bits, e.g.,
x 00001111 15
x = x & 017; /* N.B. 017 is an octal value */
y 11110110 -10
sets to zero all but the low-order 4 bits of
result = x & y; 00000110 6 x.
result = x | y; 11111111 -1 The bitwise OR operator | is often used to turn
result = x ^ y; 11111001 -7 bits on, e.g., x = x | y;
result = ~(x ^ y); 00000110 6 sets to one in x the bits that are set to one
result = ~x; 11110000 -16 in y.
result = x << 2; 00111100 60
result = x >> 2; 00000011 3
ICT106_Prac_Week_6 5 ICT106_Prac_Week_6 6
1
The bitwise exclusive OR operator ^ sets a one
in each bit position where its operands have
different bits, and zero where they are the same.
The bitwise complement operator ~, also called
the “one’s complement operator”, inverts the bit Structures in C
string it is applied to. The 0s become 1s and the
1s become 0s (Toggle)
The shift operators << and >> perform left and
right shifts of their left operand by the number of
bit positions given by the right operand, which
must be positive.
ICT106_Prac_Week_6 7 ICT106_Prac_Week_6 8
Struct-ure
Structs are like records and can be used The typedef keyword allows to create
to group data elements of different types, name for a type, e.g.
i.e., a struct is (usually) a collection of
mixed type items. typedef unsigned char BYTE;
Two ways to define a structure:
structstruct_name {variables};
BYTE one, bytes[5], *pr;
typedef struct {variables} Type_name;
ICT106_Prac_Week_6 9 ICT106_Prac_Week_6 10
To Declare struct variables
struct Employee { typedef struct { This defines a new data type called 'Employee'.
This definition is for the use of C compiler, it
char surname[4]; char surname[4]; does not allocate any space for the component
char firstInit; char firstInit; variables.
This definition can be used to declare variables
int age; int age; as follows:
float wage; float wage; Struct Employee manager;
struct Employee worker1;
}; } EMPLOYEE; EMPLOYEE manager;
EMPLOYEE worker1;
ICT106_Prac_Week_6 11 ICT106_Prac_Week_6 12
2
Accessing elements in a struct
Initialising a struct is similar to that used The elements (members) of a struct are
for arrays: accessed using the dot notation:
struct employee worker2 = {“John”, ‘B’, 32, worker1.firstInit = 'J';
45800.15}; worker1.age = 22;
Memory allocation for a structure worker1.wage = 30000.00;
‘J’ ‘o’ ‘h’ ‘n’ ‘B’ 32 45800.15 manager.wage = 2* worker1.wage;
Char[0] Char[3]
surname Age Wage
Initial
ICT106_Prac_Week_6 13 ICT106_Prac_Week_6 14
Bit Field
Another method of manipulating bits is to #define TRUE 1
use a bit field; #define FALSE 0
A bit field is constructed with a structure
struct BOOL {
declaration that labels each field and
unsigned int bit : 1;
determines its width;
};
For example, to declare a Boolean data
type
ICT106_Prac_Week_6 15 ICT106_Prac_Week_6 16
Flag Register
This definition creates a new data type struct FLAG {
unsigned int overflow : 1;
BOOL that contains one 1-bit field. unsigned int sign : 1;
unsigned int zero : 1;
unsigned int aux_carry : 1;
struct BOOL flag; unsigned int parity : 1;
unsigned int carry : 1;
flag.bit = TRUE; unsigned int direc : 1;
unsigned int interrupt : 1;
flag.bit = FALSE; };
ICT106_Prac_Week_6 17 ICT106_Prac_Week_6 18
3
Nested Structures
struct names {
A struct can contain or nest another char first[4];
struct; char surname[4];
};
Nested structures are often used to
construct complex data record; struct Employee {
struct names name; // nested struct
For example, we can create a int age;
float wage;
structure called names to represent };
an employee’s name
ICT106_Prac_Week_6 19 ICT106_Prac_Week_6 20
Pointers to Structures
Again, the elements of a struct can be accessed Using pointers is easier to manipulate
using the dot notation:
structures than the arrays;
struct Employee worker1; To overcome the problem of using
strcpy((worker1.name).last, “Bob”); structures as function arguments in some
strcpy((worker1.name).surname, “John”); older C implementations;
worker1.age = 43;
Enable to create dynamic size arrays
The construction is interpreted from left to right
ICT106_Prac_Week_6 21 ICT106_Prac_Week_6 22
/* employee record: demonstrating use of pointer to a structure */ int main() {
#include <stdio.h>
#define LEN 11 // define a constant LEN struct Employee workers[2] = {
{ {“Ewen”, “Villard”},
struct names { char last[LEN]; char surname[LEN]};
23,
struct Employee { 34000.00
struct names name; // nested structure
},
int age;
float wage; { {“Rodney”, “Swillbelly”},
}; 41,
58000.00
}
23 24
ICT106_Prac_Week_6
}; ICT106_Prac_Week_6
4
struct Employee *him; // a pointer to a structure
him = &workers[0]; // assign address to pointer
printf("workers[0].name.surname is %s\n",
workers[0].name.surname); workers[0].name.surname is Villard
printf(“workers[0].age is %d\n”, workers[0].age); workers[0].age is 23
printf(“(*him).age is %d\n”, (*him).age);
(*him).age is 23
printf(“him->age is %d\n”, him->age);
him->age is 23
him++; // point to the next structure
printf("him->name.surname is %s\nhim->wage is him->name.surname is Swillbelly
%.2f\n", him->name.surname, him->wage);
him->wage is 58000.00
return 0;
} ICT106_Prac_Week_6 25 ICT106_Prac_Week_6 26
Linked List
Construction of an employee linked list is shown
Linked lists contain a set of (mostly) below:
similar data structures;
struct Employee {
An item can be added to or removed from
strut Employee *next; // pointer to the next element
a linked list and that the length of linked
strut names name;
lists can be dynamically changed;
int age;
The length of arrays is always fixed and it float wage;
must be defined before use; };
ICT106_Prac_Week_6 27 ICT106_Prac_Week_6 28
int main() { struct Employee *him; // a pointer to a structure
struct Employee workers[2] = {
{ NULL, // pointer to nowhere
him = &workers[0]; // assign address to pointer
{"Ewen", "Villard"},
23, him->next = him+1; // link to the next record
34000.00
}, printf("(*(him->next)).name.surname is %s\n",
{ NULL, // pointer to nowhere (*(him->next)).name.surname);
{"Rodney", "Swillbelly"},
41, him++; // point to the next structure
58000.00
printf("him->name.surname is %s\n,
}
him->name.surname);
};
ICT106_Prac_Week_6 29 ICT106_Prac_Week_6 30
5
/* Book record: demonstrating linked list */
#include <stdio.h>
#include <stdlib.h>
(*(him->next)).name.surname is Swillbelly struct Book {
him->name.surname is Swillbelly struct Book *next; // pointers to next struct in list
int barcode;
float price;
};
struct Employee * struct Employee * NULL int main() {
char [10] char [10]
struct Book *head = NULL; // head of list
char [10] char [10] struct Book *prev, *current;
age age int i=1;
wage wage
ICT106_Prac_Week_6 31 ICT106_Prac_Week_6 32
do { /* create memory block for Book structure */ current = head; // pointer to head of list
current = (struct Book *) malloc(sizeof(struct Book));
while(current!=NULL) {
if(head==NULL) {
head = current; // first structure printf("Book: %d Price: %f\n",
} else { current->barcode, current->price);
prev->next = current; // subsequent structure
}
printf("\nEnter barcode for %d book: ", i); /* pointer to subsequent struct */
scanf("%d%*c", ¤t->barcode); current = current->next;
printf("Enter price for %d book: ", i); }
scanf("%f%*c", ¤t->price);
current->next = NULL; // set the next struct to NULL return 0;
prev = current; // update prev pointer }
i++;
} while (i<5);
ICT106_Prac_Week_6 33 ICT106_Prac_Week_6 34
