CS计算机代考程序代写 Java compiler C Lab 2

C Lab 2

C Lab 3
Masking and Shifting

How to allocate time for the lab presentation:
Review: 10 mins
Realloc: 5 mins
Structs: 5 mins
Memory: 5 mins
Q&A: 10 mins
Release solution when there are 20 mins left in the second week lab session, so that everyone finishes the assignment

Goals
Review
Shifts
Referencing/Dereferencing
free
malloc
structs

General Boolean Algebras
Operate on bit vectors
Operations applied bitwise
All of the properties of Boolean algebra apply

Examples of useful operations:

,

3
01101001
& 01010101
01101001
| 01010101
01101001
^ 01010101

~ 01010101
01010101
| 11110000
11110101

01010101
^ 01010101
00000000

Now, how do we use the boolean operators?
Typically on ”bit vectors” (treat a byte, or multiple bytes) as a bit vector

Bit-Level Operations in C
& (AND), | (OR), ^ (XOR), ~ (NOT)
View arguments as bit vectors, apply operations bitwise
Apply to any “integral” data type
long, int, short, char, unsigned
Examples with char a, b, c;
a = (char) 0x41; // 0x41->0b 0100 0001
b = ~a; // 0b ->0x
a = (char) 0x69; // 0x69->0b 0110 1001
b = (char) 0x55; // 0x55->0b 0101 0101
c = a & b; // 0b ->0x
a = (char) 0x41; // 0x41->0b 0100 0001
b = a; // 0b 0100 0001
c = a ^ b; // 0b ->0x
4

Some bit-twiddling puzzles in Lab 1

Shift Operations
Left shift (x<>n) bit-vector x by n positions
Throw away (drop) extra bits on right
Logical shift (for unsigned values)
Fill with 0s on left
Arithmetic shift (for signed values)
Replicate most significant bit on left
Maintains sign of x
5

Useful operator when working with bit representations
Especially Lab 1
1001

Operators Recap
NOT: ~
This will flip all bits in the operand
AND: &
This will perform a bitwise AND on every pair of bits
OR: |
This will perform a bitwise OR on every pair of bits
XOR: ^
This will perform a bitwise XOR on every pair of bits
SHIFT: <<, >>
This will shift the bits right or left
logical vs. arithmetic

Operators Recap
NOT: !
Evaluates the entire operand, rather than each bit
Produces a 1 if == 0, produces 0 if nonzero
AND: &&
Produces 1 if both operands are nonzero
OR: ||
Produces 1 if either operand is nonzero

Examples
Create 0xFFFFFFFF using only one operator

Limited to constants from 0x00 to 0xFF
Naïve approach:
0xFF + (0xFF << 8) + (0xFF << 16) … Better approach: ~0x00 = 0xFFFFFFFF Examples Replace the leftmost byte of a 32-bit integer with 0xAB Let our integer be x First, we want to create a mask for the lower 24 bits ~(0xFF << 24) will do that using just two operators (x & mask) will zero out the leftmost 8 bits Now, we want to OR in 0xAB to those zeroed-out bits Final result: (x & mask) | (0xAB << 24) Total operators: 5 Shift Operations Left shift (x<>n)
Logical shift (for unsigned values)
Fill with 0s on left
Arithmetic shift (for signed values)
Replicate most significant bit on left
Notes:
Shifts by n<0 or nw (w is bit width of x) are undefined In C: behavior of >> is determined by compiler
In gcc / C lang, depends on data type of x (signed/unsigned)
In Java: logical shift is >>> and arithmetic shift is >>
10
x 0010 0010
x<<3 0001 0000 logical: x>>2 0000 1000
arithmetic: x>>2 0000 1000

x 1010 0010
x<<3 0001 0000 logical: x>>2 0010 1000
arithmetic: x>>2 1110 1000

Extract the 2nd most significant byte of an int:
First shift, then mask: (x>>16) & 0xFF

Or first mask, then shift: (x & 0xFF0000)>>16
11
0xFF 00000000 00000000 00000000 11111111

(x>>16) & 0xFF 00000000 00000000 00000000 00000010

x>>16 00000000 00000000 00000001 00000010

x 00000001 00000010 00000011 00000100

x & 0xFF0000 00000000 00000010 00000000 00000000

(x&0xFF0000)>>16 00000000 00000000 00000000 00000010

0xFF0000 00000000 11111111 00000000 00000000

x 00000001 00000010 00000011 00000100

Using Shifts and Masks
Extract the sign bit of a signed int:
First shift, then mask: (x>>31) & 0x1
Assuming arithmetic shift here, but this works in either case
Need mask to clear 1s possibly shifted in
12
x 00000001 00000010 00000011 00000100
x>>31 00000000 00000000 00000000 00000000
0x1 00000000 00000000 00000000 00000001
(x>>31) & 0x1 00000000 00000000 00000000 00000000

x 10000001 00000010 00000011 00000100
x>>31 11111111 11111111 11111111 11111111
0x1 00000000 00000000 00000000 00000001
(x>>31) & 0x1 00000000 00000000 00000000 00000001

0
0
1
1

Using Shifts and Masks
Conditionals as Boolean expressions
For int x, what does (x<<31)>>31 do?

Can use in place of conditional:
In C: if(x) {a=y;} else {a=z;} equivalent to a=x?y:z;
a=(((x<<31)>>31)&y) |(((!x<<31)>>31)&z);
13
x=!!123 00000000 00000000 00000000 00000001
x<<31 10000000 00000000 00000000 00000000 (x<<31)>>31 11111111 11111111 11111111 11111111
!x 00000000 00000000 00000000 00000000
!x<<31 00000000 00000000 00000000 00000000 (!x<<31)>>31 00000000 00000000 00000000 00000000

Use !! to force to 0/1