From bits to bytes to intsHow are data stored?How do we buffer char output?Buffer bit outputBit Logical OperationsSlide 6Bit Shift OperationsRepresenting pixelsBit masks and shiftsSwap two ints “in place”CompSci 100E32.1From bits to bytes to intsAt some level everything is stored as either a zero or a oneA bit is a binary digit a byte is a binary term (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 intint values are stored as two's complement numbers with 32 bits, for 64 bits use the type long, a char is 16 bitsStandard in Java, different in C/C++Facilitates addition/subtraction for int valuesWe don't need to worry about this, except to note:oInfinity + 1 = - InfinityoMath.abs(-Infinity) > InfinityCompSci 100E32.2How are data stored?To facilitate compression coding we need to manipulate individual bitsWhy 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 accessesWhy do we care about this when we talk about data structures and algorithms?oWhere does data come from?CompSci 100E32.3How do we buffer char output?Done for us as part of InputStream and Reader classesInputStreams are for reading bytesReaders are for reading char valuesWhy 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 slowDo we care about I? About O? This is changing, and the java.nio classes helpoMap a file to a region in memory in one operationCompSci 100E32.4Buffer bit outputTo buffer bit output we need to store bits in a bufferWhen 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 itHow do we access bits, add to buffer, etc.?We need to use bit operationsMask bits -- access individual bitsShift bits – to the left or to the rightBitwise AND/OR/NEGATE bitsCompSci 100E32.5Bit Logical OperationsWork on integers types in binary (by bit) longs, ints, chars, and bytesThree binary operatorsAnd: &Or: |Exclusive Or (xor): ^What is result of 27 & 14?27 | 14?27 ^ 14?a b a&b a|b a^b0 0 0 0 00 1 0 1 11 0 0 1 11 1 1 1 0CompSci 100E32.6Bit Logical OperationsNeed to work bit position by bit position 11011 = 27 (many leading zeros not shown) 01110 = 14 -----------& 01010 = | 11111 =^ 10101 =Also have unary negation (not): ~ 00000000000000000000000000011011 = 27 ~ 11111111111111111111111111100100 = -26Use “masks” with the various operators toSet or clear bitsTest bitsToggle bits(Example later)What is result of 27 & 14?27 | 14?27 ^ 14”CompSci 100E32.7Bit Shift OperationsWork on same types as logical opsOne left shift and two right shiftsLeft shift: << 11011 = 2727 << 2 1101100 = 108 (shifting left is like? )Logical right shift: >>> 11011 = 27 27 >>> 2 110 = 6 (shifting right is like? )Arithmetic right shift: >> 11111111111111111111111111100100 = -26 -26 >> 2 11111111111111111111111111111001 = -7 11111111111111111111111111111111 = -1 -1 >>> 16 (for contrast) 00000000000000001111111111111111 = 65575CompSci 100E32.8Representing pixelsA pixel typically stores RGB and alpha/transparency valuesEach RGB is a value in the range 0 to 255The 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,fNote that f is 15, in binary this is 1111, one less than 10000The hex number 0xff is an 8 bit number, all onesThe bitwise & operator creates an 8 bit value, 0—255 (why)1&1 == 1, otherwise we get 0, similar to logical andSimilarly we have |, bitwise orCompSci 100E32.10Swap two ints “in place”Swap contents of two int variables without requiring extra memoryStill 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 = xProof left to the student. . .Once was useful; now more of a
View Full Document