Clemson University -- CPSC 231 -- Spring 2010
Binary representation and logic
bit - binary digit - 0/1, off/on
binary devices are relatively easy to build
mathematical diversion: assume an n-state device where the cost of the
device is linear in n (= kn); the number of devices required for
representing an arbitrary number x is log_base_n(x); thus, the total
cost to represent x is equal to kn*log_base_n(x); find the number n
that minimizes this cost. (turns out to be n = e = 2.718...)
n bits have 2**n different patterns (permutations)
unsigned integer representation = 0 to (2**n)-1
Memory unit terminology
memory contains series of bits, grouped into addressable units
word - unit of memory access and/or size of data registers, 16/32/64 bits
byte - unit for character representation, 8 bits
nibble - unit for binary-coded decimal (BCD) digit (see top p. 98)
Signed binary number: s d3 d2 d1 d0 = (-1)**sign * sum[di*(b**i)]
sign is 0 for positive, 1 for negative
di is digit, 0 <= di < b
b is base (or radix)
signed magnitude (will look at two's complement later)
Conversions
decimal (base 10, digits 0-9)
binary (base 2, digits 0,1)
octal (base 8, digits 0-7)
hexadecimal (base 16, digits 0-f)
binary-to-decimal conversion by positional representation
decimal-to-binary conversion by using remainder bits from repeated
division by two
binary-to-hexadecimal and back using a table
similar conversions between decimal and other bases, but typically
decimal first converted to binary then to octal or hex
gdb conversions (p. 105)
p/d 0x123 -- print as decimal, passing a hexadecimal constant
p/x 123 -- print as hexadecimal, passing a decimal constant
p/t 123 -- print as binary, passing a decimal constant
(note that a leading zero is significant to gdb, 0123 is taken as octal)
Character encoding - ASCII (p. 106)
Magic numbers
numbers that read as English words/phrases when displayed in hexadecimal
- catch uninitialized variables / bad pointers - 0xdeadbeef, 0xbaadf00d
- identify file type - 0xcafebabe in Java class file
- typically chosen to be a large, negative, odd integer (and thus unlikely
to be a useful program constant)
(see en.wikipedia.org/wiki/Hexspeak)
Binary Logic
a | not a b | and a b | or a b | xor
--+---- ----+---- ----+---- ----+----
0 | 1 0 0 | 0 0 0 | 0 0 0 | 0
1 | 0 0 1 | 0 0 1 | 1 0 1 | 1
1 0 | 0 1 0 | 1 1 0 | 1
1 1 | 1 1 1 | 1 1 1 | 0
SPARC a = 0 0 1 1
opcode description b = 0 1 0 1 some common names
------ ------------- ----------- ---------------------------
false 0 0 0 0 false, zero, clear
and a and b 0 0 0 1 and
andn a and (not b) 0 0 1 0 and-not, inhibit, a>b
a 0 0 1 1 a
b and (not a) 0 1 0 0 inhibit, a**a
not not a 1 1 0 0 not a
b or (not a) 1 1 0 1 implies, implication, a=>b
a nand b 1 1 1 0 nand
true 1 1 1 1 true, one, set
Logic operators in C: && and || or ! not
(zero word = false, nonzero word = true)
Bitwise operators in C: & and | or ~ not ^ xor
(each bit in word independent)
Logic operators in SPARC assembly language:
and[cc] or[cc] xor[cc]
not[cc] andn[cc] orn[cc] xnor[cc]
Synthetic operators:
mov = or %g0, reg_or_imm, %dest_reg
clr = or %g0, %g0, %dest_reg
tst = orcc %reg, %g0, %g0
btst = andcc %reg, reg_or_imm, %g0 \
bset = or %reg, reg_or_imm, %dest_reg | reg_or_imm acts as mask
bclr = andn %reg, reg_or_imm, %dest_reg | (i.e., subset selection)
btog = xor %reg, reg_or_imm, %dest_reg /
SPARC instructions are detailed in appendix D, starting on page 409 of text
synthetic instructions are in appendix E, starting on page 473 of text
**