datalab.ps

ICS 课程的Lab1

4174 y(we')-5 b(v)o(e)23 b(established)j(a)d(maximum)f(number)i(of)f
(operators)i(that)e(you)h(are)f(allo)n(wed)g(to)g(use)g(for)g(each)h
(function.)30 b(This)23 b(limit)0 4287 y(is)g(v)o(ery)g(generous)j(and)
d(is)g(designed)j(only)e(to)f(catch)h(e)o(gre)o(giously)h(inef)n
(\002cient)g(solutions.)31 b(Y)-10 b(ou)23 b(will)g(recei)n(v)o(e)h(tw)
o(o)e(points)0 4400 y(for)i(each)g(function)i(that)e(satis\002es)g(the)
g(operator)i(limit.)0 4552 y(Finally)-6 b(,)35 b(we')-5
b(v)o(e)32 b(reserv)o(ed)h(5)f(points)h(for)f(a)f(subjecti)n(v)o(e)j(e)
n(v)n(aluation)h(of)c(the)h(style)h(of)f(your)h(solutions)h(and)e(your)
h(com-)0 4665 y(menting.)59 b(Y)-10 b(our)34 b(solutions)i(should)f(be)
e(as)g(clean)i(and)f(straightforw)o(ard)j(as)c(possible.)60
b(Y)-10 b(our)34 b(comments)g(should)h(be)0 4778 y(informati)n(v)o(e,)
25 b(b)n(ut)f(the)o(y)g(need)g(not)g(\(and)h(should)g(not\))f(be)f(e)o
(xtensi)n(v)o(e.)0 5104 y Fh(P)o(art)29 b(I:)h(Bit)f(manipulations)0
5350 y Fj(T)-7 b(able)36 b(1)g(describes)i(a)e(set)g(of)g(functions)j
(that)d(manipulate)j(and)d(test)h(sets)f(of)g(bits.)67
b(The)36 b(\223Rating\224)h(\002eld)f(gi)n(v)o(es)h(the)0
5463 y(dif)n(\002culty)26 b(rating)g(\(the)f(number)g(of)f(points\))j
(for)d(the)h(puzzle,)h(and)f(the)g(\223Max)f(ops\224)i(\002eld)e(gi)n
(v)o(es)h(the)g(maximum)f(number)1924 5712 y(2)p eop
%%Page: 3 3
3 2 bop 355 485 3184 4 v 353 598 4 113 v 405 564 a Fj(Name)p
1271 598 V 701 w(Description)p 2759 598 V 1067 w(Rating)p
3101 598 V 101 w(Max)23 b(Ops)p 3537 598 V 355 601 3184
4 v 353 714 4 113 v 405 680 a Fi(bitNor\(x,y\))p 1271
714 V 313 w(\230\(x|y\))d Fj(using)25 b(only)f Fi(&)e
Fj(and)i Fi(\230)p 2759 714 V 546 w Fj(1)p 3101 714 V
344 w(8)p 3537 714 V 353 827 V 405 793 a Fi(bitXor\(x,y\))p
1271 827 V 313 w(\210)e Fj(using)j(only)f Fi(&)e Fj(and)i
Fi(\230)p 2759 827 V 819 w Fj(2)p 3101 827 V 321 w(14)p
3537 827 V 353 940 V 405 906 a Fi(isNotEqual\(x,y\))p
1271 940 V 93 w(x)54 b(!=)g(y?)p 2759 940 V 1203 w Fj(2)p
3101 940 V 344 w(6)p 3537 940 V 353 1053 V 405 1019 a
Fi(getByte\(x,n\))p 1271 1053 V 258 w Fj(Extract)24 b(byte)g
Fi(n)f Fj(from)g Fi(x)p 2759 1053 V 790 w Fj(2)p 3101
1053 V 344 w(6)p 3537 1053 V 353 1166 V 405 1132 a Fi(bang\(x\))p
1271 1166 V 533 w Fj(Compute)h Fi(!x)e Fj(without)i(using)h
Fi(!)d Fj(operator)p 2759 1166 V 201 w(4)p 3101 1166
V 321 w(12)p 3537 1166 V 353 1279 V 405 1245 a Fi(bitCount\(x\))p
1271 1279 V 313 w Fj(Count)i(number)g(of)g(1')-5 b(s)24
b(in)f Fi(x)p 2759 1279 V 665 w Fj(4)p 3101 1279 V 321
w(40)p 3537 1279 V 355 1282 3184 4 v 1155 1535 a(T)-7
b(able)24 b(1:)29 b(Bit-Le)n(v)o(el)23 b(Manipulation)k(Functions.)p
258 1657 3378 4 v 256 1770 4 113 v 308 1736 a(Name)p
1338 1770 V 864 w(Description)p 2856 1770 V 1098 w(Rating)p
3199 1770 V 101 w(Max)c(Ops)p 3634 1770 V 258 1774 3378
4 v 256 1887 4 113 v 308 1853 a Fi(tmin\(void\))p 1338
1887 V 531 w Fj(minimum)h(tw)o(o')-5 b(s)24 b(complement)h(inte)o(ger)p
2856 1887 V 300 w(1)p 3199 1887 V 344 w(4)p 3634 1887
V 256 1999 V 308 1966 a Fi(isNegative\(x\))p 1338 1999
V 366 w(x)54 b(<)h(0?)p 2856 1999 V 1288 w Fj(3)p 3199
1999 V 344 w(6)p 3634 1999 V 256 2112 V 308 2079 a Fi(divpwr2\(x,n\))p
1338 2112 V 421 w(x/\(1<<n\))p 2856 2112 V 1177 w Fj(2)p
3199 2112 V 321 w(15)p 3634 2112 V 256 2225 V 308 2191
a Fi(fitsBits\(x,n\))p 1338 2225 V 366 w Fj(return)25
b(1)e(if)h(x)f(can)h(be)f(a)g(n-bit)i(2')-5 b(s)24 b(comp)f(int)p
2856 2225 V 199 w(2)p 3199 2225 V 321 w(15)p 3634 2225
V 256 2338 V 308 2304 a Fi(isLessOrEqual\(x)o(,y)o(\))p
1338 2338 V 93 w Fj(x)h Fe(\024)e Fj(y)p 2856 2338 V
1410 w(3)p 3199 2338 V 321 w(24)p 3634 2338 V 256 2451
V 308 2417 a Fi(sum3\(x,)51 b(y,)j(z\))p 1338 2451 V
371 w Fj(sum)24 b(of)f(3)g(ints)h(using)h(a)e(single)i(add)p
2856 2451 V 469 w(3)p 3199 2451 V 321 w(16)p 3634 2451
V 256 2564 V 308 2530 a Fi(tc2sm\(x\))p 1338 2564 V 641
w Fj(con)l(v)o(ert)h(from)d(2')-5 b(s)24 b(comp)g(to)f(sign-mag)p
2856 2564 V 344 w(4)p 3199 2564 V 321 w(15)p 3634 2564
V 256 2677 V 308 2643 a Fi(satAdd\(x,y\))p 1338 2677
V 476 w Fj(saturating)k(addition\227no)f(o)o(v)o(er\003o)n(w)p
2856 2677 V 415 w(4)p 3199 2677 V 321 w(30)p 3634 2677
V 256 2790 V 308 2756 a Fi(isPower2\(x\))p 1338 2790
V 476 w Fj(is)e(x)f(a)g(po)n(wer)h(of)f(2?)p 2856 2790
V 971 w(4)p 3199 2790 V 321 w(60)p 3634 2790 V 258 2793
3378 4 v 1399 3046 a(T)-7 b(able)23 b(2:)29 b(Arithmetic)c(Functions)0
3305 y(of)e(operators)j(you)f(are)e(allo)n(wed)i(to)e(use)h(to)f
(implement)i(each)f(function.)0 3457 y(Function)35 b
Fi(bitNor)29 b Fj(computes)35 b(the)h(N)t Fd(O)t(R)f
Fj(function.)60 b(That)33 b(is,)i(when)e(applied)j(to)d(ar)n(guments)i
Fi(x)d Fj(and)i Fi(y)p Fj(,)g(it)f(returns)0 3570 y Fi(\230\(x|y\))p
Fj(.)25 b(Y)-10 b(ou)23 b(may)h(only)g(use)g(the)g(operators)i
Fi(&)c Fj(and)i Fi(\230)p Fj(.)0 3722 y(Function)h Fi(bitXor)20
b Fj(should)25 b(duplicate)h(the)e(beha)n(vior)i(of)d(the)h(bit)g
(operation)i Fi(\210)p Fj(,)c(using)j(only)f(the)g(operations)i
Fi(&)d Fj(and)h Fi(\230)p Fj(.)0 3874 y(Function)g Fi(isNotEqual)17
b Fj(compares)24 b Fi(x)d Fj(to)h Fi(y)f Fj(for)i(inequality)-6
b(.)31 b(As)21 b(with)h(all)h Ff(pr)m(edicate)h Fj(operations,)i(it)c
(should)i(return)f Fi(1)0 3987 y Fj(if)g(the)h(tested)h(condition)h
(holds)f(and)f Fi(0)e Fj(otherwise.)0 4139 y(Function)k
Fi(getByte)20 b Fj(e)o(xtracts)26 b(a)d(byte)i(from)f(a)g(w)o(ord.)31
b(The)24 b(bytes)h(within)g(a)e(w)o(ord)i(are)f(ordered)i(from)e(0)g
(\(least)h(signi\002-)0 4251 y(cant\))f(to)g(3)f(\(most)h
(signi\002cant\).)0 4404 y(Function)j Fi(bang)c Fj(implements)j(the)g
Fi(!)e Fj(using)j(other)f(operators\227the)j(operator)f
Fi(!)c Fj(is)h(often)h(pronounced)j Ff(bang)p Fj(\227hence)0
4516 y(the)24 b(function)i(name.)0 4668 y(Function)21
b Fi(bitCount)15 b Fj(returns)22 b(a)d(count)i(of)e(the)h(number)h(of)e
(1')-5 b(s)20 b(in)g(the)g(ar)n(gument.)29 b(Function)21
b Fi(bang)c Fj(computes)k(logical)0 4781 y(ne)o(gation)k(without)g
(using)f(the)g Fi(!)e Fj(operator)-5 b(.)0 5113 y Fh(P)o(art)29
b(II:)g(T)-9 b(w)o(o')l(s)29 b(Complement)h(Arithmetic)0
5359 y Fj(T)-7 b(able)23 b(2)h(describes)i(a)d(set)g(of)h(functions)i
(that)e(mak)o(e)g(use)g(of)f(the)h(tw)o(o')-5 b(s)24
b(complement)h(representation)j(of)23 b(inte)o(gers.)1924
5712 y(3)p eop
%%Page: 4 4
4 3 bop 0 573 a Fj(Function)25 b Fi(tmin)c Fj(returns)k(the)f(minimum)f
(inte)o(ger)-5 b(.)0 725 y(Function)25 b Fi(isNegative)18
b Fj(determines)26 b(whether)e Fi(x)f Fj(is)g(less)h(than)g(0.)0
877 y(Function)g Fi(divpwr2)19 b Fj(di)n(vides)25 b(its)e(\002rst)f(ar)
n(gument)j(by)e Fc(2)1825 844 y Fb(n)1872 877 y Fj(,)f(where)h
Fa(n)f Fj(is)g(the)i(second)g(ar)n(gument.)31 b(Y)-10
b(ou)22 b(may)h(assume)g(that)0 990 y Fc(0)j Fe(\024)f
Fa(n)f Fe(\024)h Fc(30)p Fj(.)k(It)24 b(must)f(round)i(to)n(w)o(ard)f
(zero.)0 1142 y(Function)i Fi(fitsBits)19 b Fj(checks)26
b(to)e(see)h(whether)g(x)f(can)h(be)f(represented)j(as)d(an)h(n-bit)g
(2')-5 b(s)24 b(complement)i(number)-5 b(.)32 b(If)24
b(so)0 1255 y(it)f(returns)i(1,)e(otherwise)j(it)d(returns)i(0.)0
1407 y(Function)g Fi(isLessOrEqual)17 b Fj(checks)25
b(to)e(see)h(whether)h(x)e(is)g(less)h(than)h(or)e(equal)i(to)e(the)h
(v)n(alue)g(y)-6 b(.)0 1559 y(Function)29 b Fi(sum3\(x,)52
b(y,)h(z\))27 b Fj(tak)o(es)i(the)f(sum)g(of)f(3)h(inte)o(gers)i(b)n
(ut)e(only)h(allo)n(ws)f(a)g(single)h(+)e(operator)j(to)e(be)g(used)h
(in)0 1672 y(the)24 b(code.)0 1824 y(Function)j Fi(tc2sm)21
b Fj(con)l(v)o(erts)28 b(from)d(a)f(2')-5 b(s)26 b(complement)g
(representation)k(to)25 b(an)g(equi)n(v)n(alent)i(v)n(alued)f(signed)h
(magnitude)0 1937 y(representation.)0 2089 y(Function)35
b Fi(satAdd)c Fj(performs)k(saturating)i(addition.)62
b(Namely)34 b(rather)h(than)g(positi)n(v)o(e)g(o)o(v)o(er\003o)n(w)e
(it)h(will)f(return)j(the)0 2202 y(maximum)22 b(inte)o(ger)h(v)n(alue)g
(and)g(rather)g(than)g(an)f(under\003o)n(w)h(\(sometimes)h(called)f(ne)
o(gati)n(v)o(e)g(o)o(v)o(er\003o)n(w\))f(it)f(will)h(return)i(the)0
2315 y(minimum)f(inte)o(ger)i(v)n(alue.)0 2467 y(Function)g
Fi(isPower2)19 b Fj(returns)25 b(1)e(if)h(x)f(is)g(a)g(po)n(wer)h(of)f
(2,)g(and)h(0)g(otherwise.)0 2798 y Fh(Advice)0 3045
y Fj(Y)-10 b(ou)27 b(are)h(welcome)f(to)g(do)h(your)g(code)g(de)n(v)o
(elopment)i(using)e(an)o(y)f(system)h(or)g(compiler)g(you)g(choose.)42
b(Just)28 b(mak)o(e)f(sure)0 3158 y(that)j(the)g(v)o(ersion)h(you)f
(turn)g(in)f(compiles)i(and)f(runs)g(correctly)i(on)d(our)h(class)g
(machines.)48 b(If)29 b(it)g(doesn')n(t)j(compile,)g(we)0
3270 y(can')n(t)25 b(grade)f(it.)0 3422 y(The)31 b Fi(dlc)f
Fj(program,)k(a)d(modi\002ed)i(v)o(ersion)g(of)e(an)h(ANSI)e(C)g
(compiler)l(,)35 b(will)d(be)f(used)i(to)e(check)i(your)g(programs)g
(for)0 3535 y(compliance)26 b(with)d(the)h(coding)h(style)g(rules.)k
(The)23 b(typical)j(usage)e(is)0 3762 y Fi(./dlc)52 b(bits.c)0
3989 y Fj(T)-7 b(ype)22 b Fi(./dlc)52 b(-help)19 b Fj(for)k(a)f(list)g
(of)g(command)h(line)g(options.)30 b(The)22 b(README)d(\002le)j(is)g
(also)h(helpful.)30 b(Some)21 b(notes)j(on)0 4102 y Fi(dlc)p
Fj(:)136 4329 y Fe(\017)46 b Fj(The)23 b Fi(dlc)f Fj(program)i(runs)h
(silently)g(unless)g(it)e(detects)j(a)d(problem.)136
4516 y Fe(\017)46 b Fj(Don')n(t)21 b(include)h Fi(<stdio.h>)15
b Fj(in)20 b(your)h Fi(bits.c)16 b Fj(\002le,)k(as)g(it)g(confuses)i
Fi(dlc)c Fj(and)i(results)i(in)e(some)g(non-intuiti)n(v)o(e)227
4629 y(error)25 b(messages.)0 4856 y(Check)j(the)g(\002le)e
Fi(README)e Fj(for)k(documentation)j(on)d(running)h(the)f
Fi(btest)c Fj(program.)42 b(Y)-10 b(ou')o(ll)28 b(\002nd)f(it)g
(helpful)i(to)f(w)o(ork)0 4969 y(through)f(the)d(functions)k(one)d(at)f
(a)g(time,)h(testing)h(each)f(one)g(as)g(you)g(go.)32
b(Y)-10 b(ou)24 b(can)h(use)g(the)g Fi(-f)e Fj(\003ag)h(to)h(instruct)h
Fi(btest)0 5082 y Fj(to)d(test)h(only)h(a)e(single)i(function,)g(e.g.,)
e Fi(./btest)51 b(-f)j(isPower2)p Fj(.)1924 5712 y(4)p
eop
%%Page: 5 5
5 4 bop 0 573 a Fh(Hand)31 b(In)e(Instructions)0 819
y Fj(When)24 b(you)g(are)g(ready)g(to)g(hand)g(in)g(your)g(code)g(you)g
(simply)h(type:)0 971 y Fi(submit)52 b(cs4400)g(lab1)g(bits.c)0
1123 y Fj(If)22 b(you)i(subsequently)i(\002nd)d(a)f(better)i(solution)h
(prior)e(to)g(the)g(deadline)i(then)e(just)g(resubmit)h(and)f(the)g
(old)g(v)o(ersion)i(will)d(be)0 1236 y(o)o(v)o(erwritten.)33
b(The)24 b(\002le)g(dates)i(will)e(be)h(used)g(to)f(determine)j
(whether)e(you)g(handed)i(it)d(in)g(on)h(time)f(or)h(not.)32
b(Submissions)0 1349 y(will)27 b(close)h(at)f(00:00)i(\002)n(v)o(e)d
(days)i(after)g(the)f(due)h(date.)40 b(Normally)28 b(a)f(lab)g(that)h
(is)f(more)g(than)h(tw)o(o)f(days)h(late)g(will)e(not)i(be)0
1462 y(accepted,)d(b)n(ut)g(you)f(also)g(ha)n(v)o(e)g(the)g(option)h
(of)e(using)i(\223late)f(days\224)h(as)f(described)i(on)d(the)h(class)h
(web)e(page.)0 1614 y(Hint:)30 b(it')-5 b(s)25 b(a)e(v)o(ery)i(bad)f
(idea)h(to)f(get)g(behind)i(in)e(this)h(class.)31 b(The)24
b(pace)h(is)e(rather)j(continuous.)33 b(Late)24 b(penalties)j(will)c
(ha)n(v)o(e)0 1727 y(a)g(signi\002cant)j(detrimental)f(ef)n(fect)g(on)e
(your)i(grade)f(if)g(last)g(year)g(is)f(an)o(y)h(indication.)136
1978 y Fe(\017)46 b Fj(Mak)o(e)24 b(sure)g(you)g(ha)n(v)o(e)h(included)
g(your)g(identifying)h(information)g(in)e(your)g(\002le)f
Fi(bits.c)p Fj(.)136 2166 y Fe(\017)46 b Fj(Remo)o(v)o(e)23
b(an)o(y)h(e)o(xtraneous)i(print)f(statements.)136 2354
y Fe(\017)46 b Fj(Mak)o(e)24 b(sure)g(you)g(ha)n(v)o(e)h(not)e
(included)j Fi(<stdio.h>)19 b Fj(as)k(it)h(will)f(confuse)i(dlc.)1924
5712 y(5)p eop
%%Trailer
end
userdict /end-hook known{end-hook}if
%%EOF