DOC PREVIEW
Duke CPS 100E - Lecture

This preview shows page 1-2-3 out of 10 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CompSci 100E32.1From bits to bytes to intsÿ At some level everything is stored as either a zero or a one A bit is a binary digit a byte is a binaryterm (8 bits) We should be grateful we can deal with Strings rather than sequences of 0's and 1's.  We should be grateful we can deal with an int rather than the 32 bits that make an intÿ int values are stored as two's complement numbers with 32 bits, for 64 bits use the type long, a char is 16 bits Standard in Java, different in C/C++ Facilitates addition/subtraction for int values We don't need to worry about this, except to note:o Infinity + 1 = - Infinityo Math.abs(-Infinity) > InfinityCompSci 100E32.2How are data stored?ÿ To facilitate compression coding we need to manipulate individual bits Why do we need to read one bit? Why do we need to write one bit? When do we read 8 bits at a time? Read 32 bits at a time?ÿ We can't actually write one bit-at-a-time. We can't really write one char at a time either. Output and input are buffered, minimize memory accesses and disk accesses Why do we care about this when we talk about data structures and algorithms?o Where does data come from?CompSci 100E32.3How do we buffer char output?ÿ Done for us as part of InputStream and Reader classes InputStreams are for reading bytes Readers are for reading char values Why do we have both and how do they interact?Reader r = new InputStreamReader(System.in); Do we need to flush our buffers?ÿ In the past Java IO has been notoriously slow Do we care about I? About O?  This is changing, and the java.nio classes helpo Map a file to a region in memory in one operationCompSci 100E32.4Buffer bit outputÿ To buffer bit output we need to store bits in a buffer When the buffer is full, we write it. The buffer might overflow, e.g., in process of writing 10 bits to 32-bit capacity buffer that has 29 bits in it How do we access bits, add to buffer, etc.?ÿ We need to use bit operations Mask bits -- access individual bits Shift bits – to the left or to the right Bitwise AND/OR/NEGATE bitsCompSci 100E32.5Bit Logical Operationsÿ Work on integers types in binary (by bit) longs, ints, chars, and bytesÿ Three binary operators And: & Or: | Exclusive Or (xor): ^ÿ What is result of  27 & 14? 27 | 14? 27 ^ 14?01111110011101000000a^ba|ba&bbaCompSci 100E32.6Bit Logical Operationsÿ Need to work bit position by bit position11011 = 27 (many leading zeros not shown)01110 = 14-----------& 01010 =| 11111 =^ 10101 =ÿ Also have unary negation (not): ~00000000000000000000000000011011 = 27~ 11111111111111111111111111100100 = -26ÿ Use “masks” with the various operators to Set or clear bits Test bits Toggle bitsÿ (Example later)CompSci 100E32.7Bit Shift Operationsÿ Work on same types as logical opsÿ One left shift and two right shifts Left shift: <<11011 = 2727 << 21101100 = 108 (shifting left is like? ) Logical right shift: >>>11011 = 2727 >>> 2110=6 (shifting right is like? ) Arithmetic right shift: >>11111111111111111111111111100100 = -26-26 >> 211111111111111111111111111111001 = -711111111111111111111111111111111 = -1-1 >>> 16 (for contrast)00000000000000001111111111111111 = 65575CompSci 100E32.8Representing pixelsÿ A pixel typically stores RGB and alpha/transparency values Each RGB is a value in the range 0 to 255 The alpha value is also in range 0 to 255Pixel red = new Pixel(255,0,0,0);Pixel white = new Pixel(255,255,255,0);ÿ Typically store these values as int values, a picture is simply an array of int valuesvoid process(int pixel){int blue = pixel & 0xff;int green = (pixel >> 8) & 0xff;int red = (pixel >> 16) & 0xff;}CompSci 100E32.9Bit masks and shiftsvoid process(int pixel){int blue = pixel & 0xff;int green = (pixel >> 8) & 0xff;int red = (pixel >> 16) & 0xff;}ÿ Hexadecimal number: 0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f Note that f is 15, in binary this is 1111, one less than 10000 The hex number 0xff is an 8 bit number, all onesÿ The bitwise & operator creates an 8 bit value, 0—255 (why) 1&1 == 1, otherwise we get 0, similar to logical and Similarly we have |, bitwise orCompSci 100E32.10Swap two ints “in place”ÿ Swap contents of two int variables without requiring extra memoryÿ Still requires three statements (same time on most machines)ÿ Replacevoid swap(int[] a, int j, int k){int temp = a[j];a[j] = a[k];a[k] = temp;}Withvoid swap(int[] a, int j, int k){a[j] = a[j] ^ a[k];a[k] = a[j] ^ a[k];a[j] = a[j] ^ a[k];}ÿ Works because x^x=0,x^0=x Proof left to the student. . . Once was useful; now more of a


View Full Document

Duke CPS 100E - Lecture

Documents in this Course
Topics

Topics

9 pages

Lecture

Lecture

3 pages

Notes

Notes

2 pages

Hashing

Hashing

19 pages

Lecture

Lecture

59 pages

Lecture

Lecture

6 pages

Lecture

Lecture

4 pages

Lecture

Lecture

20 pages

Lecture

Lecture

12 pages

Lecture

Lecture

12 pages

Lecture

Lecture

7 pages

Lecture

Lecture

8 pages

Lecture

Lecture

10 pages

Lecture

Lecture

4 pages

Notes

Notes

16 pages

Lecture

Lecture

5 pages

Lecture

Lecture

9 pages

Lecture

Lecture

4 pages

Lecture

Lecture

13 pages

Lecture

Lecture

6 pages

Lecture

Lecture

16 pages

Lecture

Lecture

5 pages

Lecture

Lecture

5 pages

Lecture

Lecture

12 pages

Lecture

Lecture

12 pages

Sets

Sets

14 pages

Lecture

Lecture

9 pages

Lecture

Lecture

4 pages

Test 1

Test 1

7 pages

Load more
Download Lecture
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?