Binary Data Representation

Lesson 8

1

Binary System Origins

1. Binary system first documented by Leibniz in 1703.

2

Binary System Origins

• Binary system first documented by Leibniz in 1703.
• For example: 01101110 = 0x6E

3

Binary System Origins

• Binary system first documented by Leibniz in 1703.
• For example: 01101110 = 0x6E
• MSB, LSB and nibble (or nybble).

4

The Big Questions

• How do we represent negative numbers?
• How do we define arithmetic? (+, -, *, /)
• How do we do all this in a way convenient to implement in hardware?

5

Sign-Magnitude — Ուղիղ Կոդ

• Records the number's sign and magnitude: 01000000 is 2⁶ = 64
• MSB is 0 for positive numbers and 1 for negative numbers. Other bits as usual.
• For instance, 01000000 is 2⁶ = 64 and 11000000 is: - 2⁶ = - 64.
• Good: easy to understand for humans, but has problems:
• Bad: Two zeros: -0 and +0. (Why is this bad?)
• Superfluity at a fundamental level.
• Bad: Requires special logic (sign detection) for all arithmetic operations.
• Any special treatment is usually bad in computation. Think of if statements.
• The hardware more difficult to design, get correct and more expensive to build.

6

One’s Complement — Հակադարձ Կոդ

• Negative of a number X defined by flipping the bits: -X = ~X
• For example: 01001001 becomes

10110110

• Leftmost bit interpreted as the sign of the number.
• Note that this means that in an N-bit system:

​

-X=(2^N-1)-X

2⁸ - 1 = 100000000 - 1 = 11111111

X = 01001001: 11111111 - X =

-X = 10110110

7

One’s Complement — Հակադարձ Կոդ

• Good: one procedure exists for addition of positive and negative numbers:
1. Simply add the numbers.
2. Carry the carry back to the LSB and add it in. For example: 103 - 97
3. Add 103 = 01100111 to - 97 = - (01100001) = 10011110
4. Result is 100000101 (9 bits)
5. Carry and add the MSB to LSB: 00000101 + 1 = 00000110 = 6
6. Which means: 103 - 97 = 6, just as expected.
• Good: Reduces subtraction to addition.
• What’s bad here?
• Still has two zeros.
• Still requires special logic (sign-detection) for * and /.

8

Two’s Complement — Լրացուցիչ Կոդ

• Negative of a number X in an N-bit system defined as 2^N-X
• First proposed by J. von Neumann in his famous EDVAC paper.
• Recalling one’s complement, note that this means: -X = ~X + 1

​

One’s:-X=2^N-1-X

Two’s:-X=2^N -X

9

Two’s Complement — Լրացուցիչ Կոդ

• Negative of a number X in an N-bit system defined as 2^N-X
• First proposed by J. von Neumann in his famous EDVAC paper.
• Recalling one’s complement, note that this means: -X = ~X + 1

10

Isomorphic to�Cyclic group

ℤ / 2^N

Two’s Complement essentially defines modular arithmetic with n = 2^N

Two’s Complement — Լրացուցիչ Կոդ

• Negative of a number X in an N-bit system defined as 2^N-X
• First proposed by J. von Neumann in his famous EDVAC paper.
• Recalling one’s complement, note that this means: -X = ~X + 1
• Just like one’s complement, makes addition and subtraction simple:

11

Example: x, y > 0

​

x + (-y) = x + (2^N - y)

= 2^N + (x - y)

= 2^N - (y - x)

= -(y - x)

= x - y

Example: x > 0

​

-(-x) = 2^N - (-x)

= 2^N - (2^N - x)

= x

​

Two’s Complement — Լրացուցիչ Կոդ

• Good: only one zero (“-0” = ~00000000 + 1 = 100000000 = 0 mod 2^N).
• Good: in addition to it and unlike one’s complement, multiplication is also simple:
• (-x)y = (2^N-x)y = 2^Ny - (xy)
• Again, 2^Ny = 0 mod 2^N (being represented by Nth and the more significant bits).
• Those are dropped, so 2^Ny - (xy) = -(xy).
• Good: type promotion is implemented easily with sign extension.
• Arithmetic operators in C++ do not accept types smaller than int.
• Simply repeat the sign bit on the left. (Works for negative numbers also.)
• A single instruction on some processors.
• Note that 10000000 (value -128) has no inverse.
• Inverting it and adding 1 gives 01111111 + 1 = 10000000, same number.
• This makes allowed values in two’s complement asymmetrical: -2^N-1 to 2^N-1-1

12

Comparing All Three

13

Sign-Magnitude One’s Complement Two’s Complement

Comparing All Three

14

Why does this work “best”

Why did this “win”?

Sign-Magnitude One’s Complement Two’s Complement

Because two’s complement has the best underlying mathematical / algebraic structure.

Fundamental Algebraic Structures

15

Monoid

• Single associative binary operation
• Identity element

Fundamental Algebraic Structures

16

Monoid

• Single associative binary operation
• Identity element

(a + b)c = ac + bc�c(a + b) = ca + cb

​

​

�

Fundamental Algebraic Structures

17

Monoid

• Single associative binary operation
• Identity element

a + (-a) = 0

​

​

�

(a + b)c = ac + bc�c(a + b) = ca + cb

​

​

�

Fundamental Algebraic Structures

18

Monoid

• Single associative binary operation
• Identity element

a + (-a) = 0

​

​

�

ab = ba

​

​

�

(a + b)c = ac + bc�c(a + b) = ca + cb

​

​

�

Fundamental Algebraic Structures

19

Monoid

• Single associative binary operation
• Identity element

a + (-a) = 0

​

​

�

ab = ba

​

​

�

ab = 0 ⇒ a or b = 0

​

​

�

(a + b)c = ac + bc�c(a + b) = ca + cb

​

​

�

Fundamental Algebraic Structures

20

Monoid

• Single associative binary operation
• Identity element

a + (-a) = 0

​

​

�

ab = ba

​

​

�

ab = 0 ⇒ a or b = 0

​

​

�

a * 1/a = 1

​

​

�

Fields have the “usual” numerical properties

by which we make sense of the world.

(a + b)c = ac + bc�c(a + b) = ca + cb

​

​

�

Bigger Universe of Algebraic Structures

21

XOR Swap

22

Regular (with temp)

Why does this work?

Which is faster?

XOR Swap Algebra

23

L1 follows from L4 because:

e = (ab)² = abab

Multiply both sides by a, b:

ab = aababb

ab = ba

XOR Swap

1. Won’t optimize swap in practice.

24

XOR Swap

• Won’t optimize swap in practice.
• Might even make swap slower. Why?

25

XOR Swap

• Won’t optimize swap in practice.
• Might even make swap slower. Why? What’s the fundamental difference?

26

XOR Swap

• Won’t optimize swap in practice.
• Might even make swap slower. Why? What’s the fundamental difference?
• Because data dependency is very bad for pipelines.

27

XOR Swap

• Won’t optimize swap in practice.
• Might even make swap slower. Why? What’s the fundamental difference?
• Because data dependency is very bad for pipelines.
• Whereas the temporary in usual swap will be optimized or moved away.

28

Functions on Bits

• Check if Nth bit is set in an integer: x & (1 << (N-1))
• Divide by 2^N with shift: x >> N
• Counting bits set in an integer:

unsigned int x;�unsigned int c = 0;

for (; x; x >>= 1)�{� c += x & 1;�}

​

29

Functions on Bits

• Check if Nth bit is set in an integer: x & (1 << (N-1))
• Divide by 2^N with shift: x >> N
• Counting bits set in an integer, slightly faster:

unsigned int x;�unsigned int c = 0;

for (; x; c++)�{� x &= x - 1;�}

​

​

30

Functions on Bits

• Check if Nth bit is set in an integer: x & (1 << (N-1))
• Divide by 2^N with shift: x >> N
• Counting bits set in an integer, slightly faster:

unsigned int x;�unsigned int c = 0;

for (; x; c++)�{� x &= x - 1; // because 11000000 - 1 = 10111111�}

&-ing these together eliminates the rightmost bit that was 1

​

​

31

Functions on Bits

• Check if Nth bit is set in an integer: x & (1 << (N-1))
• Divide by 2^N with shift: x >> N
• Detect if two integers x, y have opposite signs:

bool opposite = ((x ^ y) < 0);

​

​

32

Functions on Bits

• Check if Nth bit is set in an integer: x & (1 << (N-1))
• Divide by 2^N with shift: x >> N
• Detect if an integer x is a power of 2:

33

bool is = x && !(x & (x - 1));

x = 01000000� x-1 = 00111111

then

x & (x-1) = 0

See more at bit twiddling hacks

Part II

Multi-Byte Data Representation

Multi-Byte Data Representation

There are 00000010 00000000 kinds of people in the world:�Those who understand endianness,�and those who don't.

​

35

“Powerful you have become, the dark side I sense in you.”

Multi-Byte Data Representation

36

int main()

{

short a = 256; // 00000001'00000000

​

// What will these print and why?

cout << (((char*)&a)[0] == 0);

cout << (((char*)&a)[1] == 1);

}

Multi-Byte Data Representation

37

Multi-Byte Data Representation

38

Multi-Byte Data Representation

• Issue arises in byte-addressable memory – one we use today.
• As opposed to bit- or word-addressable memory. (Word size = GP-register size).

39

Multi-Byte Data Representation

• Issue arises in byte-addressable memory – one we use today.
• As opposed to bit- or word-addressable memory. (Word size = GP-register size).
• Introduced with highly influential IBM System/360 in 1964.
• Previous models used bytes of variable size at arbitrary bit addresses.
• Byte order is referred to as endianness (from Gulliver's Travels).

​

​

​

​

​

​

Big-endian

40

Multi-Byte Data Representation

• Issue arises in byte-addressable memory – one we use today.
• As opposed to bit- or word-addressable memory. (Word size = GP-register size).
• Introduced with highly influential IBM System/360 in 1964.
• Previous models used bytes of variable size at arbitrary bit addresses.
• Byte order is referred to as endianness (from Gulliver's Travels).

​

​

​

​

​

​

Little-endian

41

Multi-Byte Data Representation

• Issue arises in byte-addressable memory – one we use today.
• As opposed to bit- or word-addressable memory. (Word size = GP-register size).
• Introduced with highly influential IBM System/360 in 1964.
• Previous models used bytes of variable size at arbitrary bit addresses.
• Byte order is referred to as endianness (from Gulliver's Travels).
• Intel CPUs are little-endian, also the default and the only required by RISC-V

​

​

​

​

​

Little-endian

42

Multi-Byte Data Representation

• Issue arises in byte-addressable memory – one we use today.
• As opposed to bit- or word-addressable memory. (Word size = GP-register size).
• Introduced with highly influential IBM System/360 in 1964.
• Previous models used bytes of variable size at arbitrary bit addresses.
• Byte order is referred to as endianness (from Gulliver's Travels).
• Intel CPUs are little-endian, also the default and the only required by RISC-V

43

• For such CPUs, compilers will lay out data in little-endian format.
• Big-endian is used in:
• RISC CPUs (MIPS, SPARC, Power(PC) of 1980s
• Motorola microprocessors.
• TCP / IP (See why. Big-endian is sometimes called network order).
• No endianness in registers (no “growing addresses” as in memory).
• Debuggers show register values in the form “natural to humans”.

Little-Endian Advantages

• Instructions to pick up an N-byte number are exactly the same for any N.

44

Little-Endian Advantages

• Instructions to pick up an N-byte number are exactly the same for any N.
• Casts are no-ops because LS byte is first, i.e. address is the same.

45

Little-Endian Advantages

• Instructions to pick up an N-byte number are exactly the same for any N.
• Casts are no-ops because LS byte is first, i.e. address is the same.
• Many math routines are correspondingly simpler and easier to write.

46

Little-Endian Advantages

• Instructions to pick up an N-byte number are exactly the same for any N.
• Casts are no-ops because LS byte is first, i.e. address is the same.
• Many math routines are correspondingly simpler and easier to write.
• Big-endian would need to adjust the pointer to arrive at LS byte, etc.

47

Little-Endian Advantages

• Instructions to pick up an N-byte number are exactly the same for any N.
• Casts are no-ops because LS byte is first, i.e. address is the same.
• Many math routines are correspondingly simpler and easier to write.
• Big-endian would need to adjust the pointer to arrive at LS byte, etc.
• Increasing a number simply appends bytes at higher addresses.

48

Little-Endian Advantages

• Instructions to pick up an N-byte number are exactly the same for any N.
• Casts are no-ops because LS byte is first, i.e. address is the same.
• Many math routines are correspondingly simpler and easier to write.
• Big-endian would need to adjust the pointer to arrive at LS byte, etc.
• Increasing a number simply appends bytes at higher addresses.
• Big-endian would need to shift everything to the right first to make room.

49

Big-Endian Advantages

• Tests of the number sign is quick by looking at the byte at offset zero.

50

Big-Endian Advantages

• Tests of the number sign is quick by looking at the byte at offset zero.
• Little-endian would need to adjust the pointer to arrive at sign’s byte.

51

Big-Endian Advantages

• Tests of the number sign is quick by looking at the byte at offset zero.
• Little-endian would need to adjust the pointer to arrive at sign’s byte.
• More human-readable.

52

Big-Endian Advantages

• Tests of the number sign is quick by looking at the byte at offset zero.
• Little-endian would need to adjust the pointer to arrive at sign’s byte.
• More human-readable. (Although contrast is less in right-to-left cultures.)

53

Big-Endian Advantages

• Tests of the number sign is quick by looking at the byte at offset zero.
• Little-endian would need to adjust the pointer to arrive at sign’s byte.
• More human-readable. (Although contrast is less in right-to-left cultures.)
• Network-related code is simpler.

54

Multi-Byte Data Representation

55

So what’s the verdict?

Multi-Byte Data Representation

56

So what’s the verdict?

​

​

“Agreement upon an order is more important

than the order agreed upon.”

​

Danny Cohen

Byte Swap

Unsigned int change_endianness(unsigned int value)�{� Unsigned int result = 0;�� result |= (value & 0x000000FF) << 24;� result |= (value & 0x0000FF00) << 8;� result |= (value & 0x00FF0000) >> 8;� result |= (value & 0xFF000000) >> 24;

return result;�}

57

Assembly

​

BSWAP eax

Hexspeak

• Sometimes a bug will only appear in debug mode.
• Because debug memory is often scrambled with special numbers.
• But is simply marked in release mode, making it work “as expected".
• Because it is faster to leave the contents as they are.

58

Microsoft (Visual Studio Debugger)

1. 0x0000000FF1CE in Office components.
2. 0xBEEFCACE in .NET as a magic number in resource files.
3. 0xBAADF00D in debug HeapAlloc() to mark uninitialized heap memory.
4. 0xABABABAB in debug HeapAlloc() to mark guard bytes after allocated memory.
5. 0xFEEEFEEE in debug HeapFree() to mark freed heap memory.
6. 0xCCCCCCCC by debug runtime library to mark uninitialized stack memory.
7. 0xCDCDCDCD by debug malloc() to mark uninitialized heap memory.
8. 0xDDDDDDDD by debug free() to mark freed heap memory.
9. 0xCAFEBABE used as the first four bytes in the bytecode of Java .class files

59

• When the JVM loads a class, it first checks for 0xCAFEBABE
• If missing or incorrect, the JVM throws an error like java.lang.ClassFormatError

Apple iOS Crash Reports

• 0x8BADF00D for long launch time, termination, etc.
• 0xDEADFA11 when the user force quits an application.
• 0xDEAD10CC when a background app holds a system resource.
• 0xC00010FF "cool off" when application was killed in response to a thermal event.
• 0xDEADFEED when a timeout occurs while spawning a service.

60

Other Hexspeak

• 0xABADCAFE to initialize all unallocated memory (Mungwall, AmigaOS).
• 0xBADDCAFE by Libumem to indicate uninitialized memory.
• 0xBADDCAFE on Sun Microsystems' Solaris marks uninitialized kernel memory.
• 0xD15EA5E "disease" indicates regular boot on the Nintendo GameCube and Wii.
• 0xDEADBAAD by Android libc abort() when native heap corruption is detected.
• 0xDEADBEEF often used to indicate a crash or deadlock in embedded systems.
• 0xDEADDEAD used with the Blue Screen of Death.
• 0xFEE1DEAD "feel dead" used in the Linux reboot system call.
• 0xBADC0FFEE0DDF00D used by IBM to indicate uninitialized CPU registers.

61

Questions?

62