CMPSC 311 – Introduction to Systems Programming
Bit/Byte Operations
Professors
Sencun Zhu and (Slides are mostly by Professor Patrick McDaniel
Copyright By PowCoder代写 加微信 powcoder
and Professor Abutalib Aghayev)
CMPSC 311 – Introduction to Systems Programming
Number Systems
• All base-X systems have the following characteristic:
Base-10 (decimal)
• Digits: 0,1,2,3,4,5,6,7,8,9
Base-2(binary)
• Digits: 0,1
• Place values: 2
• Example: 1011 = 1×1+1×2+0x4+1×8
Base-16 (hexadecimal)
• Digits: 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F • Place values: 160 , 161, 162, …
• Example: 0xAFC = Cx1+Fx16+Ax256
• Place values: 10
• Example: 123 = 3×1+2×10+1×100
CMPSC 311 – Introduction to Systems Programming
Converting Decimal to Binary
• while n != 0:
• next binary digit (from right to left) = n % 2 • n = n /2
235 (base-10) = 11101011 (base-2)
CMPSC 311 – Introduction to Systems Programming
Converting Decimal and Binary to Hex
• Converting decimal to hexadecimal • while n != 0:
• next hex digit (from right to left) = n % 16 • n = n / 16
235 (base-10) = EB (base-16)
• Converting binary to hexadecimal
• group binary digits to into groups of 4 bits (nibbles) starting from right • Convert each nibble to hexadecimal digit
235 (base-10) = 11101011 (base-2) = 1110 1011 = EB
• Be familiar with hex notation: 0xDEADBEEF has 8 nibbles, 4 bytes (or octets) • Hexadecimal to binary: just convert each nibble to binary
CMPSC 311 – Introduction to Systems Programming
Conversion Summary
• Binary to decimal
• sum of binary digits times powers of 2
• Hexadecimal to decimal
• sum of hex digits times power of 16
• Decimal to binary • division method
• Decimal to hex
• division method
• or, convert to binary and use binary to hex method below
• Binary to hex
• group binary digits to nibbles, convert nibbles to hex digits
• Hex to binary
• convert each hex digit to binary
CMPSC 311 – Introduction to Systems Programming
Byte Ordering Example
• How should bytes within a multi-byte word be ordered in memory? • Big Endian: Least significant byte has highest address (SPARC)
• Little Endian: Least significant byte has lowest address (x86)
• Example: int x = 305419896
• Variable x has 4-byte representation 0x12345678 • Address given by &x is 0x100
Big Endian Little Endian
0x100 0x101 0x102 0x103
0x100 0x101 0x102 0x103
CMPSC 311 – Introduction to Systems Programming
Examining Data Representations
• Code to find endianness of the architecture • Casting pointer to uint8_t * creates byte array
#include <
Result (Linux on x86):
int main(void) {
int a = 305419896;
#include <
(uint8_t *start, int
show_bytes
(“a lives at address %p
printf directives
%p Print pointer
%x Print hexadecimal
show_bytes
((uint8_t *)&a,
a lives at address 0x7ffebf803174
0x7ffebf803174 0x78 0x7ffebf803175 0x56 0x7ffebf803176 0x34 0x7ffebf803177 0x12
CMPSC 311 - Introduction to Systems Programming
Boolean Algebra
• Developed by in 19th Century
• Algebraic representation of logic that based on “True” (as 1) and “False” (as 0)
A&B = 1 when both A=1 and B=1
~A = 1 when A=0
A|B = 1 when either A=1 or B=1
Exclusive-Or (Xor)
A^B = 1 when either A=1 or B=1, but not both
CMPSC 311 - Introduction to Systems Programming
Bit-Level Operations in C
• Operations &, |, ~, ^ Available in C
• Apply to any “integral” data type • long, int, short, char, unsigned
• View arguments as bit vectors • Argumentsappliedbit-wise
• Examples (Char data type) • ~0x41 ➙ 0xBE
• ~010000012 ➙ 101111102 • ~0x00 ➙ 0xFF
• ~000000002 ➙ 111111112 • 0x69 & 0x55 ➙ 0x41
• 011010012 & 010101012 ➙ 010000012 • 0x69 | 0x55 ➙ 0x7D
• 011010012 | 010101012 ➙ 011111012
CMPSC 311 - Introduction to Systems Programming
Contrast: Logic Operations in C
• Contrast to Logical Operators (&&, ||, !)
• View 0 as “False”
• Anything nonzero as “True”
• Always return 0 or 1
• Earlytermination
CMPSC 311 - Introduction to Systems Programming
Representing & Manipulating Sets
• Representation
• Width w bit vector represents subsets of {0, ..., w–1} for set “A”
• aj=1 if j∈A
{ 0, 2, 4, 6 }
{ 0, 3, 5, 6 }
Operations On Sets:
& Intersection |Union
^ Symmetric difference ~ Complement
01000001 { 0, 6 }
01111101 {0,2,3,4,5,6} 00111100 { 2, 3, 4, 5 } 10101010 { 1, 3, 5, 7 }
CMPSC 311 - Introduction to Systems Programming
Representing Signed Numbers
One’s complement
Two’s complement
7 = 2n-1 – 1
• Computing one’s complement negative representation: • Complement the positive number
• Computing two’s complement negative representation: • Complement the positive number and add 1
• Most architectures use two’s complement
• Given n-bit signed integer:
• Positive range: 0 – 2n-1 -1
• Negative range: -2n-1
-8 = -2n-1
[-32768,32767]
unsigned short int
[-214748648, 2147483647]
[0, 65535]
CMPSC 311 - Introduction to Systems Programming
unsigned int
[0, 4294967295]
[-2147483648,
long int 4 8 %ld
Beware of integer overflows
• Spot the bug in the following:
for (uint32_t n = 10; n >=0; –n) {
printf(“do I ever terminate?\n”);
• What does the following print?
int x = 0xffffffff;
printf(“%d\n”, x);
CMPSC 311 – Introduction to Systems Programming
Shift Operations
• A shift operator (<< or >>) moves bits to the right or left, throwing away bits and adding bits as necessary
X = X << 3;
(throw away)
Read as this: shift the bits of the value 3 places to the left
(“new” bits)
CMPSC 311 - Introduction to Systems Programming
Putting it all together
• Suppose you want to place multiple values in the same 32-bit integer • Value a in least significant byte
• Value b in 2nd byte
• Value c in 3rd byte
• Value d in 4th byte
Bits Values
CMPSC 311 - Introduction to Systems Programming
Using bit operations ...
uint32_t pack_bytes(uint32_t a, uint32_t b, uint32_t c, uint32_t d) {
// Setup some local values
uint32_t retval = 0x0, tempa, tempb, tempc, tempd;
tempa = a&0xff; // Make sure you are only getting the bottom 8 bits tempb = (b&0xff) << 8; // Shift value to the second byte
tempc = (c&0xff) << 16; // Shift value to the third byte
tempd = (d&0xff) << 24; // Shift value to the top byte
retval = tempa|tempb|tempc|tempd; // Now combine all of the values
// Print out all of the values
printf("A: 0x%08x\n", tempa); printf("B: 0x%08x\n", tempb); printf("C: 0x%08x\n", tempc); printf("D: 0x%08x\n", tempd);
// Return the computed value
return retval;
A: 0x00000011
B: 0x00002200
C: 0x00330000
D: 0x44000000
Packed bytes : 0x44332211
printf("Packed bytes : 0x%08x\n", pack_bytes(0x111, 0x222, 0x333, 0x444));
CMPSC 311 - Introduction to Systems Programming
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com