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<
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<
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