Clemson University -- CPSC 231 -- Fall 2009 Binary representation and logic binary devices are relatively easy to build - positive feedback drives the device to one of two extreme states and keeps it there bit - binary digit - 0/1, off/on n bits have 2**n different patterns (permutations), can represent 0 to (2**n)-1 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...) memory contains series of bits, grouped into addressable units word - unit of memory access and/or size of data register(s), often 32 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) 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, aa 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