Practical Applications of Bit Shifting and Bitsets in Java

Shifting and Bitsets CS 0447 Jarrett Billingsley

Class announcements there are a couple Java examples on the materials page! today we ll see more practical applications of the bitwise operations that we learned about last time o BUT FIRST... a few more operations CS447 2

Bit shifting CS447 3

Bit shifting besides AND, OR, and NOT, we can move bits around, too. if we shift these bits left by 1 we stick a 0 at the bottom. 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 1 0 again! 1 1 0 0 1 1 1 1 0 0 AGAIN! 1 1 0 0 1 1 1 1 0 0 0 AGAIN!!!! 1 1 0 0 1 1 1 1 0 0 0 0 CS447 4

Left-shifting in C/Java and MIPS (animated) C/Java/Python/etc. use the << operator for left shift: B = A << 4; // B = A shifted left 4 bits MIPS has the sll (Shift Left Logical) instruction: sll t2, t0, 4 # t2 = t0 << 4 but wait. if the bottom 4 bits of the result are now 0s o what happened to the top 4 bits? 0011 0000 0000 1111 1100 1101 1100 1111 the bit bucket is not a real place it's a programmer joke ok bits that get "shifted off" the top are discarded. this is really a kind of truncation, and may or may not lead to strange results! Bit Bucket CS447 5

So what does it DO? let's start with a value like 5 and shift left and see what happens. Binary Decimal 00000101 5 00001010 10 00010100 20 00101000 40 01010000 80 why is this happening well uh... what if I gave you 49018853 how do you multiply that by 10? by 100? by 100000? something very similar is happening here! CS447 6

a << n == a shifting left by n is the same as multiplying by 2n. o you probably learned this as "moving the decimal point " o and moving the decimal point right is like shifting the digits left. to quickly calculate powers of 2, shift 1 left by the desired exponent. o e.g. (1 << 5) == 1 25 ==25 with bit shifting, we're moving the binary point (yes, really) shifting is very fast on most CPUs! o way faster than multiplication in any case o HLL compilers will try really hard to replace "multiplication by a constant" with shifts and adds 2n CS447 7

<_< >_> we can shift right, too. 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 1 1 0 1 1 1 0 0 1 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 1 1 0 1 1 1 0 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 1 1 0 1 1 1 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 1 1 0 1 1 1 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 1 1 0 1 1 1 0 0 C uses >>, Java uses >>>, MIPS uses srl (Shift Right Logical). 32 bits on a slide is a bit much well if shifting left is like multiplying, then ? CS447 8

a >>> n == a shifting right by n is the same as dividing by 2n. Binary Decimal 01010000 80 2n that's what integer division gives us too, right? 40 00101000 5 / 2 == 2 20 00010100 10 5 2 00001010 00000101 00000010 but soon we'll see that right- shifting and division can sometimes disagree. CS447 9

Signed numbers messing things up again since they use the MSB as the sign bit, we have a problem. if we shift this right Unsigned Signed = 172 = 86 = 43 = -84 = 86 = 43 1 0 1 0 1 1 0 0 0 1 0 1 0 1 1 0 0 0 1 0 1 0 1 1 well that's a little unfortunate. Arithmetic Right Shift is used for signed numbers: it "smears" the sign bit into the top bits. = -84 = -42 = -21 1 0 1 0 1 1 0 0 1 1 0 1 0 1 1 0 1 1 1 0 1 0 1 1 Java uses >>, MIPS uses sra (Shift Right Arithmetic) CS447 10

Uh oh, they're fighting let's look at the values we get as we divide and shift. n a / 2n a a >> n -8010 -4010 -2010 -1010 -510 -310 -210 -110 0 101100002 110110002 111011002 111101102 111110112 111111012 111111102 111111112 -8010 -4010 -2010 -1010 -510 -210 -110 010 well that's a little weird. 1 actually, this is correct. but so is the way that integer division works. they're both right. 2 3 4 5 (we'll come back to this.) 6 7 CS447 11

Bit sets CS447 12

Booleans are wasteful! there are a lot of problems out there that involve storing large numbers of boolean (true/false) values. a boolean variable in Java (or bool in C/C++/Rust/many others) usually takes up an entire 8-bit byte to store 1 bit of information. a much more efficient way to store large numbers of booleans is by treating the bits of integers as arrays of booleans. this technique goes by a few names bit flags, bit arrays, bit vectors, bit maps, or bit sets, which is the term we ll be using. o the Bitset.javaexample shows why we call them bit sets because 1 means in the set and 0 means not in the set ! there s no syntax for accessing bits this way, but you can imagine we need to be able to do three things: bits[n] = 1, bits[n] = 0, and if(bits[n] != 0). CS447 13

Turning bits on (bits[n] = 1) let s say I have a pattern of 4 bits which control some LEDs. what if I want to turn on just bit 1? but importantly, we want to do it without changing any of the others. 1 3 0 2 0 1 0 0 Bit # which bitwise operation takes two values and can output a 1 when one of its inputs is 0? 1 0 0 0 1 0 0 | 0 if I just want to turn on bit 1, what pattern of bits will I use? 1 0 1 0 is there a way to generalize this pattern based on the bit s number? CS447 14

The pattern for bit n is (bits[n] = 1) let s see. To turn on bit #... OR with 0 00012 1 00102 2 01002 3 10002 bitwise 0 3 0 2 0 1 0 0 Bit # wait a second. these look like shifted versions of each other! you start with 1 and shift it left by the number of the bit you want to turn on. so: to turn on bit n, you do: bits = bits | (1 << n); or more tersely, bits |= (1 << n); CS447 15

Turning bits off (bits[n] = 0) now I want to do the opposite. I want to turn offjust bit 2. which bitwise operation takes two values and can output a 0 when one of its inputs is 0? 1 3 1 2 1 1 0 0 the pattern of bits needed looks odd.... 1 1 0 1 1 0 1 but this pattern of bits is not arbitrary. remember that (1 << 2) = 01002 & 1 1 0 1 0 this is the complementof(1 << 2)! to turn off bit n, you do: bits = bits & ~(1 << n); or more tersely, bits &= ~(1 << n); CS447 16

Testing if bits are 1 or 0 (if(bits[n] != 0)) now we have a pattern of bits that represents buttons being pressed. I want to see if button 1 is pressed and do something based on that. I want to sort of filter out or ignore the bits other than bit 1. all I care about is seeing if bit 1 is 0 or not-0. I can filter out bits by turning them off. which operation turns off bits? 1 3 0 2 1 1 0 0 1 0 0 1 1 0 0 once again, (1 << n)is the bit pattern, but this time we don t bitwise NOT it. & 0 so: to test bit n, you do: if((bits & (1 << n)) != 0) 0 0 1 0 CS447 17

These are set operations these aren t just arrays of bits. they represent sets. so... 0 1 1 0 & 1 0 1 0 AND gives the intersection, the set of things that are in both sets. 0 0 1 0 0 1 1 0 1 0 1 0 OR gives the union, the set of things that are in either set. | 1 1 1 0 0 1 1 0 ^ 1 0 1 0 the symmetric set difference is the set of items in one set but not both... what boolean operation is this? 1 1 0 0 XOR! CS447 18

Masking CS447 19

Masquerade we just saw that bitwise AND can turn off bits while leaving others untouched, which let us filter out unwanted bits. a mask is a specially-constructed value that has: o 1s in the bits that we want to keep o 0s in the bits that we want to discard what if I want to isolate the lowest 5 bits of a number? 00000000000011111100100001001011 00000000000000000000000000011111 & 00000000000000000000000000001011 this is masking: ANDing a value with a mask to isolate some bits by turning off the others. to isolate the lowest n bits, AND with 2n-1. or, bits & ((1 << n) 1) CS447 20

Another way to make masks what if you don't waaaaaanna calculate 2n-1? think of it this way: to extract n bits, you need n 1s (in binary). o so write that many 1s, then convert to hex, which is easy. n Binary Mask 1 2 3 4 5 6 11 1111 7 111 1111 Hex Mask notice the pattern in the hex versions. 1, 3, 7, F and then it repeats. 1 0x1 11 0x3 111 1111 0x7 0xF I don't even think of the binary anymore. I just go: "13 bits? 0xFFF gives me 12, then put 1 in front of that 0x1FFF." 1 1111 0x1F 0x3F 0x7F CS447 21

Masking can also do modulo! something arithmetically useful that masking can do: we re kind of truncating this value to 3 bits, right? and truncation performs modular arithmetic so this does 53 % 8. 00110101 = 53 = 8 - 1 & 00000111 00000101 = 5 so, if you want to modulo by 2n, AND with 2n-1. or, a % 2n == a& ((1 << n) - 1) note that this only works for powers of 2! you cannot do x & 49to do x % 50 because 50 is not a power of 2. CS447 22