Transcript CS204 Advanced Programming

Bit Operations
Horton pp. 70 - 76
Why we need to work with bits
Sometimes one bit is enough to store your data: say the gender of the
student (e.g. 0 for men, 1 for women). We don’t have a 1-bit variable
type in C++, so for gender, you will have to use a unsigned char or
char type variable.
But if you need say 8 such 1-bit variables, say to record if the student were
present in the times when attendance was taken, then you can actually
combine all into one char variable.
class student {
…
private:
unsigned char attendance;
//now I can fit 8 bits into this, we will see how
}
In C++, there is special container class, called bitset, that is designed to store bits.
But we will not see and use it. And you are not allowed to use it in this course.
Packing bits
“Packing” 8 1-bit variables into 1 char variable is easy.
Say you know that the student were present in the first 3 class and not in the last 5.
The variable attendance can be set as:
unsigned char attendance = 7;
0
0
0
0
0
1
1
1
where the lest significant 3 bits represent the first 3 attendances (just a choice, it
could be the other way around as well).
But in addition to being able to set a variable’s value, we need to be able to handle
each bit separately, for which we need bit operators.
Hexadecimal literals and output
In C++ a hexadecimal literal (number) is represented by preceeding 0x before the
literal.
E.g. 0xb4a2
// equivalent to 11x163 + 4x162 + 10x16 + 2 = 46242 (decimal)
char ch = 0x7c;
// ch contains 124 (7x16+ 12)
When you want to display a numeric value in hexadecimal, use hex in cout before the
value to be displayed.
–This affects all future integer outputs to be displayed in hexadecimal, so if you want to
switch back to decimal, use dec later.
short nums = -200;
cout << "hexadecimal: " << hex << nums << "
decimal: " << dec <<
nums << endl;
Output: hexadecimal: ff38 decimal: -200
unsigned int numi = 0xfd04e0e4;
cout << "hexadecimal: " << hex << numi << "
decimal: " << dec << numi << endl;
Output: hexadecimal: fd04e0e4 decimal: 4244955364
Bit Operators
&
|
^
~
<<
>>
Bitwise and
Bitwise or
Bitwise exclusive or
Complement (unary operator, takes only one operand)
shift left
shift right
Do not confuse
&& with &
|| with |
Bitwise Operations: AND
Take the AND of the two numbers, bit by bit.
char x,y,z;
x = 0xd5;
y = 0x6c;
z = x&y;
x
a
b
a &b
0
0
0
0
1
0
1
0
0
1
1
1
1
1
0
1
0
1
0
1
y
0
1
1
0
1
1
0
0
z
0
1
0
0
0
1
0
0
Bitwise AND
unsigned char
c1, c2, c3;
c1 = 0x45;
c2 = 0x71;
c3 = c1&c2;
c1 : 0100 0101
c2 : 0111 0001
c3 : 0100 0001
(=0x41 = 4x16+1 = 65 10)
Bitwise OR
Take the OR of the two numbers, bit by bit.
unsigned char
c1, c2, c3;
c1 = 0x45;
c2 = 0x71;
c3 = c1 | c2;
c1 : 0100 0101
c2 : 0111 0001
c3 : 0111 0101
(=0x75 = 7x16+5 = 11710 )
a
b
a |b
0
0
0
0
1
1
1
0
1
1
1
1
Bitwise XOR
Take the Exclusive OR of the two numbers, bit by bit.
unsigned char
c1, c2, c3;
c1 = 0x45;
c2 = 0x71;
c3 = c1 ^ c2;
c1 : 0100 0101
c2 : 0111 0001
c3 : 0011 0100
(=0x34 = 3x16+4 = 5210 )
a
b
a^b
0
0
0
0
1
1
1
0
1
1
1
0
Bitwise Complement
Complement operation (~) converts bits with value 0 to 1 and bits with value
1 to 0.
unsigned char b1 = 0xc1;
unsigned char b4 = 0x08;
b4 = ~b1;
a
~a
0
1
1
0
// 1100 0001
// 0000 1000
// 0011 1110
What do these two statements do?
char x = 0xA5;
if ( x & 0x08 )
//what does this mean?
x = x | 0x02;
//what happened to x?
These are two of the most important bit operations! We will see more later,
but basically you can access a particular bit and you can set a particular
bit with these two operations.
Logic Operators versus Bitwise Logic Ops.
The operators && , || and ! are not bitwise logic operators!
– The result of ! , && and || operations is an integral data type with the
value 0 (every bit is a zero) or 1 (Least Significant bit is 1, all the others are 0).
Shift Operators
Shift operators move bits left or right, discarding bits from one side and filling
the other side with 0s.
<<
>>
means shift left
means shift right
Do not confuse with stream operators
how many times
it is shifted
Bit operations: left shift
Suppose we want to shift the bits of a number N, k bits to the left
– denoted
N << k
• drop leftmost k bits
• append k zeros to the right
Ex:
y = x << 1;
x
1
1
0
1
0
1
0
1
y
1
0
1
0
1
0
1
0
Another example:
unsigned char c2 = 0x9C;
c = c2 << 2
//10011100
//01110000
Bit Shifting as Multiplication
Shift left by one position means multiplication by 2 (provided that the result
is in the range)
0 0 0 1 0 0 1 1 = 19
1 1 1 1 1 1 0 1 = -3
0 0 1 0 0 1 1 0 = 38
1 1 1 1 1 0 1 0 = -6
- Works as multiplication for both unsigned & 2’s complement numbers
- May overflow.
– What is the effect of shifting a number left by 3?
Bit operations: right shift
As opposed to left shift, the right shift works differently for signed and
unsigned numbers.
Suppose we want to shift N by k bits to the right (denoted N >> k):
– For unsigned numbers (i.e. unsigned char, unsigned int, etc.):
• drop rightmost k bits
• append k zeros to the left
– For signed numbers (i.e. char, int, etc.):
• drop the rightmost k bits
• append the sign bit k times to the left
right shift operator:examples
Signed (all your variables are signed unless you specify “unsigned” specifically):
– positives:
char c = 8;
c = c >> 2
//0000 1000
//0000 0010 = 210
– negatives:
char c = - 8;
c = c >> 2
//1111 1000 in 2s comp.
//1111 1110 which is -210
– Called arithmetic shift
Unsigned:
unsigned char d = 0xf8;
d = d >> 2
– Called logical shift
//1111 1000 (24810)
//0011 1110 which is 6210
Bit Shifting as Division: summary
Logical shift right for one bit divides by 2 for unsigned:
0 1 1 1 =7
1 0 0 0 =8
0 0 1 1 =3
0 1 0 0 =4
Always rounds down!
Arithmetic shift right for one bit divides by 2 for signed numbers
0 1 1 1 =7
1 0 0 1 = -7
0 0 1 1 =3
1 1 0 0 = -4
Always rounds down!
CAUTION: Regular division of negative integers
rounds down magnitude-wise. E.g. -7/2 is -3
Bit Shifting as Multiplication & Division
Why useful?
– Simpler, thus faster, than general multiplication & division
Can shift multiple positions at once:
– Multiplies or divides by corresponding power of 2.
– a << 5
– a >> 5
(multiply by 25)
(divide by 25)
Remember, when you need to use only positive numbers or you need
to manipulate bits, use unsigned numbers.
Self-Quiz
What are the resulting values of x,y and z?
char x,y,z;
x
x
y
z
=
=
=
=
0x33;
(x << 3) | 0x0F;
(x >> 1) & 0x0F;
x && y;
Example for setting, testing, and clearing
the bits of bytes
const char IO_ERROR = 0x01; //LSB (right-most bit) is 1, others are 0
const char CHANNEL_DOWN = 0x10;
char flags = 0;
//if ever CHANNEL_DOWN event happens, set its corresponding bit in the flags variable
flags = flags | CHANNEL_DOWN;
...
// set the 5th bit
This is also called masking
//to check what errors may have happened...
if ((flags & IO_ERROR ) != 0)
// check the 1st bit
cout << "I/O error flag is set";
else if ((flags & CHANNEL_DOWN) != 0)
// check the 5th bit
cout << "Channel down error flag is set";
...
flags = flags & ~IO_ERROR;
// clear the ERROR flag
Example 2: Attendance
unsigned char attendance = 0x00;
//let the LSB be for quiz 1, the next one is for quiz 2, . . .
//0 means unattended, 1 means attended
//there are total of 8 quizzes; initally all unattended
unsigned char mask=0x01;
//Draft code showing how attendance array may be filled
//if attended to quiz 1
attendance = attendance | mask;
//if attended quiz 3
mask = mask << 2; // mask becomes 0000 0100
attendance = attendance | mask;
...
//to display attendance information
mask=0x01;
for (int i=1; i <= 8; i++)
{
if (attendance & mask)
cout << "Student attended quiz number " << i << endl;
else
cout << "Student missed quiz number " << i << endl;
mask = mask << 1;
}
22