1
00:00:01,069 --> 00:00:03,189

the following content is provided under  a Creative Commons license your support  will help MIT OpenCourseWare continue to  offer high quality educational resources  for free  to make a donation or to view additional  materials from hundreds of MIT courses  visit MIT opencourseware at ocw.mit.edu  good afternoon everybody so welcome to  the third lecture of six one seven two  today today we're gonna talk about bit  hacks and today's going to be a really  fun lecture so first of all let's recall  the binary representation of a word so a  w bit word is represented as follows so  we're gonna number the bits from X 0 to  X W minus 1 starting from the rightmost  side and unsigned integer value stored  in X with this binary representation can  be computed as follows  so it's essentially the sum of a whole  bunch of powers of two and you sum the  product of the bit with the appropriate  power of 2 so if the bit is 1 in  position K then you multiply by 2 the  decaying of it 0 then you just add 0 so  for example let's say we have this 8 bit  word here and if we apply this equation  we get first we get 2 because there's a  1 bit in the first position so we  multiply 1 by 2 0 1 which is 2 then in  the second position we also have a 1 so  we multiply 1 by 2 to the 2 which is 4  and then we have 16 and 128 so we just  sum up all of these powers of 2 and that  gives us the unsigned integer value and  that 0b prefix here represents boolean  constant so that means we're gonna  interpret this constant as a boolean  value  there's also sign integers so you can  also represent negative numbers which is  useful and this is called the two's  complement representation and here's the  formula for computing a two's complement  representation of a word  so for bed zero all the way up to a bit  W minus two you do the same thing as  above but for the leftmost bit or a bit  W minus one use multiple you subtract  that bit multiplied by two to the W  minus one so for this example here for  we saw two plus four plus 16 that's the  same as above but for the leftmost bit  since we have a 1 here we're going to  subtract two to the seven which is 128  and this gives us the signed value for  the integer which is negative 106 does  that make sense  any questions about this representation  okay so the leftmost bit is known as a  sign bit because it tells you whether  you need to subtract by this negative  value or not so if it's zero then you  don't have to subtract anything if it's  one then you subtract by a large integer  value so in two's complement the all  zeros word is just zero so you just  applied the above formula and everything  is zero so you just get zero what's the  value of the all ones word yes  negative one right so the reason why  it's negative one so you can just use  the formula and we're gonna sum up a  bunch of powers of two all of the X sub  KS are going to be one so we're summing  up to the decay from K equals zero to W  minus two and that's a geometric series  which sums to 2 to the W minus 1 minus 1  and then for the sign bit we're gonna  subtract 2 to the W minus 1 so now the  two w minus ones cancel out and we're  just left with negative 1 so this is an  important property to know about two's  complement representation the all ones  word is just negative 1  and this leads to important identity  which says that X plus the ones  complement of X the ones complement is  just all the bits of X flipped is equal  to negative one this is because if you  add X with all of its bit bits flipped  then you're just gonna end up with all  ones word and we saw in the previous  slide that that's equal to negative 1  and from this identity we have that  negative X is equal to the ones  complement of X plus 1 so this relates  the two's complement to the ones  complement representation let's look at  an example so let's look at let's say X  is equal to this constant here the ones  complement of X or tilde of X is just  all the bits of X flipped and then to  get negative x we add one to the ones  complement of X and the fact of adding  one here is we're going to take the  rightmost 0 bit in the ones complement  flip that to a 1 and then for all the  bits the right of that we flip them to  zeros so another way to see this is you  look at the representation of X and you  flip all of the bits up to the rightmost  one but not including that rightmost one  bit and then you just copy everything  over so any questions about this ok  so this is a table showing the  relationship between hex and binary  representation so hex representation is  base 16 and the reason why we use hex is  because sometimes we have these big  binary constants and we don't want to  write have to type all of these symbols  into our code and hex gives us a more  compact format to write these constants  and this table you can basically just  look up for each possible hex value what  is binary representation is and for the  values from 0 to 9 we're just gonna use  the same as decimal representation for  hex and then for values 10 to 15 we're  gonna use two characters from A to F to  translate from hex to binary you just  take each hex digit look it up in this  table right out the binary equivalent  and then you concatenate together all of  the binary values you got so in this  example I have this hex constant which  says decide to code for food so now I  just look up each of these hex values in  this table so D is 1 1 0 1 e is 1 1 1 0  C is 1 1 0 0 and so on and I just  concatenate all of these values together  and that gives me my binary  representation and you can also go the  other way around converting binary to  hex and you do the same thing just look  it up in this table and the prefix 0x  here doesn't makes a hex constant just  like 0b doesn't get the boolean constant  so if you're using these constants in  your code and you're writing it in hex  then you should use the 0x prefix  okay so SIA has a bunch of bitwise  operators and here's a table describing  what these bitwise operators do so the  ampersand is just logical and the  vertical bar is logical or the this  caret sign is the export or exclusive or  and XOR just says that if either of the  two bits is one that we return one and  if both of the bits are 0 or both of  them are 1 then we return 0 the tilde  sign is the ones complement or the not  and then we have left shift and right  shift operators so let's look at how  these operators work on this example  here so we have these 2 8-bit words a  and B to compute a and B we just look at  every two-bit in the same position and a  and B and compute the and of those two  bits so 1 ANDed with 0 is 0 so we get 0  here 0 ended with 1 is 0 1 ANDed with 1  is 1 and so on a or B is similar but now  you apply the or operator instead of the  a n operators have either one of the two  positions is 1 then you return 1 and if  both are 0 then you return 0 so in a or  b all the bits  except for this bit here is 0 because in  the original two words both of the  corresponding bits were 0 for ax or b we  check if exactly one of the two bits is  one so for the leftmost bit we have 1  and 0 so only so we have exactly one bit  set to 1 and we get a 1 here the second  bit is 0 and 1 so that's 1 the third bit  is 1 1 so that's 0 and so on till Dovie  is just a 1 compliment of a we saw that  before we just flip all the bits a right  shifted by 3 we just shift the bit  string to the right by 3 and then we  fill in the digits or the bits on the  left with zeros and then a left shift of  shipped it with two we do the same thing  but to the left and then we fill in  these empty bits with zeros so these are  the bitwise operators in C any questions  for for a right shift there is a there  is a shift that can that will fill in  the upper digits what with whatever the  leftmost digit was but if you're working  with unsigned integers then it's not  going to do that for sine integers it  will and when we're doing bit  manipulations were usually going to  stick to unsigned integers so so we  don't have to worry about that okay so  now let's look at some common idioms  that you can do using these bitwise  operators so the first one we'll look at  is setting the case bit in a word X to  one so the idea here is to use a shift  followed by an or so we're going to  compute one left shift it by K if we  want to set the case bit to a one and  this gives us a mask with a 1 in exactly  the case position and 0 is everywhere  else and then now when we order that in  to X that's going to change the bit from  a zero to one if it was a zero and if  that bit was already set to one then  this doesn't do anything and then for  all of the other positions since we're  doing an or with zero we're just copying  over two bits from X such setting the  case bit we can also clear the case bit  and the idea here is to use a shift a  compliment and then an and so again  we're going to generate this mask one  left shifted by K but now we're gonna  take the complement of this so now we  have a zero in exactly the case position  and ones everywhere else and now when we  end this mass with X in the cave  position it's going to clear that bit  because we're  ending it with a zero so the result is  going to be zero no matter what was  there before  and that for all the remaining bits  since we're anding with one we're just  copying it over from the original word  you can toggle the case bit or flip the  case that using an shift and in an XOR  so again we're going to generate this  mask and then now when we do an XOR with  this mask it's going to change the bit  from a zero to one or from a one to a  zero because that's what XOR does so in  this example is changing from a zero to  one but if it was already a one then  it's going to toggle it back to zero any  questions ok so let's look at another  bit trick so here we're trying to  extract a bit field from a word X and  this is important if you're working with  encoded data and idea here is to do a  mask in a shift so we're going to  generate a mask with ones in exactly the  positions that we want to extract out of  this word and then zeros everywhere else  and then we're going to and X with the  mask and that's going to give us the  bits in the four positions that we  wanted to extract in this example and  then we have zeros everywhere else and  then now we're going to right shift this  value that we extracted so that so that  it appears in the least significant  digits so that we can use it in our  computation so this is a very useful bit  trick to know if you're working with  compressed or encoded data and if you  use dab it feels facilities in C is  actually going to generate assembly code  that will do masking and shifting for  you  you can also set a bit field in a word  so let's say we want to set a bit field  in X to some value Y the idea is to  first in invert this mask to clear those  bits we want to set in X and that we are  in the shifted value of y so let's say  we have these two words x and y here  we're going to generate the mast as we  did before but now we're going to flip  all the bits in a mask by taking the  ones complement and then we end the we  end the ones complement of the masts  with X and that's going to clear the  bits in X because we have zeros in  exactly those positions in their mask  and when you add that into X it will  return a zero and then for all the other  positions we're just copying in the bits  of X and then finally we're going to  left shift Y by an appropriate amount so  that we can line up the value with these  four bit positions here and then we can  now just or those values in and this  will set the positions and X to the  value Y in order in order to be safe you  should actually do a mask on the shifted  y value before you or it in because you  don't know that the value of y is within  the range of the mass so if Y has some  garbage values in the higher bits and  when you order this in it might pollute  the original value of x so for safety  you should actually do a mask before you  or the value the shifted value of y in  okay so any questions on this so now  let's look at how we can swap two  integers so we want to swap the values  of x and y the standard way to do this  is to use a temporary variable T so we  set T equal to X X equal to Y and then y  equal to T this does involve a temporary  variable however so now the question is  whether we can do a swap without using a  temporary variable it turns out that you  can using bit tricks so here's the code  for doing a know temp swap so you first  set X equal to X X or Y then y equal to  X X or Y and then X equal to X X or Y so  as anyone's seen this before okay good  so some of you have seen this before and  for the rest of you all I'll tell you  how it works in the next couple slides  so let's first look at an example of how  to run this code before we go into why  it actually works so we're gonna start  with these two words in X&Y we're first  going to do X equal X X or Y and now we  store the result in X and this is the  result when you do the XOR of these two  words and then now we do y equal to X X  or Y notice that the value of x here has  already changed so we're doing the XOR  of these two words and setting that to Y  and here this value is actually the same  as X so we've already placed X in Y and  I finally do another XOR we set X equal  to two X X X or Y and then this gives us  this value which which is y so at the  end we've just swapped x and y without  using any temporary variable so the  reason why this works is because XOR is  his own inverse so if you do X X or Y  and then X or the result of that with Y  you just get back X itself so let's look  at the truth table to see why this is  true so  in the X&Y columns I've shown all the  all the possibilities so there are four  different possibilities of x and y and  then I also have the values of X X or Y  so it's 1 in the rows where I have  exactly 1 1 and then 0 in the remaining  rows and now if I do X X or Y X sword  with y I'm going to XOR these values  with y 0 X or 0 is 0 1 X or 1 is 0 1 X  or 0 is 1 and 0 X 4 1 is 1 and notice  that these values are the same as the  values of X so when I XOR to this  something in twice it just canceled out  and I get back the original thing okay  so now let's go into why this bit trick  actually does a swap so in the first  line what we're doing is we're  generating a mask where with ones where  the bits and x and y differ because  that's what XOR is gonna give you it's  gonna return a 1 if the bits are  different and 0 otherwise so this is a  mass that tells us in which positions  the bits in x and y differ and I'm gonna  store that into X and then in the second  line when I do X X or Y this is going to  flip the bits and why that are different  from X because I'm exporting with this  mass which tells me which of the bits  differ from X and then if I XOR with  that mass I'm flipping the bits in Y  that differ from X and this will just  give me back X and I store that in Y so  we see that the original value of x is  in Y now and then in the last line I do  the same thing but now I'm flipping the  bits and X that are different from Y so  I still have the mass that's stored in X  and then I can XOR that mask with Y and  Y has the original value of x so this is  flipping the bits and X that differ from  Y and now I have the original value of y  stored in X  so this is a pretty cool trick right any  questions on why this works so one thing  about this bit trick here is that it's  actually poor poor at exploiting  instruction level parallelism so it's  actually gonna be slower than the naive  code that uses a temporary variable  because in the in the original code I  had I could actually execute two lines  in parallel I can store a value into the  temporary and then also changed one of  the values of x and y at the same time  whereas in this code here there's a  sequential dependence among these three  lines I can't execute any of the lines  in parallel we'll learn more about  instruction level parallelism in next  week's lectures but I just wanted to  point out that the performance of this  isn't actually that great but this is  actually a pretty cool trick to know  sometimes it shows up in job interviews  okay so the next thing we're going to  look at is finding a minimum of two  integers x and y so let's say we want to  store the result of the minimum in a  variable R here's a standard way to do  this we just use an if-else statement so  if X is less and Y then R is X and  otherwise R is set to Y here's an  equivalent expression it just uses the  ternary operator in C it does exactly  the same thing as the if-else statement  on the left  one performance problem with this code  is that there's a branch in the code so  we have this if statement that checks  with X is less than Y and modern  machines will do branch prediction and  for whatever branch it predicts the code  to take it's gonna do prefetching and  execute some of the instructions in  advance but the problem is if it miss  predicts the branch it does it does a  lot of wasted work and the processor has  to empty the pipeline and undo all the  work that it did so this is a  performance issue due to branch  misprediction modern compilers are  usually good enough to optimize this  branch away but sometimes the compiler  isn't good enough to optimize the branch  away so it's there a way to do a minimum  without using a branch all right so  here's how you do it so we set our equal  to Y X or X X or Y ANDed with negative X  less than Y so pretty obvious right so  why does this work so first we need to  know that the C language represents the  boolean values true and false with the  injures one and zero respectively  so now let's look at the two possible  cases first let's look at a case where X  is less than Y and then we'll look at  the case where X is greater than or  equal to Y so in the first case when X  is less than Y the comparison here X  less than Y is going to return one and  then we're going to negate that which  gives us negative one and recall from  earlier negative one is two all ones  word in two's complement representation  so when we and X X or Y with the all  ones word that just gives us X X or Y  and now we're left with Y X or X X or Y  and we know that we know that the  inverse of XOR is itself and therefore  the two y's cancel out here and we're  just left with X  and in this case X is indeed the minimum  in the other case we have X greater than  or equal to Y then the expression X less  Y it's going to return 0 negative of 0  is still 0 and then when we and X X or Y  was 0 we're left with 0 and this just  gives us Y X or 0 which is y and in this  case Y is the minimum with the two  integers so any questions how many of  you how many of you knew this already  good so we learned something new today  all right so let's see how how branches  work in in a real function so here we're  trying to merge together two sorted  arrays and this is a subroutine that's  used in merge sort if you've seen it  before so the inputs to this function  are three arrays so we want to merge  together arrays a and B and store the  result in C and then we also passed a  function the sizes of a and B in n a n  and B so what is the restrict keyword do  here does anyone know okay so the  restrict keyword tells the compiler that  this is going to be the only pointer  that can point to the particular data  and this enables the compiler to do more  optimizations so when you're writing  programs and you know that there can  only be one pointer pointing to specific  pieces of data then you can declare the  restrict keyword and this gives the  compiler more freedom to do  optimizations okay so now let's look at  this procedure here so while the sizes  of a and B are non zero we're going to  go into this if else clause and we're  going to check if the element pointed to  by a is less than or equal to the  element pointed to by B and if so we're  going to store that  pointed to by a into C and then we're  going to increment both the C and the a  pointers and then we're going to  decrement na this tells us that there's  one less element in a that we need to  merge it now and otherwise we do the  same thing but with the array B and NB  and if one of the two arrays becomes  empty then we go to one of these two  while loops at the bottom and we just  copy all the remaining elements in the  non empty array into C so here if na is  if n a is greater than zero then a is a  non empty array and then we just copy  the remaining elements of a into C and  otherwise we copy the remaining elements  of B into C so let's do a simple example  the last time we want to merge these two  arrays in green into the blue array here  so let's say the top array is a and the  bottom array is B in the blue array is C  so initially a and B are pointing to the  beginning of these two green arrays and  since both arrays are non-empty we're  going to compare the first two elements  here and we see that 3 is less than 4 so  we're gonna place 3 into the array C and  then we're going to increment the  pointer in a to point to the next  element and we're also going to  increment the pointer in C to point the  next slot now we're going to compare 4  in 12 4 is less than 12 so we place for  into the array C and we increment array  B and that we just keep doing this so 12  is less than 14 and 14 is less than 19  19 is less than 21 21 is less than 46  and here 23 is less than 46 and at this  point one of the arrays becomes empty so  B is empty now so now we get to the  second while loop and we see that a  still has elements in it and we just  copy the remaining elements in a into C  and then we're done so that's how the  standard code for merging two sorted  array works so let's look at each of  these branches to see if it's  predictable so a predictable branch is a  brain  that all that most of the time it  returns the same answer and only rarely  does it return a different answer in an  unpredictable branch is one where is  sometimes returns one value in sometimes  returns another value you can't really  predict it so let's look at the first  branch does anyone know if this branch  is predictable yes so it turns out that  this branch is actually predictable  because it's going to return true most  so the time except for the last time so  it's only going to return false when NB  is equal to zero and at that point  you're just gonna execute this once and  then you're done but most of the time  and B is going to be greater than zero  when you execute this and we call this a  predictable branch what about this the  second one sorry  yeah so it's all so ridiculous aim  reason what about the third one yes  yes so this turns out to be  unpredictable because we don't know the  values in a and B a priori so this this  condition inside the if statement is  going to return true about half of the  time because we don't know what values  are in a and B and that's going to be  unpredictable branch because we it's  going to return true or false about  50/50 what about the last one yeah why  yeah so it is predictable the reason why  it's predictable is that most of the  time it's going to return true and then  once it returns false you're never going  to look at that again in this inside  this function call so it returns true  most of the time and we call that a  predict low branch so branches one two  and four are okay because they're  predictable branches but branch three is  going to cause a problem it's an  unpredictable branch and the hardware  doesn't really like this because I can't  do prefetching efficiently so to fix  this we can use our no branch minimum  bit trick that we learned a couple  slides ago so now what we're doing is  we're going to have a variable called  comp which stores the result of the  comparison between the first element of  a in the first element of B and then now  we're going to get the minimum of a and  B as follows is the same bit trick that  we saw before so now the variable min is  going to store the smaller of the first  element of a in the first element of B  and we also have the result of this  comparison here so so that's stored in  comp so first we're gonna place the  minimum value in C and then based on the  result of comp we're going to increment  one of A or B so if a was less than or  equal to B then comp is going to be one  and a plus or plus equal comp is going  to  increment and buy a buy one and then be  plus equal to not cop is going to not do  anything because not comp is 0 and then  for na we're going to decrement by comp  so it's going to be 1 if a is less than  or equal to B and 0 otherwise  and then for NB we're going to decrement  by the not of the cop so only one of  these two lines is actually going to do  something based on the result of the  comparison and then the rest of the code  is the same as before any questions so  now we've gotten rid of this  unpredictable branch that we had before  so one thing about this optimization is  that it works well on certain machines  however on modern machines using a good  compiler like clang with the - oh 3 flag  the branch list version is usually going  to be slower than the branching version  because the compiler is actually smart  enough to get rid of the branch inside  the original version of minimum there's  this instruction called C move or a  conditional move where it's basically a  branch less instruction - for doing a  comparison we'll learn more about that  next week so this trick actually usually  doesn't really work there might be some  machines and some compilers it works but  most of the time the compiler is better  at optimizing this code than you are so  one of the common themes so far is that  I've told you about a really cool bit  trick and then I've told I told you that  it doesn't really work so why are we  even learning about these bit tricks  then if they don't even work  so first is because the compiler does  some of these bit tricks and it's  helpful to understand what these bit  tricks are so you can figure out what  the compiler is doing when you look at  the assembly code secondly sometimes the  compiler doesn't do these optimizations  for you and you have to do it yourself  thirdly many bit hacks for words extend  naturally to a bit and word hacks for  vectors which are widely used in  high-performance code so it's good to  know about these tricks these bit tricks  also arise and  domains and finally because they're just  fun to learn about and for project one  you'll be playing around with some of  these bit tricks so it's good to know  about these things that I've talked  about already here I'll talk about a bit  trick that actually does work so here  we're trying to do modular addition so  we want to do X plus y mod N and here  let's assume that X is between 0 and n  minus 1 and Y is also between 0 and n  minus 1 so the standard way to do this  is just to use the mod operator X plus y  mod n however this does a division which  is relatively expensive compared to  other operations unless N is a power of  two but most of the time you don't know  if N is a power of two at compile time  so the compiler can't actually translate  this to a right shift operation and then  it has to do a division so here's  another way to do it without using  division so we're first going to set Z  equal to the sum of X and y and then if  Z is less than n then it's ready within  the range and we can just return Z if Z  is greater than or equal to n well we  know it can be at most 2 n minus 2  because x and y we're both at most n  minus 1 so all we have to do is to  subtract n and bring it back into range  however this code has an unpredictable  branch here because we don't know  whether Z is less than n or not so now  we can use the same trick as minimum so  now we're gonna set our equal to Z minus  n and it with the negative of Z greater  than or equal to n so if Z is less than  n then this is going to return 0 in here  in n and it with 0 0 so we're just left  with Z and if Z is greater than or equal  to n then this is going to be 1 we  negate that we get negative 1 which is  all ones word and ANDed with all one's  it's just n so then as Z minus  and which will bring the result back  into range okay so any questions yes so  this pressure is just generating either  a boolean value one or zero there's  actually like the code that you execute  after it is still the same in either  case so the branch misprediction only  hurts you if there are two different  code paths in in this version there are  two different codes code paths because  one is doing Z and one is just one is  doing Z minus n all right so the next  problem we'll look at is computing or  rounding a value up to the nearest power  of two and this is just 2 to the ceiling  of log base 2 of n every call that LG of  n is the log base 2 event thus the  notation we'll be using in this class  here's some code to do this so we have  our value of n here first we're going to  decrement n and then we're going to do  an or of n with n right shifted by one  then an or with n and right shifted by  two and so on all the way up to 32 so we  do this for all powers of 2 up to 32 and  then finally we increment and at the end  so let's look at an example to see why  this works so we're starting with this  value of n here first we're going to  decrement it and what that does is it  flips the rightmost one bit to 0 and  then it fills in all the zeros right of  that with ones and then when we do this  line which says n is equal to n Ord with  n right shifted by one  that's essentially propagating all of  the one bits one position to the right  and then oaring those in so we can see  that this one bit got copied one  position to the right this one bit got  copied one position to the right  these ones also propagate but says there  ready ones it doesn't do anything for  the next line we're propagating the one  best two positions there right so this  one bit here gets copied here this one  gets copied here and so on and then the  next line is going to propagate bits for  positions to the right then 8 16 and 32  for this example here when I get to this  line I'm already done but in general you  have more bits in a word which I can't  fit on this slide and now we have  something that's exactly one less than a  power of two and when we add one to that  we just get a power of two so we're  gonna zero out all these one bits and  then place a one here and this is  exactly the power of two that's greater  than the value n so the first line here  is essentially guaranteeing us that the  log n minus 1 bit is set and we need  that bit to be set because we want to  propagate that bit to all the positions  to the right of it and then these six  lines here are populating all of the  bits to the right with ones and then the  last bit is setting the log n bits 1 and  then clearing all of the other bits so  one question is why did we have to  decrement n at the beginning yes  yeah so if n is already a power of two  and if we don't decrement and this is  isn't gonna work because the log n minus  one bit isn't set but if we decrement n  then it's gonna guarantee us that the  law against minus one bit is set so that  we can propagate that to the right okay  any questions yes  because in general you have you're using  64-bit words here here I don't have that  many bits here because I can't fit it on  the slide but in general you have more  bits okay let's look at another problem  here we want to compute the mask of the  least significant one in a word X so we  want a mask that has a one and only the  position of the least significant one in  X and zeros everywhere else  so how can we do this so we can set our  the result equal to X and it with  negative x so let's look at why this  works say here is X and recall negative  X is is the two's complement of X plus  one so what we do is we flip all of the  bits up to the rightmost one but not  including it and then we just copy all  of the bits over that's how we get  negative X from X and then now we  compare X and negative x we see that all  the bits when we add them together are  going to be zero  except for the bit at the position  corresponding to the least significant 1  bit in X and that's going to be 1 since  we're anding 1 and 1 and everything else  is going to be 0 and this will give us  the mask that we want okay so this works  because the binary representation of  minus X is just the ones complement of X  plus 1  so now a question is how can we find the  index of this bit so here I'm just  generating a mass that has a 1 in the  least-significant 1 in X but it doesn't  actually tell me the index of this bit  bit in other words I want to find the  log base 2 of a power of 2 so that's the  problem we want to solve and here's some  code that lets us do this so we have  this constant called de bruyne it's  written in hex here and then we have  this table of size 64 called convert and  now all we have to do is multiply X by  this de bruyne constant right shifted by  58 positions and then look up the result  in the convert table and that's gonna  give us log base 2 of a power of 2 any  questions ok so this looks like magic to  us so in the spirit of magic we're gonna  do a math magic trick and to do this  trick I'm going to need five volunteers  in the only requirement is that you need  to be able to follow directions so who  wants to volunteer for this magic trick  yes one two three four one more fine all  right coming up so line up here yeah  just line up right here  I can move a little bit over to the left  okay cool so today I have the pleasure  of welcoming Jasser a also known as a  golden ratio to join us for lecture and  help us perform this cool magic trick so  let's give her a round of applause we'll  be doing a little bit of a magic trick  for you all today I'm gonna be reading  your guys's minds and I know you're  looking skeptical but I'm hoping I can  convince you here so we'll get to that  part in a second but first the first big  step in reading minds is you got to  clear the air like get rid of all the  negative vibes all the bad energy throw  that out so I'm gonna need a little help  from you guys and doing this so first we  have this sweet old Bell here let's say  who wants the Bell  all right can you hold that for a second  so what this Bell is gonna do is help us  get rid of some of those negative vibes  Mia it's gonna give it a ring oh yeah  so that painful ringing you're hearing  in your ears right now is actually just  clearing out the air for us making it so  I can read your minds thank you stop  that all right  next we have this magic tome here who  would like to give this a spin hey can  you a shake that around a couple times  in it go like this there we go  all right perfect all right it's feeling  a little clearer here I can start a can  start getting things off your minds  don't worry I won't tell anybody what  you're thinking oh let's see what else  let me channel the spirits  all right feeling good all right so what  we're gonna be doing is as I said  reading your mind I'm gonna be doing  this by giving you cards and I'm gonna  tell you what each of you are holding  for the card so I have some cards here I  guess either a little small let's see go  a little bigger yeah here we go  let's this looks better all right get  rid of these junk ones up here all right  so need your help for this so what I  want you to do is take the cards and cut  the deck as many times as you want so  basically just going like that however  much just don't actually like shuffle  them randomly all right cool  so now I'm gonna hand each of you a card  don't let me see it feel free to look at  it yeah all right so the reason I'm  wearing this awesome onesie is this  helps me sweat out the bad energy I'm  literally sweating right now but there's  one more piece that we need for this  mind-reading trick it's a magic hat all  right  see if it spits on my head there we go  where's the switch all right turn it on  all right feeling good here all right  you guys ready all right so I do need a  little help getting this trick started  so if you're holding a red card can you  just raise your hand so now who's got  the red card red Fred you don't have red  okay so all right so the first one and  the third one all right so let me I  channel the mind-reading abilities yeah  now what I'm gonna do is gonna go left  to right and tell you what you're  holding obviously I know the color but  I'll tell you what suit it is and also I  will tell you what the number is  so first card obviously I know you have  a red hmm  I'm feeling a diamond and also a for  yeah all right all right good start good  start  all right got a to think about what the  next one is here alright so I know you  got a black card let's see black of  Spades is it ace of spades oh yeah there  we go alright so back to red alright  this one let's see red diamond - alright  alright we're doing good so far can I  get the last two um all right let's see  what you can do here  all right black Club for alright last  one last one  alright it's gonna be a tough one black  Spade eight and if we had time I could  you know mystify you and go through the  rest of the deck but we won't do that so  thank you guys very much I hope your  minds were blown yeah me collect the  cards back from you  thank you all right thank you now I can  get out of this and stop sweating it's  pretty cool right so why does this  actually work to know why this trick  actually works we need to first study  what a de Bruyne sequence is so a de  Bruyne sequence s of length two to decay  is a cyclic bit sequence such that each  of the two to decay possible bit strings  of length K occurs exactly once as a  substring in s all right so this is a  pretty long definition so let's look at  an example so here's a de bruyne  sequence for K equals three so the  length of this sequence is 8 because 2  to the 3 is 8 and you can see that each  of the possible 3 bit substrings occurs  exactly once in this cyclic bit string  of length 8 so it wraps around at the  end you can consider this as a cyclic  string so we see that 0 0 0 appears at  position 0 0 0 1 is that position 1 that  0 1 0 is at position 6 0 1 one's at  position 2 1 0 0 is at position 7 1 0  ones at 5 1 1 0 is at 4 and then 1 1 1  is at 3 so all of the eight possible  substrings of length 3 occur exactly  once in this de bruyne sequence ok so  now we're going to create this convert  table of length 8 in general this will  be 2 to the K and here K is 3 and in  this convert table what we're storing in  each position is the index in the de  bruyne sequence where the bit string  corresponding to that position starts in  the in the  de Bruyne sequence so here we see that  convert of two is six because the bit  string corresponding to two is zero one  zero and that begins at position six in  the de Bruyne sequence we also see that  convert of four is seven because 4 is 1  0 0 and that begins at position 7 in the  de bruyne sequence now we have this  convert table and recall that we're  trying to compute the log base 2 of a  power of 2 so hopefully you guys  remember that so the way to do this is  we're going to multiply the de bruyne  sequence constant by this power of 2 so  let's say we're working with the integer  16 which is 2 2 4 so we're going to  multiply this de bruyne sequence by 2 to  the 4 and when we multiply by a power of  2 that's the same as left shifting so  that's going to laugh shift at the Broin  sequence for positions to the left and  then now we want to see which of the  eight possible sub strings appears at  the beginning of this sequence and after  we do the left shift 1 1 0 appears at  the beginning of the sequence and we  want to extract this out and we can do  that by right shifting 5 positions and 1  1 0 is just 6 and we can figure out  where 6 starts in this de bruyne  sequence by looking it up in the convert  table so we see that convert of 6 is 4  so the string 1 1 0 appears starting at  position 4 in the de bruyne sequence and  that means that we did a left shift by 4  in the first step and that gives us the  log base 2 of the power of 2 because the  only reason why we did a left shift by 4  is because the the power of 2 was 2 to  the 4 so this returns us to log base 2  of the integer that we started with and  one thing to notice is that it's  important to  start with all zeroes in this sequence  here because we're representing this as  a cyclic bit sequence so when we do a  left shift we need to make sure that the  values that fill in on the right side  are correct so notice that in the sixth  and seventh positions we need zeros at  the end when we overflow so because the  de bruyne sequence starts with all zeros  when we do the left shift is  automatically gonna fill in with zeros  giving us the correct substring so a  magic trick that just did had 32 cards  where and in that case K was equal to 5  and the cards were arranged according to  a de bruyne sequence of length 32 and  each of the cards correspond to one  particular bit string of length five and  the color of the card corresponding to  the bit so when she asked you what the  color of your card was she could  determine the the bits corresponding to  the first card in the sequence because  she has the five bits corresponding to  that card and with that she has some  clever way to determine the rest of the  cards so that's how the the Bruyne  sequence is related to the magic trick  that you just saw any questions yes  so there could be multiple de bruyne  sequence we just need one particular de  bruyne sequence to make this bit Rick  work yeah so this example was just for K  equals three I mean the code I showed  you before that was for K equals eight  so you can do up to 64 bit words yes so  there's a mathematical proof that says  that I can give you some pointers so  that you can look at it after class but  there's a proof that says that for any  length there is a de bruyne sequence yes  so so we have we're starting with some  integer that is a power of two so what  we multiply by that power of to its left  shifting by the log base two of that and  then we can determine how much we left  shifted because we know we can just look  at the first three bits of this sequence  after we did the left shift and then  look at where that 3-bit sequence  appears in the in the original de Bruyne  sequence before we shifted it and to do  that you can look it up in the convert  table this is what we did when we looked  up the bit string 1 1 0 in the convert  table and that tells us that it starts  in the 4th position that means that we  left shifted by 4 and that's that means  that the value of n was 2 to the 4 does  that make sense  yes so this only works if you're  starting with a power of 2 so if it's  not a power of 2 this doesn't work  any other questions yes if it's not a  power of two you can round it up to the  nearest power of two using another bit  trick that we saw earlier and then you  can use this bit trick here the  performance of this bit trick is limited  by the performance of multiplication and  table lookup so you have to do a  multiplication by some constant and then  you have to do table lookup in this  convert table so a table lookup does a  memory reference which could be  expensive and nowadays there's actually  a hardware instruction to compute this  so you don't actually have to implement  this trick but this trick is still  pretty cool cool and in the past this is  how you would do it before there was a  hardware instruction that came out okay  so let's look at another problem so this  is the N Queens problem how many of  you've seen this before yeah so many of  you have seen this before as a reminder  we're trying to place n Queens on an N  by n chess board so that no Queens  attacks another Queen in other words  there are no two Queens in any row any  column or any diagonal and commonly we  want to count the number of possible  solutions to the N Queens problem for a  particular value of n and in this  example here this is a valid  configuration you can check for each of  the Queens it can't attack any other  Queen on the board so one common  strategy for implementing the N Queens  algorithm is to use backtracking we're  gonna try placing Queens row by row we  know that there can only be one Queen  per row so we just need to determine  which position in that row the Queen  will appear in and then if we can't  place a queen in any row then we  backtrack so for example in the first  row we'll just place the Queen in the  first position because there's no Queens  on the board yet so the first position  is valid for the second row  we're gonna try to place in the first  position but we can't place it there  because then it will attack the first  Queen and then the second position is  also invalid so the third position is  where we place the second Queen now for  a third row we're going to check the  positions until we get to one that's  valid and this is going to be the fifth  position do this again here we can do it  in the second position for the fifth row  let's see where this this is going to  end off okay so it goes in the fourth  position what about the sixth row  so oops so all of the eight positions  are invalid because if we place the  Queen in any of those positions it's  going to attack one of the Queens that  we already placed so now we're going to  backtrack when you'll find another  position for the fifth Queen so let's  try some more positions okay so we can  place it at the end now we try again  all right so unfortunately we couldn't  find a position for the six row again we  have the backtrack but we already tried  all the positions in the fifth row so we  backtrack to the fourth row and you get  the idea  and then whenever we find a  configuration where all eight queens are  valid then we increment some counter by  one and at the end we just return this  counter which tells us the number of  solutions to the end Queens puzzle okay  so so you can implement this quite  easily using a recursive procedure you  can implement this backtracking search  but one question is how should we  represent the board to facilitate you  fish and queen placement so one way to  represent the board is to use an array  of n squared bytes and for each byte we  just have a one if there's a queen in  that position and zero otherwise is  there a better way to represent the  board  yeah so so that's a good answer so  instead of using bytes we can use bits  because the value can only be 0 1 we  only need one bit to represent that so  we can just have an array of n squared  bits is there a better way to do this  yes yes so good answers so a better way  to do this is to just use an array of n  bytes because we know that on each row  there can only be one Queen so we just  need to store the position of that Queen  so we have an array of and bytes one  byte for each row and then you just use  the byte to store the position of the  Queen in that row it turns out to  implement this algorithm there's a even  more compact representation which is to  use three bit vectors of size n - n  minus 1 + 2 n minus 1 so let's see how  this works  so the first bit vector we're gonna use  is of length n we're called gonna call  this the down vector and the down vector  just stores a 1 in the columns that have  a queen in it and 0 in the columns that  are empty and then when we when we want  to check whether placing a queen is safe  in any position we first have to check  whether that column is empty and you can  do this by anding the down bit vector  with one left shifted by C or C is the  column where you want to place the Queen  and if that's nonzero that means there's  already a queen and that call me you  can't place it otherwise we're gonna  have to do another check and we're gonna  create this other bit vector called left  the length of this back bit vector is 2n  minus 1 and it stores of 1 in the  diagonal that has a queen in it and  zeros otherwise and there are 2n minus 1  possible diagonals and then now when we  want to place a queen in row R and  column C we can check whether it's safe  by doing left and it with one left  shifted by R plus C and this is going to  be nonzero if there's already a queen in  that particular diagonal so in that case  we can't place the Queen there and  otherwise we're gonna do a final check  using this right bit vector which is  essentially the same but we're looking  at the diagonals going down to the right  so again we have a 1 in the diagonals  that have a queen and zeros otherwise  and then now the check is going to be  right and it with one left shifted by n  minus one minus R plus C and if a  particular candidate passes all three of  these checks then we know that there's  not going to be a conflict and we can  place the queen in that particular  position so this is a bit vector  representation you actually still have  to write the code to count the number of  Queens using this bit vector  representation and it's actually a  interesting exercise so I encourage you  to try to do this at home but I just  told you about the bit vector  representation send you questions yes  yeah so the down vector is stores a1 in  the columns I have a queen in it and  zeros otherwise and what you do is if  you want to place a queen in column C  you you first create the mask one left  shifted by C and then you and it with  the down vector and that's gonna be  nonzero if there's a queen in that  column all right any other questions yes  so it turns out that you don't need it  just these three checks is enough to  guarantee guarantee that you can place a  queen in a position if it passes all  three of the checks yes a fourth check  would just be redundant yeah that's true  good point yeah so we're only placing  one queen in each particular row all  right so let's look at another problem  this is called population count or pop  count for a short and the problem here  is we want to count the number of 1 bits  in some word X here's a way to do this  that repeatedly eliminates the least  significant 1 bit in the word so we have  this for loop where R is initialized to  0 and we're going to repeat this loop  until X becomes 0 and that each time we  go through this loop we increment our  and inside the loop we're going to set X  equal to X ANDed with X minus 1 and this  is going to clear the least-significant  one bit in X so let's look at an example  so let's say we have this value here for  X well to get X minus 1 we flip the  rightmost one bit in X from a 1 to 0 and  then we fill in all the bits the right  of that with one's and then now when we  end those things two things together  we're going to copy all of the bits up  to the rightmost one and then for the  rightmost one we're going to zero it out  because we're ending with a zero and  then all the bits the right of that are  still going to be 0 so X ended with X  minus 1 is  going to get rid of the least  significant one bit and then we repeat  this process until X becomes zero in  that case we've already eliminated all  the ones and we know the answer which is  stored in our questions okay so so this  code will be pretty fast if the number  of 1 bits is small but but the running  time is proportional to the number of 1  bits and the word so in the worst case  if most of the bits are set to 1 then  you're going to need a lot of iterations  to run this code so let's look at a more  efficient way to do this this is to use  table lookup so we're gonna create a  table of size 256 which stores for each  8-bit word the number of ones in that  8-bit word so we have all possible 8-bit  words stored in this table and then now  to get the number of 1 bits in X for  every 8-bit substring in X we're going  to look it up in this count table and  add it to our and then we're going to  write shift X by 8 so that we can get  the next word and then when X becomes 0  we know we're done so that's that's  table lookup and the performance here  depends on the size of X if we have a  64-bit word we need to do this at most 8  times whereas in the initial code we  might have to do it 64 times if we had  64 one bits the cost of this code is  bottlenecked by the memory operations  because this table here is stored in  memory so every time you access it you  have to go to memory to fetch the value  there and here are some approximate  costs for accessing memory and various  levels of the hierarchy  if something sorted in register it's  very fascinates you one cycle if it's  stored in l1 cache it's about 4 cycle  l2-cache about 10 cycles l3 cache about  50 cycles and then finally if you have  to go to DRAM because it's not in cache  it's much more expensive 150 cycles it's  an order of magnitude slower than doing  something fetching something that's  already stored in the register okay so  let's now look at a third way to do  population count where we don't actually  have to go to cache or drm essentially  we can do everything in registers so  here's how you do it so we're gonna  create these five mass or six mass from  m 0 up to m5 and these mass the values  of these masks are shown in the comments  here in this notation here X to the K  just means X repeated K times so the  mask m5 has 32 zeros followed by 32 ones  the mass m0 has the base ring 0 1  repeated 32 times and so on after we  create these mass we're going to execute  these sex instructions at the bottom and  this is going to give us the number of  ones in the word so let's do an example  to see how this works so let's say we  start with this bit string here in the  first in the first step what we're gonna  do is we're gonna and X with the mask m0  and then we're also going to and X right  shifted by 1 with the mask  m0 and recall that the mask M 0 is just  0 1 repeated 32 times and therefore the  mass is essentially extracting all the  even bits so X ANDed with m0 gives us  all the even bits and then when we write  shift X by 1 and end it with m0 that's  going to give us all the odd bits and  then we're gonna line those two things  up and add them together and the result  of doing this is it's going to tell us  for every group of two bits the number  of one bits in that group so now for  each of these pairs of bits is telling  us how  many of them were won so in the  left-most group here we had two ones so  the result of adding 1 & 1 is 1 0 which  is 2 for the rightmost group we have 2  zeros and the count there is 0 0 and  this is the same for all of the other  groups so this gives us the number of  ones in every pair of in every pair of  positions now we're gonna end and the  result with m1 and we're gonna right  shift it by 2 and also and it with m1  and add those two things together and m1  is a mass that will give us the bottom  two bits in every group of 4 bits so  when we write shift X by 2 that's giving  us the top two bits and then now we add  those together and it will give us the  count of the number of 1 bits in every  group of size 4 and these are the count  these counts are stored in the result  here now so you can verify that each of  these groups has the count of the number  of 1 bits so for example we have 1 0 0  here and this is correct since there are  4 1 bits now we do this again with the  mass m2 that's going to give us the  counts for all groups of size 8 do we go  to groups of size 16 and I finally we  add these two together giving us the  number of bits in this group of size 32  and this is actually the pop count so  the value here is 17 and you can verify  that there are indeed 17 1s in the input  word X any questions  so the performance of this code which is  based on a parallel divide-and-conquer  is going to be proportional to log base  two of W where W is the word length  because on every step I'm doubling the  size of my groups and after I do this  log base two of W times I have the whole  group in the first two instructions that  are executed here I have to actually do  the and separately for X right shifted  by one and X and also X right shifted by  two and X and then add them together  because there's an overflow issue the  overflow issue is that the size of the  groups here might not be large enough to  actually store the count of the number  of one bits in that group but once I get  to the larger groups the count can  always be stored in a group of that size  and I don't need to worry about overflow  so for the last four lines I can  actually save one instruction I don't  need to do the and twice  okay so it turns out that most modern  machines nowadays have an intrinsic pop  count instruction implemented in  hardware which is faster than anything  you can code yourself and you can access  this pop count instruction via compiler  intrinsics for example in GCC or clang  and in GCC it's underscore underscore  built-in underscore pop count one  warning though is that if you write this  code using these intrinsics  if you run if you try to compile the  code on a machine that doesn't support  it your code isn't going to compile so  it makes your code less portable but  this this intrinsic is faster than the  parallel divide-and-conquer version so  one question is how could get the log  base two of a power of two quickly using  a pop count instruction so instead of  using the de bruyne sequence trick yes  yes so what you do is you subtract one  from the power of two and that's gonna  flood off the lower bits with ones and  then now when you execute pop count it's  gonna count the number of ones and that  gives us the log base two of the power  of two so good answer all right so those  are all the bit tricks I'm gonna be  talking about today there's a lot of  resources online if you're interested in  learning more there's this really good  website maintained by Shawn Aaron  Anderson there's also the news textbook  which has some bit tricks in there  there's a chess programming website  which has a lot of cool bit tricks some  of those are used in implementing chess  programs and then finally this book  called hackers delight so you'll be  playing around with many of these bit  tricks in project one so happy bit  hacking  you

2
00:00:03,189 --> 00:00:05,769
the following content is provided under  a Creative Commons license your support  will help MIT OpenCourseWare continue to  offer high quality educational resources  for free  to make a donation or to view additional  materials from hundreds of MIT courses  visit MIT opencourseware at ocw.mit.edu  good afternoon everybody so welcome to  the third lecture of six one seven two  today today we're gonna talk about bit  hacks and today's going to be a really  fun lecture so first of all let's recall  the binary representation of a word so a  w bit word is represented as follows so  we're gonna number the bits from X 0 to  X W minus 1 starting from the rightmost  side and unsigned integer value stored  in X with this binary representation can  be computed as follows  so it's essentially the sum of a whole  bunch of powers of two and you sum the  product of the bit with the appropriate  power of 2 so if the bit is 1 in  position K then you multiply by 2 the  decaying of it 0 then you just add 0 so  for example let's say we have this 8 bit  word here and if we apply this equation  we get first we get 2 because there's a  1 bit in the first position so we  multiply 1 by 2 0 1 which is 2 then in  the second position we also have a 1 so  we multiply 1 by 2 to the 2 which is 4  and then we have 16 and 128 so we just  sum up all of these powers of 2 and that  gives us the unsigned integer value and  that 0b prefix here represents boolean  constant so that means we're gonna  interpret this constant as a boolean  value  there's also sign integers so you can  also represent negative numbers which is  useful and this is called the two's  complement representation and here's the  formula for computing a two's complement  representation of a word  so for bed zero all the way up to a bit  W minus two you do the same thing as  above but for the leftmost bit or a bit  W minus one use multiple you subtract  that bit multiplied by two to the W  minus one so for this example here for  we saw two plus four plus 16 that's the  same as above but for the leftmost bit  since we have a 1 here we're going to  subtract two to the seven which is 128  and this gives us the signed value for  the integer which is negative 106 does  that make sense  any questions about this representation  okay so the leftmost bit is known as a  sign bit because it tells you whether  you need to subtract by this negative  value or not so if it's zero then you  don't have to subtract anything if it's  one then you subtract by a large integer  value so in two's complement the all  zeros word is just zero so you just  applied the above formula and everything  is zero so you just get zero what's the  value of the all ones word yes  negative one right so the reason why  it's negative one so you can just use  the formula and we're gonna sum up a  bunch of powers of two all of the X sub  KS are going to be one so we're summing  up to the decay from K equals zero to W  minus two and that's a geometric series  which sums to 2 to the W minus 1 minus 1  and then for the sign bit we're gonna  subtract 2 to the W minus 1 so now the  two w minus ones cancel out and we're  just left with negative 1 so this is an  important property to know about two's  complement representation the all ones  word is just negative 1  and this leads to important identity  which says that X plus the ones  complement of X the ones complement is  just all the bits of X flipped is equal  to negative one this is because if you  add X with all of its bit bits flipped  then you're just gonna end up with all  ones word and we saw in the previous  slide that that's equal to negative 1  and from this identity we have that  negative X is equal to the ones  complement of X plus 1 so this relates  the two's complement to the ones  complement representation let's look at  an example so let's look at let's say X  is equal to this constant here the ones  complement of X or tilde of X is just  all the bits of X flipped and then to  get negative x we add one to the ones  complement of X and the fact of adding  one here is we're going to take the  rightmost 0 bit in the ones complement  flip that to a 1 and then for all the  bits the right of that we flip them to  zeros so another way to see this is you  look at the representation of X and you  flip all of the bits up to the rightmost  one but not including that rightmost one  bit and then you just copy everything  over so any questions about this ok  so this is a table showing the  relationship between hex and binary  representation so hex representation is  base 16 and the reason why we use hex is  because sometimes we have these big  binary constants and we don't want to  write have to type all of these symbols  into our code and hex gives us a more  compact format to write these constants  and this table you can basically just  look up for each possible hex value what  is binary representation is and for the  values from 0 to 9 we're just gonna use  the same as decimal representation for  hex and then for values 10 to 15 we're  gonna use two characters from A to F to  translate from hex to binary you just  take each hex digit look it up in this  table right out the binary equivalent  and then you concatenate together all of  the binary values you got so in this  example I have this hex constant which  says decide to code for food so now I  just look up each of these hex values in  this table so D is 1 1 0 1 e is 1 1 1 0  C is 1 1 0 0 and so on and I just  concatenate all of these values together  and that gives me my binary  representation and you can also go the  other way around converting binary to  hex and you do the same thing just look  it up in this table and the prefix 0x  here doesn't makes a hex constant just  like 0b doesn't get the boolean constant  so if you're using these constants in  your code and you're writing it in hex  then you should use the 0x prefix  okay so SIA has a bunch of bitwise  operators and here's a table describing  what these bitwise operators do so the  ampersand is just logical and the  vertical bar is logical or the this  caret sign is the export or exclusive or  and XOR just says that if either of the  two bits is one that we return one and  if both of the bits are 0 or both of  them are 1 then we return 0 the tilde  sign is the ones complement or the not  and then we have left shift and right  shift operators so let's look at how  these operators work on this example  here so we have these 2 8-bit words a  and B to compute a and B we just look at  every two-bit in the same position and a  and B and compute the and of those two  bits so 1 ANDed with 0 is 0 so we get 0  here 0 ended with 1 is 0 1 ANDed with 1  is 1 and so on a or B is similar but now  you apply the or operator instead of the  a n operators have either one of the two  positions is 1 then you return 1 and if  both are 0 then you return 0 so in a or  b all the bits  except for this bit here is 0 because in  the original two words both of the  corresponding bits were 0 for ax or b we  check if exactly one of the two bits is  one so for the leftmost bit we have 1  and 0 so only so we have exactly one bit  set to 1 and we get a 1 here the second  bit is 0 and 1 so that's 1 the third bit  is 1 1 so that's 0 and so on till Dovie  is just a 1 compliment of a we saw that  before we just flip all the bits a right  shifted by 3 we just shift the bit  string to the right by 3 and then we  fill in the digits or the bits on the  left with zeros and then a left shift of  shipped it with two we do the same thing  but to the left and then we fill in  these empty bits with zeros so these are  the bitwise operators in C any questions  for for a right shift there is a there  is a shift that can that will fill in  the upper digits what with whatever the  leftmost digit was but if you're working  with unsigned integers then it's not  going to do that for sine integers it  will and when we're doing bit  manipulations were usually going to  stick to unsigned integers so so we  don't have to worry about that okay so  now let's look at some common idioms  that you can do using these bitwise  operators so the first one we'll look at  is setting the case bit in a word X to  one so the idea here is to use a shift  followed by an or so we're going to  compute one left shift it by K if we  want to set the case bit to a one and  this gives us a mask with a 1 in exactly  the case position and 0 is everywhere  else and then now when we order that in  to X that's going to change the bit from  a zero to one if it was a zero and if  that bit was already set to one then  this doesn't do anything and then for  all of the other positions since we're  doing an or with zero we're just copying  over two bits from X such setting the  case bit we can also clear the case bit  and the idea here is to use a shift a  compliment and then an and so again  we're going to generate this mask one  left shifted by K but now we're gonna  take the complement of this so now we  have a zero in exactly the case position  and ones everywhere else and now when we  end this mass with X in the cave  position it's going to clear that bit  because we're  ending it with a zero so the result is  going to be zero no matter what was  there before  and that for all the remaining bits  since we're anding with one we're just  copying it over from the original word  you can toggle the case bit or flip the  case that using an shift and in an XOR  so again we're going to generate this  mask and then now when we do an XOR with  this mask it's going to change the bit  from a zero to one or from a one to a  zero because that's what XOR does so in  this example is changing from a zero to  one but if it was already a one then  it's going to toggle it back to zero any  questions ok so let's look at another  bit trick so here we're trying to  extract a bit field from a word X and  this is important if you're working with  encoded data and idea here is to do a  mask in a shift so we're going to  generate a mask with ones in exactly the  positions that we want to extract out of  this word and then zeros everywhere else  and then we're going to and X with the  mask and that's going to give us the  bits in the four positions that we  wanted to extract in this example and  then we have zeros everywhere else and  then now we're going to right shift this  value that we extracted so that so that  it appears in the least significant  digits so that we can use it in our  computation so this is a very useful bit  trick to know if you're working with  compressed or encoded data and if you  use dab it feels facilities in C is  actually going to generate assembly code  that will do masking and shifting for  you  you can also set a bit field in a word  so let's say we want to set a bit field  in X to some value Y the idea is to  first in invert this mask to clear those  bits we want to set in X and that we are  in the shifted value of y so let's say  we have these two words x and y here  we're going to generate the mast as we  did before but now we're going to flip  all the bits in a mask by taking the  ones complement and then we end the we  end the ones complement of the masts  with X and that's going to clear the  bits in X because we have zeros in  exactly those positions in their mask  and when you add that into X it will  return a zero and then for all the other  positions we're just copying in the bits  of X and then finally we're going to  left shift Y by an appropriate amount so  that we can line up the value with these  four bit positions here and then we can  now just or those values in and this  will set the positions and X to the  value Y in order in order to be safe you  should actually do a mask on the shifted  y value before you or it in because you  don't know that the value of y is within  the range of the mass so if Y has some  garbage values in the higher bits and  when you order this in it might pollute  the original value of x so for safety  you should actually do a mask before you  or the value the shifted value of y in  okay so any questions on this so now  let's look at how we can swap two  integers so we want to swap the values  of x and y the standard way to do this  is to use a temporary variable T so we  set T equal to X X equal to Y and then y  equal to T this does involve a temporary  variable however so now the question is  whether we can do a swap without using a  temporary variable it turns out that you  can using bit tricks so here's the code  for doing a know temp swap so you first  set X equal to X X or Y then y equal to  X X or Y and then X equal to X X or Y so  as anyone's seen this before okay good  so some of you have seen this before and  for the rest of you all I'll tell you  how it works in the next couple slides  so let's first look at an example of how  to run this code before we go into why  it actually works so we're gonna start  with these two words in X&Y we're first  going to do X equal X X or Y and now we  store the result in X and this is the  result when you do the XOR of these two  words and then now we do y equal to X X  or Y notice that the value of x here has  already changed so we're doing the XOR  of these two words and setting that to Y  and here this value is actually the same  as X so we've already placed X in Y and  I finally do another XOR we set X equal  to two X X X or Y and then this gives us  this value which which is y so at the  end we've just swapped x and y without  using any temporary variable so the  reason why this works is because XOR is  his own inverse so if you do X X or Y  and then X or the result of that with Y  you just get back X itself so let's look  at the truth table to see why this is  true so  in the X&Y columns I've shown all the  all the possibilities so there are four  different possibilities of x and y and  then I also have the values of X X or Y  so it's 1 in the rows where I have  exactly 1 1 and then 0 in the remaining  rows and now if I do X X or Y X sword  with y I'm going to XOR these values  with y 0 X or 0 is 0 1 X or 1 is 0 1 X  or 0 is 1 and 0 X 4 1 is 1 and notice  that these values are the same as the  values of X so when I XOR to this  something in twice it just canceled out  and I get back the original thing okay  so now let's go into why this bit trick  actually does a swap so in the first  line what we're doing is we're  generating a mask where with ones where  the bits and x and y differ because  that's what XOR is gonna give you it's  gonna return a 1 if the bits are  different and 0 otherwise so this is a  mass that tells us in which positions  the bits in x and y differ and I'm gonna  store that into X and then in the second  line when I do X X or Y this is going to  flip the bits and why that are different  from X because I'm exporting with this  mass which tells me which of the bits  differ from X and then if I XOR with  that mass I'm flipping the bits in Y  that differ from X and this will just  give me back X and I store that in Y so  we see that the original value of x is  in Y now and then in the last line I do  the same thing but now I'm flipping the  bits and X that are different from Y so  I still have the mass that's stored in X  and then I can XOR that mask with Y and  Y has the original value of x so this is  flipping the bits and X that differ from  Y and now I have the original value of y  stored in X  so this is a pretty cool trick right any  questions on why this works so one thing  about this bit trick here is that it's  actually poor poor at exploiting  instruction level parallelism so it's  actually gonna be slower than the naive  code that uses a temporary variable  because in the in the original code I  had I could actually execute two lines  in parallel I can store a value into the  temporary and then also changed one of  the values of x and y at the same time  whereas in this code here there's a  sequential dependence among these three  lines I can't execute any of the lines  in parallel we'll learn more about  instruction level parallelism in next  week's lectures but I just wanted to  point out that the performance of this  isn't actually that great but this is  actually a pretty cool trick to know  sometimes it shows up in job interviews  okay so the next thing we're going to  look at is finding a minimum of two  integers x and y so let's say we want to  store the result of the minimum in a  variable R here's a standard way to do  this we just use an if-else statement so  if X is less and Y then R is X and  otherwise R is set to Y here's an  equivalent expression it just uses the  ternary operator in C it does exactly  the same thing as the if-else statement  on the left  one performance problem with this code  is that there's a branch in the code so  we have this if statement that checks  with X is less than Y and modern  machines will do branch prediction and  for whatever branch it predicts the code  to take it's gonna do prefetching and  execute some of the instructions in  advance but the problem is if it miss  predicts the branch it does it does a  lot of wasted work and the processor has  to empty the pipeline and undo all the  work that it did so this is a  performance issue due to branch  misprediction modern compilers are  usually good enough to optimize this  branch away but sometimes the compiler  isn't good enough to optimize the branch  away so it's there a way to do a minimum  without using a branch all right so  here's how you do it so we set our equal  to Y X or X X or Y ANDed with negative X  less than Y so pretty obvious right so  why does this work so first we need to  know that the C language represents the  boolean values true and false with the  injures one and zero respectively  so now let's look at the two possible  cases first let's look at a case where X  is less than Y and then we'll look at  the case where X is greater than or  equal to Y so in the first case when X  is less than Y the comparison here X  less than Y is going to return one and  then we're going to negate that which  gives us negative one and recall from  earlier negative one is two all ones  word in two's complement representation  so when we and X X or Y with the all  ones word that just gives us X X or Y  and now we're left with Y X or X X or Y  and we know that we know that the  inverse of XOR is itself and therefore  the two y's cancel out here and we're  just left with X  and in this case X is indeed the minimum  in the other case we have X greater than  or equal to Y then the expression X less  Y it's going to return 0 negative of 0  is still 0 and then when we and X X or Y  was 0 we're left with 0 and this just  gives us Y X or 0 which is y and in this  case Y is the minimum with the two  integers so any questions how many of  you how many of you knew this already  good so we learned something new today  all right so let's see how how branches  work in in a real function so here we're  trying to merge together two sorted  arrays and this is a subroutine that's  used in merge sort if you've seen it  before so the inputs to this function  are three arrays so we want to merge  together arrays a and B and store the  result in C and then we also passed a  function the sizes of a and B in n a n  and B so what is the restrict keyword do  here does anyone know okay so the  restrict keyword tells the compiler that  this is going to be the only pointer  that can point to the particular data  and this enables the compiler to do more  optimizations so when you're writing  programs and you know that there can  only be one pointer pointing to specific  pieces of data then you can declare the  restrict keyword and this gives the  compiler more freedom to do  optimizations okay so now let's look at  this procedure here so while the sizes  of a and B are non zero we're going to  go into this if else clause and we're  going to check if the element pointed to  by a is less than or equal to the  element pointed to by B and if so we're  going to store that  pointed to by a into C and then we're  going to increment both the C and the a  pointers and then we're going to  decrement na this tells us that there's  one less element in a that we need to  merge it now and otherwise we do the  same thing but with the array B and NB  and if one of the two arrays becomes  empty then we go to one of these two  while loops at the bottom and we just  copy all the remaining elements in the  non empty array into C so here if na is  if n a is greater than zero then a is a  non empty array and then we just copy  the remaining elements of a into C and  otherwise we copy the remaining elements  of B into C so let's do a simple example  the last time we want to merge these two  arrays in green into the blue array here  so let's say the top array is a and the  bottom array is B in the blue array is C  so initially a and B are pointing to the  beginning of these two green arrays and  since both arrays are non-empty we're  going to compare the first two elements  here and we see that 3 is less than 4 so  we're gonna place 3 into the array C and  then we're going to increment the  pointer in a to point to the next  element and we're also going to  increment the pointer in C to point the  next slot now we're going to compare 4  in 12 4 is less than 12 so we place for  into the array C and we increment array  B and that we just keep doing this so 12  is less than 14 and 14 is less than 19  19 is less than 21 21 is less than 46  and here 23 is less than 46 and at this  point one of the arrays becomes empty so  B is empty now so now we get to the  second while loop and we see that a  still has elements in it and we just  copy the remaining elements in a into C  and then we're done so that's how the  standard code for merging two sorted  array works so let's look at each of  these branches to see if it's  predictable so a predictable branch is a  brain  that all that most of the time it  returns the same answer and only rarely  does it return a different answer in an  unpredictable branch is one where is  sometimes returns one value in sometimes  returns another value you can't really  predict it so let's look at the first  branch does anyone know if this branch  is predictable yes so it turns out that  this branch is actually predictable  because it's going to return true most  so the time except for the last time so  it's only going to return false when NB  is equal to zero and at that point  you're just gonna execute this once and  then you're done but most of the time  and B is going to be greater than zero  when you execute this and we call this a  predictable branch what about this the  second one sorry  yeah so it's all so ridiculous aim  reason what about the third one yes  yes so this turns out to be  unpredictable because we don't know the  values in a and B a priori so this this  condition inside the if statement is  going to return true about half of the  time because we don't know what values  are in a and B and that's going to be  unpredictable branch because we it's  going to return true or false about  50/50 what about the last one yeah why  yeah so it is predictable the reason why  it's predictable is that most of the  time it's going to return true and then  once it returns false you're never going  to look at that again in this inside  this function call so it returns true  most of the time and we call that a  predict low branch so branches one two  and four are okay because they're  predictable branches but branch three is  going to cause a problem it's an  unpredictable branch and the hardware  doesn't really like this because I can't  do prefetching efficiently so to fix  this we can use our no branch minimum  bit trick that we learned a couple  slides ago so now what we're doing is  we're going to have a variable called  comp which stores the result of the  comparison between the first element of  a in the first element of B and then now  we're going to get the minimum of a and  B as follows is the same bit trick that  we saw before so now the variable min is  going to store the smaller of the first  element of a in the first element of B  and we also have the result of this  comparison here so so that's stored in  comp so first we're gonna place the  minimum value in C and then based on the  result of comp we're going to increment  one of A or B so if a was less than or  equal to B then comp is going to be one  and a plus or plus equal comp is going  to  increment and buy a buy one and then be  plus equal to not cop is going to not do  anything because not comp is 0 and then  for na we're going to decrement by comp  so it's going to be 1 if a is less than  or equal to B and 0 otherwise  and then for NB we're going to decrement  by the not of the cop so only one of  these two lines is actually going to do  something based on the result of the  comparison and then the rest of the code  is the same as before any questions so  now we've gotten rid of this  unpredictable branch that we had before  so one thing about this optimization is  that it works well on certain machines  however on modern machines using a good  compiler like clang with the - oh 3 flag  the branch list version is usually going  to be slower than the branching version  because the compiler is actually smart  enough to get rid of the branch inside  the original version of minimum there's  this instruction called C move or a  conditional move where it's basically a  branch less instruction - for doing a  comparison we'll learn more about that  next week so this trick actually usually  doesn't really work there might be some  machines and some compilers it works but  most of the time the compiler is better  at optimizing this code than you are so  one of the common themes so far is that  I've told you about a really cool bit  trick and then I've told I told you that  it doesn't really work so why are we  even learning about these bit tricks  then if they don't even work  so first is because the compiler does  some of these bit tricks and it's  helpful to understand what these bit  tricks are so you can figure out what  the compiler is doing when you look at  the assembly code secondly sometimes the  compiler doesn't do these optimizations  for you and you have to do it yourself  thirdly many bit hacks for words extend  naturally to a bit and word hacks for  vectors which are widely used in  high-performance code so it's good to  know about these tricks these bit tricks  also arise and  domains and finally because they're just  fun to learn about and for project one  you'll be playing around with some of  these bit tricks so it's good to know  about these things that I've talked  about already here I'll talk about a bit  trick that actually does work so here  we're trying to do modular addition so  we want to do X plus y mod N and here  let's assume that X is between 0 and n  minus 1 and Y is also between 0 and n  minus 1 so the standard way to do this  is just to use the mod operator X plus y  mod n however this does a division which  is relatively expensive compared to  other operations unless N is a power of  two but most of the time you don't know  if N is a power of two at compile time  so the compiler can't actually translate  this to a right shift operation and then  it has to do a division so here's  another way to do it without using  division so we're first going to set Z  equal to the sum of X and y and then if  Z is less than n then it's ready within  the range and we can just return Z if Z  is greater than or equal to n well we  know it can be at most 2 n minus 2  because x and y we're both at most n  minus 1 so all we have to do is to  subtract n and bring it back into range  however this code has an unpredictable  branch here because we don't know  whether Z is less than n or not so now  we can use the same trick as minimum so  now we're gonna set our equal to Z minus  n and it with the negative of Z greater  than or equal to n so if Z is less than  n then this is going to return 0 in here  in n and it with 0 0 so we're just left  with Z and if Z is greater than or equal  to n then this is going to be 1 we  negate that we get negative 1 which is  all ones word and ANDed with all one's  it's just n so then as Z minus  and which will bring the result back  into range okay so any questions yes so  this pressure is just generating either  a boolean value one or zero there's  actually like the code that you execute  after it is still the same in either  case so the branch misprediction only  hurts you if there are two different  code paths in in this version there are  two different codes code paths because  one is doing Z and one is just one is  doing Z minus n all right so the next  problem we'll look at is computing or  rounding a value up to the nearest power  of two and this is just 2 to the ceiling  of log base 2 of n every call that LG of  n is the log base 2 event thus the  notation we'll be using in this class  here's some code to do this so we have  our value of n here first we're going to  decrement n and then we're going to do  an or of n with n right shifted by one  then an or with n and right shifted by  two and so on all the way up to 32 so we  do this for all powers of 2 up to 32 and  then finally we increment and at the end  so let's look at an example to see why  this works so we're starting with this  value of n here first we're going to  decrement it and what that does is it  flips the rightmost one bit to 0 and  then it fills in all the zeros right of  that with ones and then when we do this  line which says n is equal to n Ord with  n right shifted by one  that's essentially propagating all of  the one bits one position to the right  and then oaring those in so we can see  that this one bit got copied one  position to the right this one bit got  copied one position to the right  these ones also propagate but says there  ready ones it doesn't do anything for  the next line we're propagating the one  best two positions there right so this  one bit here gets copied here this one  gets copied here and so on and then the  next line is going to propagate bits for  positions to the right then 8 16 and 32  for this example here when I get to this  line I'm already done but in general you  have more bits in a word which I can't  fit on this slide and now we have  something that's exactly one less than a  power of two and when we add one to that  we just get a power of two so we're  gonna zero out all these one bits and  then place a one here and this is  exactly the power of two that's greater  than the value n so the first line here  is essentially guaranteeing us that the  log n minus 1 bit is set and we need  that bit to be set because we want to  propagate that bit to all the positions  to the right of it and then these six  lines here are populating all of the  bits to the right with ones and then the  last bit is setting the log n bits 1 and  then clearing all of the other bits so  one question is why did we have to  decrement n at the beginning yes  yeah so if n is already a power of two  and if we don't decrement and this is  isn't gonna work because the log n minus  one bit isn't set but if we decrement n  then it's gonna guarantee us that the  law against minus one bit is set so that  we can propagate that to the right okay  any questions yes  because in general you have you're using  64-bit words here here I don't have that  many bits here because I can't fit it on  the slide but in general you have more  bits okay let's look at another problem  here we want to compute the mask of the  least significant one in a word X so we  want a mask that has a one and only the  position of the least significant one in  X and zeros everywhere else  so how can we do this so we can set our  the result equal to X and it with  negative x so let's look at why this  works say here is X and recall negative  X is is the two's complement of X plus  one so what we do is we flip all of the  bits up to the rightmost one but not  including it and then we just copy all  of the bits over that's how we get  negative X from X and then now we  compare X and negative x we see that all  the bits when we add them together are  going to be zero  except for the bit at the position  corresponding to the least significant 1  bit in X and that's going to be 1 since  we're anding 1 and 1 and everything else  is going to be 0 and this will give us  the mask that we want okay so this works  because the binary representation of  minus X is just the ones complement of X  plus 1  so now a question is how can we find the  index of this bit so here I'm just  generating a mass that has a 1 in the  least-significant 1 in X but it doesn't  actually tell me the index of this bit  bit in other words I want to find the  log base 2 of a power of 2 so that's the  problem we want to solve and here's some  code that lets us do this so we have  this constant called de bruyne it's  written in hex here and then we have  this table of size 64 called convert and  now all we have to do is multiply X by  this de bruyne constant right shifted by  58 positions and then look up the result  in the convert table and that's gonna  give us log base 2 of a power of 2 any  questions ok so this looks like magic to  us so in the spirit of magic we're gonna  do a math magic trick and to do this  trick I'm going to need five volunteers  in the only requirement is that you need  to be able to follow directions so who  wants to volunteer for this magic trick  yes one two three four one more fine all  right coming up so line up here yeah  just line up right here  I can move a little bit over to the left  okay cool so today I have the pleasure  of welcoming Jasser a also known as a  golden ratio to join us for lecture and  help us perform this cool magic trick so  let's give her a round of applause we'll  be doing a little bit of a magic trick  for you all today I'm gonna be reading  your guys's minds and I know you're  looking skeptical but I'm hoping I can  convince you here so we'll get to that  part in a second but first the first big  step in reading minds is you got to  clear the air like get rid of all the  negative vibes all the bad energy throw  that out so I'm gonna need a little help  from you guys and doing this so first we  have this sweet old Bell here let's say  who wants the Bell  all right can you hold that for a second  so what this Bell is gonna do is help us  get rid of some of those negative vibes  Mia it's gonna give it a ring oh yeah  so that painful ringing you're hearing  in your ears right now is actually just  clearing out the air for us making it so  I can read your minds thank you stop  that all right  next we have this magic tome here who  would like to give this a spin hey can  you a shake that around a couple times  in it go like this there we go  all right perfect all right it's feeling  a little clearer here I can start a can  start getting things off your minds  don't worry I won't tell anybody what  you're thinking oh let's see what else  let me channel the spirits  all right feeling good all right so what  we're gonna be doing is as I said  reading your mind I'm gonna be doing  this by giving you cards and I'm gonna  tell you what each of you are holding  for the card so I have some cards here I  guess either a little small let's see go  a little bigger yeah here we go  let's this looks better all right get  rid of these junk ones up here all right  so need your help for this so what I  want you to do is take the cards and cut  the deck as many times as you want so  basically just going like that however  much just don't actually like shuffle  them randomly all right cool  so now I'm gonna hand each of you a card  don't let me see it feel free to look at  it yeah all right so the reason I'm  wearing this awesome onesie is this  helps me sweat out the bad energy I'm  literally sweating right now but there's  one more piece that we need for this  mind-reading trick it's a magic hat all  right  see if it spits on my head there we go  where's the switch all right turn it on  all right feeling good here all right  you guys ready all right so I do need a  little help getting this trick started  so if you're holding a red card can you  just raise your hand so now who's got  the red card red Fred you don't have red  okay so all right so the first one and  the third one all right so let me I  channel the mind-reading abilities yeah  now what I'm gonna do is gonna go left  to right and tell you what you're  holding obviously I know the color but  I'll tell you what suit it is and also I  will tell you what the number is  so first card obviously I know you have  a red hmm  I'm feeling a diamond and also a for  yeah all right all right good start good  start  all right got a to think about what the  next one is here alright so I know you  got a black card let's see black of  Spades is it ace of spades oh yeah there  we go alright so back to red alright  this one let's see red diamond - alright  alright we're doing good so far can I  get the last two um all right let's see  what you can do here  all right black Club for alright last  one last one  alright it's gonna be a tough one black  Spade eight and if we had time I could  you know mystify you and go through the  rest of the deck but we won't do that so  thank you guys very much I hope your  minds were blown yeah me collect the  cards back from you  thank you all right thank you now I can  get out of this and stop sweating it's  pretty cool right so why does this  actually work to know why this trick  actually works we need to first study  what a de Bruyne sequence is so a de  Bruyne sequence s of length two to decay  is a cyclic bit sequence such that each  of the two to decay possible bit strings  of length K occurs exactly once as a  substring in s all right so this is a  pretty long definition so let's look at  an example so here's a de bruyne  sequence for K equals three so the  length of this sequence is 8 because 2  to the 3 is 8 and you can see that each  of the possible 3 bit substrings occurs  exactly once in this cyclic bit string  of length 8 so it wraps around at the  end you can consider this as a cyclic  string so we see that 0 0 0 appears at  position 0 0 0 1 is that position 1 that  0 1 0 is at position 6 0 1 one's at  position 2 1 0 0 is at position 7 1 0  ones at 5 1 1 0 is at 4 and then 1 1 1  is at 3 so all of the eight possible  substrings of length 3 occur exactly  once in this de bruyne sequence ok so  now we're going to create this convert  table of length 8 in general this will  be 2 to the K and here K is 3 and in  this convert table what we're storing in  each position is the index in the de  bruyne sequence where the bit string  corresponding to that position starts in  the in the  de Bruyne sequence so here we see that  convert of two is six because the bit  string corresponding to two is zero one  zero and that begins at position six in  the de Bruyne sequence we also see that  convert of four is seven because 4 is 1  0 0 and that begins at position 7 in the  de bruyne sequence now we have this  convert table and recall that we're  trying to compute the log base 2 of a  power of 2 so hopefully you guys  remember that so the way to do this is  we're going to multiply the de bruyne  sequence constant by this power of 2 so  let's say we're working with the integer  16 which is 2 2 4 so we're going to  multiply this de bruyne sequence by 2 to  the 4 and when we multiply by a power of  2 that's the same as left shifting so  that's going to laugh shift at the Broin  sequence for positions to the left and  then now we want to see which of the  eight possible sub strings appears at  the beginning of this sequence and after  we do the left shift 1 1 0 appears at  the beginning of the sequence and we  want to extract this out and we can do  that by right shifting 5 positions and 1  1 0 is just 6 and we can figure out  where 6 starts in this de bruyne  sequence by looking it up in the convert  table so we see that convert of 6 is 4  so the string 1 1 0 appears starting at  position 4 in the de bruyne sequence and  that means that we did a left shift by 4  in the first step and that gives us the  log base 2 of the power of 2 because the  only reason why we did a left shift by 4  is because the the power of 2 was 2 to  the 4 so this returns us to log base 2  of the integer that we started with and  one thing to notice is that it's  important to  start with all zeroes in this sequence  here because we're representing this as  a cyclic bit sequence so when we do a  left shift we need to make sure that the  values that fill in on the right side  are correct so notice that in the sixth  and seventh positions we need zeros at  the end when we overflow so because the  de bruyne sequence starts with all zeros  when we do the left shift is  automatically gonna fill in with zeros  giving us the correct substring so a  magic trick that just did had 32 cards  where and in that case K was equal to 5  and the cards were arranged according to  a de bruyne sequence of length 32 and  each of the cards correspond to one  particular bit string of length five and  the color of the card corresponding to  the bit so when she asked you what the  color of your card was she could  determine the the bits corresponding to  the first card in the sequence because  she has the five bits corresponding to  that card and with that she has some  clever way to determine the rest of the  cards so that's how the the Bruyne  sequence is related to the magic trick  that you just saw any questions yes  so there could be multiple de bruyne  sequence we just need one particular de  bruyne sequence to make this bit Rick  work yeah so this example was just for K  equals three I mean the code I showed  you before that was for K equals eight  so you can do up to 64 bit words yes so  there's a mathematical proof that says  that I can give you some pointers so  that you can look at it after class but  there's a proof that says that for any  length there is a de bruyne sequence yes  so so we have we're starting with some  integer that is a power of two so what  we multiply by that power of to its left  shifting by the log base two of that and  then we can determine how much we left  shifted because we know we can just look  at the first three bits of this sequence  after we did the left shift and then  look at where that 3-bit sequence  appears in the in the original de Bruyne  sequence before we shifted it and to do  that you can look it up in the convert  table this is what we did when we looked  up the bit string 1 1 0 in the convert  table and that tells us that it starts  in the 4th position that means that we  left shifted by 4 and that's that means  that the value of n was 2 to the 4 does  that make sense  yes so this only works if you're  starting with a power of 2 so if it's  not a power of 2 this doesn't work  any other questions yes if it's not a  power of two you can round it up to the  nearest power of two using another bit  trick that we saw earlier and then you  can use this bit trick here the  performance of this bit trick is limited  by the performance of multiplication and  table lookup so you have to do a  multiplication by some constant and then  you have to do table lookup in this  convert table so a table lookup does a  memory reference which could be  expensive and nowadays there's actually  a hardware instruction to compute this  so you don't actually have to implement  this trick but this trick is still  pretty cool cool and in the past this is  how you would do it before there was a  hardware instruction that came out okay  so let's look at another problem so this  is the N Queens problem how many of  you've seen this before yeah so many of  you have seen this before as a reminder  we're trying to place n Queens on an N  by n chess board so that no Queens  attacks another Queen in other words  there are no two Queens in any row any  column or any diagonal and commonly we  want to count the number of possible  solutions to the N Queens problem for a  particular value of n and in this  example here this is a valid  configuration you can check for each of  the Queens it can't attack any other  Queen on the board so one common  strategy for implementing the N Queens  algorithm is to use backtracking we're  gonna try placing Queens row by row we  know that there can only be one Queen  per row so we just need to determine  which position in that row the Queen  will appear in and then if we can't  place a queen in any row then we  backtrack so for example in the first  row we'll just place the Queen in the  first position because there's no Queens  on the board yet so the first position  is valid for the second row  we're gonna try to place in the first  position but we can't place it there  because then it will attack the first  Queen and then the second position is  also invalid so the third position is  where we place the second Queen now for  a third row we're going to check the  positions until we get to one that's  valid and this is going to be the fifth  position do this again here we can do it  in the second position for the fifth row  let's see where this this is going to  end off okay so it goes in the fourth  position what about the sixth row  so oops so all of the eight positions  are invalid because if we place the  Queen in any of those positions it's  going to attack one of the Queens that  we already placed so now we're going to  backtrack when you'll find another  position for the fifth Queen so let's  try some more positions okay so we can  place it at the end now we try again  all right so unfortunately we couldn't  find a position for the six row again we  have the backtrack but we already tried  all the positions in the fifth row so we  backtrack to the fourth row and you get  the idea  and then whenever we find a  configuration where all eight queens are  valid then we increment some counter by  one and at the end we just return this  counter which tells us the number of  solutions to the end Queens puzzle okay  so so you can implement this quite  easily using a recursive procedure you  can implement this backtracking search  but one question is how should we  represent the board to facilitate you  fish and queen placement so one way to  represent the board is to use an array  of n squared bytes and for each byte we  just have a one if there's a queen in  that position and zero otherwise is  there a better way to represent the  board  yeah so so that's a good answer so  instead of using bytes we can use bits  because the value can only be 0 1 we  only need one bit to represent that so  we can just have an array of n squared  bits is there a better way to do this  yes yes so good answers so a better way  to do this is to just use an array of n  bytes because we know that on each row  there can only be one Queen so we just  need to store the position of that Queen  so we have an array of and bytes one  byte for each row and then you just use  the byte to store the position of the  Queen in that row it turns out to  implement this algorithm there's a even  more compact representation which is to  use three bit vectors of size n - n  minus 1 + 2 n minus 1 so let's see how  this works  so the first bit vector we're gonna use  is of length n we're called gonna call  this the down vector and the down vector  just stores a 1 in the columns that have  a queen in it and 0 in the columns that  are empty and then when we when we want  to check whether placing a queen is safe  in any position we first have to check  whether that column is empty and you can  do this by anding the down bit vector  with one left shifted by C or C is the  column where you want to place the Queen  and if that's nonzero that means there's  already a queen and that call me you  can't place it otherwise we're gonna  have to do another check and we're gonna  create this other bit vector called left  the length of this back bit vector is 2n  minus 1 and it stores of 1 in the  diagonal that has a queen in it and  zeros otherwise and there are 2n minus 1  possible diagonals and then now when we  want to place a queen in row R and  column C we can check whether it's safe  by doing left and it with one left  shifted by R plus C and this is going to  be nonzero if there's already a queen in  that particular diagonal so in that case  we can't place the Queen there and  otherwise we're gonna do a final check  using this right bit vector which is  essentially the same but we're looking  at the diagonals going down to the right  so again we have a 1 in the diagonals  that have a queen and zeros otherwise  and then now the check is going to be  right and it with one left shifted by n  minus one minus R plus C and if a  particular candidate passes all three of  these checks then we know that there's  not going to be a conflict and we can  place the queen in that particular  position so this is a bit vector  representation you actually still have  to write the code to count the number of  Queens using this bit vector  representation and it's actually a  interesting exercise so I encourage you  to try to do this at home but I just  told you about the bit vector  representation send you questions yes  yeah so the down vector is stores a1 in  the columns I have a queen in it and  zeros otherwise and what you do is if  you want to place a queen in column C  you you first create the mask one left  shifted by C and then you and it with  the down vector and that's gonna be  nonzero if there's a queen in that  column all right any other questions yes  so it turns out that you don't need it  just these three checks is enough to  guarantee guarantee that you can place a  queen in a position if it passes all  three of the checks yes a fourth check  would just be redundant yeah that's true  good point yeah so we're only placing  one queen in each particular row all  right so let's look at another problem  this is called population count or pop  count for a short and the problem here  is we want to count the number of 1 bits  in some word X here's a way to do this  that repeatedly eliminates the least  significant 1 bit in the word so we have  this for loop where R is initialized to  0 and we're going to repeat this loop  until X becomes 0 and that each time we  go through this loop we increment our  and inside the loop we're going to set X  equal to X ANDed with X minus 1 and this  is going to clear the least-significant  one bit in X so let's look at an example  so let's say we have this value here for  X well to get X minus 1 we flip the  rightmost one bit in X from a 1 to 0 and  then we fill in all the bits the right  of that with one's and then now when we  end those things two things together  we're going to copy all of the bits up  to the rightmost one and then for the  rightmost one we're going to zero it out  because we're ending with a zero and  then all the bits the right of that are  still going to be 0 so X ended with X  minus 1 is  going to get rid of the least  significant one bit and then we repeat  this process until X becomes zero in  that case we've already eliminated all  the ones and we know the answer which is  stored in our questions okay so so this  code will be pretty fast if the number  of 1 bits is small but but the running  time is proportional to the number of 1  bits and the word so in the worst case  if most of the bits are set to 1 then  you're going to need a lot of iterations  to run this code so let's look at a more  efficient way to do this this is to use  table lookup so we're gonna create a  table of size 256 which stores for each  8-bit word the number of ones in that  8-bit word so we have all possible 8-bit  words stored in this table and then now  to get the number of 1 bits in X for  every 8-bit substring in X we're going  to look it up in this count table and  add it to our and then we're going to  write shift X by 8 so that we can get  the next word and then when X becomes 0  we know we're done so that's that's  table lookup and the performance here  depends on the size of X if we have a  64-bit word we need to do this at most 8  times whereas in the initial code we  might have to do it 64 times if we had  64 one bits the cost of this code is  bottlenecked by the memory operations  because this table here is stored in  memory so every time you access it you  have to go to memory to fetch the value  there and here are some approximate  costs for accessing memory and various  levels of the hierarchy  if something sorted in register it's  very fascinates you one cycle if it's  stored in l1 cache it's about 4 cycle  l2-cache about 10 cycles l3 cache about  50 cycles and then finally if you have  to go to DRAM because it's not in cache  it's much more expensive 150 cycles it's  an order of magnitude slower than doing  something fetching something that's  already stored in the register okay so  let's now look at a third way to do  population count where we don't actually  have to go to cache or drm essentially  we can do everything in registers so  here's how you do it so we're gonna  create these five mass or six mass from  m 0 up to m5 and these mass the values  of these masks are shown in the comments  here in this notation here X to the K  just means X repeated K times so the  mask m5 has 32 zeros followed by 32 ones  the mass m0 has the base ring 0 1  repeated 32 times and so on after we  create these mass we're going to execute  these sex instructions at the bottom and  this is going to give us the number of  ones in the word so let's do an example  to see how this works so let's say we  start with this bit string here in the  first in the first step what we're gonna  do is we're gonna and X with the mask m0  and then we're also going to and X right  shifted by 1 with the mask  m0 and recall that the mask M 0 is just  0 1 repeated 32 times and therefore the  mass is essentially extracting all the  even bits so X ANDed with m0 gives us  all the even bits and then when we write  shift X by 1 and end it with m0 that's  going to give us all the odd bits and  then we're gonna line those two things  up and add them together and the result  of doing this is it's going to tell us  for every group of two bits the number  of one bits in that group so now for  each of these pairs of bits is telling  us how  many of them were won so in the  left-most group here we had two ones so  the result of adding 1 & 1 is 1 0 which  is 2 for the rightmost group we have 2  zeros and the count there is 0 0 and  this is the same for all of the other  groups so this gives us the number of  ones in every pair of in every pair of  positions now we're gonna end and the  result with m1 and we're gonna right  shift it by 2 and also and it with m1  and add those two things together and m1  is a mass that will give us the bottom  two bits in every group of 4 bits so  when we write shift X by 2 that's giving  us the top two bits and then now we add  those together and it will give us the  count of the number of 1 bits in every  group of size 4 and these are the count  these counts are stored in the result  here now so you can verify that each of  these groups has the count of the number  of 1 bits so for example we have 1 0 0  here and this is correct since there are  4 1 bits now we do this again with the  mass m2 that's going to give us the  counts for all groups of size 8 do we go  to groups of size 16 and I finally we  add these two together giving us the  number of bits in this group of size 32  and this is actually the pop count so  the value here is 17 and you can verify  that there are indeed 17 1s in the input  word X any questions  so the performance of this code which is  based on a parallel divide-and-conquer  is going to be proportional to log base  two of W where W is the word length  because on every step I'm doubling the  size of my groups and after I do this  log base two of W times I have the whole  group in the first two instructions that  are executed here I have to actually do  the and separately for X right shifted  by one and X and also X right shifted by  two and X and then add them together  because there's an overflow issue the  overflow issue is that the size of the  groups here might not be large enough to  actually store the count of the number  of one bits in that group but once I get  to the larger groups the count can  always be stored in a group of that size  and I don't need to worry about overflow  so for the last four lines I can  actually save one instruction I don't  need to do the and twice  okay so it turns out that most modern  machines nowadays have an intrinsic pop  count instruction implemented in  hardware which is faster than anything  you can code yourself and you can access  this pop count instruction via compiler  intrinsics for example in GCC or clang  and in GCC it's underscore underscore  built-in underscore pop count one  warning though is that if you write this  code using these intrinsics  if you run if you try to compile the  code on a machine that doesn't support  it your code isn't going to compile so  it makes your code less portable but  this this intrinsic is faster than the  parallel divide-and-conquer version so  one question is how could get the log  base two of a power of two quickly using  a pop count instruction so instead of  using the de bruyne sequence trick yes  yes so what you do is you subtract one  from the power of two and that's gonna  flood off the lower bits with ones and  then now when you execute pop count it's  gonna count the number of ones and that  gives us the log base two of the power  of two so good answer all right so those  are all the bit tricks I'm gonna be  talking about today there's a lot of  resources online if you're interested in  learning more there's this really good  website maintained by Shawn Aaron  Anderson there's also the news textbook  which has some bit tricks in there  there's a chess programming website  which has a lot of cool bit tricks some  of those are used in implementing chess  programs and then finally this book  called hackers delight so you'll be  playing around with many of these bit  tricks in project one so happy bit  hacking  you
 

3
00:00:05,769 --> 00:00:08,019

 

4
00:00:08,019 --> 00:00:09,850

 

5
00:00:09,850 --> 00:00:10,930

 

6
00:00:10,930 --> 00:00:13,120

 

7
00:00:13,120 --> 00:00:15,160

 

8
00:00:15,160 --> 00:00:21,359

 

9
00:00:21,359 --> 00:00:24,760

 

10
00:00:24,760 --> 00:00:28,170

 

11
00:00:28,170 --> 00:00:30,880

 

12
00:00:30,880 --> 00:00:32,530

 

13
00:00:32,530 --> 00:00:37,690

 

14
00:00:37,690 --> 00:00:41,530

 

15
00:00:41,530 --> 00:00:45,460

 

16
00:00:45,460 --> 00:00:47,980

 

17
00:00:47,980 --> 00:00:51,160

 

18
00:00:51,160 --> 00:00:55,750

 

19
00:00:55,750 --> 00:00:57,760

 

20
00:00:57,760 --> 00:00:59,139

 

21
00:00:59,139 --> 00:01:01,600

 

22
00:01:01,600 --> 00:01:05,439

 

23
00:01:05,439 --> 00:01:08,410

 

24
00:01:08,410 --> 00:01:09,880

 

25
00:01:09,880 --> 00:01:12,730

 

26
00:01:12,730 --> 00:01:15,520

 

27
00:01:15,520 --> 00:01:17,560

 

28
00:01:17,560 --> 00:01:21,270

 

29
00:01:21,270 --> 00:01:25,690

 

30
00:01:25,690 --> 00:01:28,870

 

31
00:01:28,870 --> 00:01:32,440

 

32
00:01:32,440 --> 00:01:34,899

 

33
00:01:34,899 --> 00:01:37,950

 

34
00:01:37,950 --> 00:01:41,980

 

35
00:01:41,980 --> 00:01:46,179

 

36
00:01:46,179 --> 00:01:49,539

 

37
00:01:49,539 --> 00:01:53,830

 

38
00:01:53,830 --> 00:01:55,030

 

39
00:01:55,030 --> 00:01:57,249

 

40
00:01:57,249 --> 00:01:57,259

 

41
00:01:57,259 --> 00:02:00,570


42
00:02:00,570 --> 00:02:04,030

 

43
00:02:04,030 --> 00:02:05,859

 

44
00:02:05,859 --> 00:02:07,660

 

45
00:02:07,660 --> 00:02:09,849

 

46
00:02:09,849 --> 00:02:12,339

 

47
00:02:12,339 --> 00:02:14,080

 

48
00:02:14,080 --> 00:02:18,040

 

49
00:02:18,040 --> 00:02:20,170

 

50
00:02:20,170 --> 00:02:23,290

 

51
00:02:23,290 --> 00:02:27,760

 

52
00:02:27,760 --> 00:02:30,100

 

53
00:02:30,100 --> 00:02:36,309

 

54
00:02:36,309 --> 00:02:38,920

 

55
00:02:38,920 --> 00:02:41,680

 

56
00:02:41,680 --> 00:02:43,449

 

57
00:02:43,449 --> 00:02:46,390

 

58
00:02:46,390 --> 00:02:49,990

 

59
00:02:49,990 --> 00:02:54,190

 

60
00:02:54,190 --> 00:02:55,030

 

61
00:02:55,030 --> 00:03:01,050

 

62
00:03:01,050 --> 00:03:04,270

 

63
00:03:04,270 --> 00:03:08,110

 

64
00:03:08,110 --> 00:03:10,750

 

65
00:03:10,750 --> 00:03:13,360

 

66
00:03:13,360 --> 00:03:14,770

 

67
00:03:14,770 --> 00:03:17,650

 

68
00:03:17,650 --> 00:03:22,960

 

69
00:03:22,960 --> 00:03:25,960

 

70
00:03:25,960 --> 00:03:27,670

 

71
00:03:27,670 --> 00:03:31,809

 

72
00:03:31,809 --> 00:03:38,289

 

73
00:03:38,289 --> 00:03:41,949

 

74
00:03:41,949 --> 00:03:45,220

 

75
00:03:45,220 --> 00:03:48,759

 

76
00:03:48,759 --> 00:03:51,430

 

77
00:03:51,430 --> 00:03:54,460

 

78
00:03:54,460 --> 00:03:57,039

 

79
00:03:57,039 --> 00:03:59,559

 

80
00:03:59,559 --> 00:04:02,830

 

81
00:04:02,830 --> 00:04:05,680

 

82
00:04:05,680 --> 00:04:08,710

 

83
00:04:08,710 --> 00:04:11,020

 

84
00:04:11,020 --> 00:04:14,289

 

85
00:04:14,289 --> 00:04:17,020

 

86
00:04:17,020 --> 00:04:19,930

 

87
00:04:19,930 --> 00:04:23,740

 

88
00:04:23,740 --> 00:04:26,350

 

89
00:04:26,350 --> 00:04:29,140

 

90
00:04:29,140 --> 00:04:31,270

 

91
00:04:31,270 --> 00:04:34,300

 

92
00:04:34,300 --> 00:04:37,390

 

93
00:04:37,390 --> 00:04:40,360

 

94
00:04:40,360 --> 00:04:42,370

 

95
00:04:42,370 --> 00:04:44,350

 

96
00:04:44,350 --> 00:04:46,240

 

97
00:04:46,240 --> 00:04:48,940

 

98
00:04:48,940 --> 00:04:51,340

 

99
00:04:51,340 --> 00:04:53,530

 

100
00:04:53,530 --> 00:04:55,420

 

101
00:04:55,420 --> 00:04:58,630

 

102
00:04:58,630 --> 00:05:03,490

 

103
00:05:03,490 --> 00:05:06,100

 

104
00:05:06,100 --> 00:05:09,340

 

105
00:05:09,340 --> 00:05:13,180

 

106
00:05:13,180 --> 00:05:16,810

 

107
00:05:16,810 --> 00:05:19,030

 

108
00:05:19,030 --> 00:05:22,150

 

109
00:05:22,150 --> 00:05:25,180

 

110
00:05:25,180 --> 00:05:27,610

 

111
00:05:27,610 --> 00:05:30,430

 

112
00:05:30,430 --> 00:05:37,270

 

113
00:05:37,270 --> 00:05:39,640

 

114
00:05:39,640 --> 00:05:42,580

 

115
00:05:42,580 --> 00:05:44,890

 

116
00:05:44,890 --> 00:05:46,300

 

117
00:05:46,300 --> 00:05:57,649

 

118
00:05:57,649 --> 00:06:00,290

 

119
00:06:00,290 --> 00:06:03,679

 

120
00:06:03,679 --> 00:06:05,839

 

121
00:06:05,839 --> 00:06:10,760

 

122
00:06:10,760 --> 00:06:12,589

 

123
00:06:12,589 --> 00:06:14,899

 

124
00:06:14,899 --> 00:06:16,999

 

125
00:06:16,999 --> 00:06:19,669

 

126
00:06:19,669 --> 00:06:22,579

 

127
00:06:22,579 --> 00:06:26,059

 

128
00:06:26,059 --> 00:06:29,629

 

129
00:06:29,629 --> 00:06:33,199

 

130
00:06:33,199 --> 00:06:36,709

 

131
00:06:36,709 --> 00:06:38,899

 

132
00:06:38,899 --> 00:06:41,029

 

133
00:06:41,029 --> 00:06:47,570

 

134
00:06:47,570 --> 00:06:50,359

 

135
00:06:50,359 --> 00:06:52,730

 

136
00:06:52,730 --> 00:06:54,799

 

137
00:06:54,799 --> 00:06:58,309

 

138
00:06:58,309 --> 00:07:01,399

 

139
00:07:01,399 --> 00:07:04,069

 

140
00:07:04,069 --> 00:07:08,420

 

141
00:07:08,420 --> 00:07:11,359

 

142
00:07:11,359 --> 00:07:16,399

 

143
00:07:16,399 --> 00:07:19,159

 

144
00:07:19,159 --> 00:07:21,889

 

145
00:07:21,889 --> 00:07:23,600

 

146
00:07:23,600 --> 00:07:27,109

 

147
00:07:27,109 --> 00:07:28,909

 

148
00:07:28,909 --> 00:07:32,179

 

149
00:07:32,179 --> 00:07:37,699

 

150
00:07:37,699 --> 00:07:40,040

 

151
00:07:40,040 --> 00:07:42,829

 

152
00:07:42,829 --> 00:07:45,259

 

153
00:07:45,259 --> 00:07:47,059

 

154
00:07:47,059 --> 00:07:53,250

 

155
00:07:53,250 --> 00:07:57,060

 

156
00:07:57,060 --> 00:08:00,720

 

157
00:08:00,720 --> 00:08:02,670

 

158
00:08:02,670 --> 00:08:05,580

 

159
00:08:05,580 --> 00:08:09,660

 

160
00:08:09,660 --> 00:08:12,600

 

161
00:08:12,600 --> 00:08:16,230

 

162
00:08:16,230 --> 00:08:18,780

 

163
00:08:18,780 --> 00:08:22,050

 

164
00:08:22,050 --> 00:08:25,290

 

165
00:08:25,290 --> 00:08:29,460

 

166
00:08:29,460 --> 00:08:32,790

 

167
00:08:32,790 --> 00:08:36,780

 

168
00:08:36,780 --> 00:08:39,300

 

169
00:08:39,300 --> 00:08:41,250

 

170
00:08:41,250 --> 00:08:46,530

 

171
00:08:46,530 --> 00:08:49,200

 

172
00:08:49,200 --> 00:08:51,900

 

173
00:08:51,900 --> 00:08:56,160

 

174
00:08:56,160 --> 00:09:00,060

 

175
00:09:00,060 --> 00:09:06,150

 

176
00:09:06,150 --> 00:09:08,580

 

177
00:09:08,580 --> 00:09:10,590

 

178
00:09:10,590 --> 00:09:13,290

 

179
00:09:13,290 --> 00:09:15,690

 

180
00:09:15,690 --> 00:09:18,090

 

181
00:09:18,090 --> 00:09:21,090

 

182
00:09:21,090 --> 00:09:23,730

 

183
00:09:23,730 --> 00:09:29,040

 

184
00:09:29,040 --> 00:09:31,470

 

185
00:09:31,470 --> 00:09:36,180

 

186
00:09:36,180 --> 00:09:39,030

 

187
00:09:39,030 --> 00:09:42,660

 

188
00:09:42,660 --> 00:09:45,300

 

189
00:09:45,300 --> 00:09:49,530

 

190
00:09:49,530 --> 00:09:51,420

 

191
00:09:51,420 --> 00:09:54,480

 

192
00:09:54,480 --> 00:09:57,750

 

193
00:09:57,750 --> 00:09:59,670

 

194
00:09:59,670 --> 00:10:03,930

 

195
00:10:03,930 --> 00:10:07,139

 

196
00:10:07,139 --> 00:10:09,090

 

197
00:10:09,090 --> 00:10:11,369

 

198
00:10:11,369 --> 00:10:15,960

 

199
00:10:15,960 --> 00:10:32,420

 

200
00:10:32,420 --> 00:10:37,470

 

201
00:10:37,470 --> 00:10:40,019

 

202
00:10:40,019 --> 00:10:43,579

 

203
00:10:43,579 --> 00:10:46,530

 

204
00:10:46,530 --> 00:10:48,389

 

205
00:10:48,389 --> 00:10:50,009

 

206
00:10:50,009 --> 00:10:52,290

 

207
00:10:52,290 --> 00:10:54,720

 

208
00:10:54,720 --> 00:10:56,549

 

209
00:10:56,549 --> 00:11:04,410

 

210
00:11:04,410 --> 00:11:06,269

 

211
00:11:06,269 --> 00:11:08,369

 

212
00:11:08,369 --> 00:11:10,499

 

213
00:11:10,499 --> 00:11:13,619

 

214
00:11:13,619 --> 00:11:17,309

 

215
00:11:17,309 --> 00:11:21,379

 

216
00:11:21,379 --> 00:11:25,079

 

217
00:11:25,079 --> 00:11:26,879

 

218
00:11:26,879 --> 00:11:30,329

 

219
00:11:30,329 --> 00:11:32,100

 

220
00:11:32,100 --> 00:11:35,369

 

221
00:11:35,369 --> 00:11:38,249

 

222
00:11:38,249 --> 00:11:40,439

 

223
00:11:40,439 --> 00:11:42,059

 

224
00:11:42,059 --> 00:11:43,860

 

225
00:11:43,860 --> 00:11:45,269

 

226
00:11:45,269 --> 00:11:46,860

 

227
00:11:46,860 --> 00:11:52,499

 

228
00:11:52,499 --> 00:11:55,559

 

229
00:11:55,559 --> 00:11:57,840

 

230
00:11:57,840 --> 00:12:01,379

 

231
00:12:01,379 --> 00:12:03,059

 

232
00:12:03,059 --> 00:12:05,819

 

233
00:12:05,819 --> 00:12:07,530

 

234
00:12:07,530 --> 00:12:10,110

 

235
00:12:10,110 --> 00:12:14,879

 

236
00:12:14,879 --> 00:12:18,269

 

237
00:12:18,269 --> 00:12:19,919

 

238
00:12:19,919 --> 00:12:20,430

 

239
00:12:20,430 --> 00:12:23,160

 

240
00:12:23,160 --> 00:12:24,690

 

241
00:12:24,690 --> 00:12:25,320

 

242
00:12:25,320 --> 00:12:27,420

 

243
00:12:27,420 --> 00:12:29,070

 

244
00:12:29,070 --> 00:12:35,930

 

245
00:12:35,930 --> 00:12:39,270

 

246
00:12:39,270 --> 00:12:42,210

 

247
00:12:42,210 --> 00:12:44,610

 

248
00:12:44,610 --> 00:12:48,210

 

249
00:12:48,210 --> 00:12:50,130

 

250
00:12:50,130 --> 00:12:52,950

 

251
00:12:52,950 --> 00:12:56,520

 

252
00:12:56,520 --> 00:12:57,990

 

253
00:12:57,990 --> 00:12:59,700

 

254
00:12:59,700 --> 00:13:04,950

 

255
00:13:04,950 --> 00:13:15,320

 

256
00:13:15,320 --> 00:13:18,270

 

257
00:13:18,270 --> 00:13:21,570

 

258
00:13:21,570 --> 00:13:23,730

 

259
00:13:23,730 --> 00:13:27,810

 

260
00:13:27,810 --> 00:13:31,740

 

261
00:13:31,740 --> 00:13:34,890

 

262
00:13:34,890 --> 00:13:36,960

 

263
00:13:36,960 --> 00:13:40,320

 

264
00:13:40,320 --> 00:13:43,590

 

265
00:13:43,590 --> 00:13:45,480

 

266
00:13:45,480 --> 00:13:47,670

 

267
00:13:47,670 --> 00:13:49,470

 

268
00:13:49,470 --> 00:13:53,970

 

269
00:13:53,970 --> 00:13:56,310

 

270
00:13:56,310 --> 00:13:59,430

 

271
00:13:59,430 --> 00:14:01,260

 

272
00:14:01,260 --> 00:14:03,450

 

273
00:14:03,450 --> 00:14:08,940

 

274
00:14:08,940 --> 00:14:10,760

 

275
00:14:10,760 --> 00:14:13,770

 

276
00:14:13,770 --> 00:14:16,290

 

277
00:14:16,290 --> 00:14:19,200

 

278
00:14:19,200 --> 00:14:22,530

 

279
00:14:22,530 --> 00:14:22,540

 

280
00:14:22,540 --> 00:14:26,820


281
00:14:26,820 --> 00:14:30,210

 

282
00:14:30,210 --> 00:14:32,890

 

283
00:14:32,890 --> 00:14:37,090

 

284
00:14:37,090 --> 00:14:39,610

 

285
00:14:39,610 --> 00:14:42,370

 

286
00:14:42,370 --> 00:14:46,360

 

287
00:14:46,360 --> 00:14:49,960

 

288
00:14:49,960 --> 00:14:51,520

 

289
00:14:51,520 --> 00:14:53,230

 

290
00:14:53,230 --> 00:14:55,690

 

291
00:14:55,690 --> 00:15:01,030

 

292
00:15:01,030 --> 00:15:03,070

 

293
00:15:03,070 --> 00:15:05,260

 

294
00:15:05,260 --> 00:15:09,820

 

295
00:15:09,820 --> 00:15:11,530

 

296
00:15:11,530 --> 00:15:13,380

 

297
00:15:13,380 --> 00:15:15,780

 

298
00:15:15,780 --> 00:15:18,250

 

299
00:15:18,250 --> 00:15:23,200

 

300
00:15:23,200 --> 00:15:26,260

 

301
00:15:26,260 --> 00:15:28,480

 

302
00:15:28,480 --> 00:15:30,640

 

303
00:15:30,640 --> 00:15:33,640

 

304
00:15:33,640 --> 00:15:36,100

 

305
00:15:36,100 --> 00:15:45,670

 

306
00:15:45,670 --> 00:15:48,160

 

307
00:15:48,160 --> 00:15:50,140

 

308
00:15:50,140 --> 00:15:52,090

 

309
00:15:52,090 --> 00:15:55,620

 

310
00:15:55,620 --> 00:15:58,330

 

311
00:15:58,330 --> 00:16:00,160

 

312
00:16:00,160 --> 00:16:03,070

 

313
00:16:03,070 --> 00:16:05,290

 

314
00:16:05,290 --> 00:16:14,420

 

315
00:16:14,420 --> 00:16:22,160

 

316
00:16:22,160 --> 00:16:23,780

 

317
00:16:23,780 --> 00:16:25,610

 

318
00:16:25,610 --> 00:16:30,710

 

319
00:16:30,710 --> 00:16:33,440

 

320
00:16:33,440 --> 00:16:36,350

 

321
00:16:36,350 --> 00:16:42,080

 

322
00:16:42,080 --> 00:16:44,750

 

323
00:16:44,750 --> 00:16:46,730

 

324
00:16:46,730 --> 00:16:48,950

 

325
00:16:48,950 --> 00:16:52,670

 

326
00:16:52,670 --> 00:16:56,150

 

327
00:16:56,150 --> 00:16:59,870

 

328
00:16:59,870 --> 00:17:04,910

 

329
00:17:04,910 --> 00:17:08,660

 

330
00:17:08,660 --> 00:17:11,150

 

331
00:17:11,150 --> 00:17:12,920

 

332
00:17:12,920 --> 00:17:14,390

 

333
00:17:14,390 --> 00:17:18,470

 

334
00:17:18,470 --> 00:17:20,600

 

335
00:17:20,600 --> 00:17:23,630

 

336
00:17:23,630 --> 00:17:27,350

 

337
00:17:27,350 --> 00:17:31,430

 

338
00:17:31,430 --> 00:17:34,070

 

339
00:17:34,070 --> 00:17:36,170

 

340
00:17:36,170 --> 00:17:39,560

 

341
00:17:39,560 --> 00:17:43,400

 

342
00:17:43,400 --> 00:17:45,560

 

343
00:17:45,560 --> 00:17:48,850

 

344
00:17:48,850 --> 00:17:52,580

 

345
00:17:52,580 --> 00:17:57,050

 

346
00:17:57,050 --> 00:18:00,380

 

347
00:18:00,380 --> 00:18:04,610

 

348
00:18:04,610 --> 00:18:07,070

 

349
00:18:07,070 --> 00:18:09,860

 

350
00:18:09,860 --> 00:18:14,270

 

351
00:18:14,270 --> 00:18:17,450

 

352
00:18:17,450 --> 00:18:20,450

 

353
00:18:20,450 --> 00:18:23,090

 

354
00:18:23,090 --> 00:18:25,310

 

355
00:18:25,310 --> 00:18:27,170

 

356
00:18:27,170 --> 00:18:27,950

 

357
00:18:27,950 --> 00:18:31,119

 

358
00:18:31,119 --> 00:18:34,220

 

359
00:18:34,220 --> 00:18:37,489

 

360
00:18:37,489 --> 00:18:39,980

 

361
00:18:39,980 --> 00:18:44,210

 

362
00:18:44,210 --> 00:18:47,659

 

363
00:18:47,659 --> 00:18:52,279

 

364
00:18:52,279 --> 00:18:54,769

 

365
00:18:54,769 --> 00:19:00,649

 

366
00:19:00,649 --> 00:19:04,249

 

367
00:19:04,249 --> 00:19:06,830

 

368
00:19:06,830 --> 00:19:12,259

 

369
00:19:12,259 --> 00:19:14,720

 

370
00:19:14,720 --> 00:19:20,659

 

371
00:19:20,659 --> 00:19:23,509

 

372
00:19:23,509 --> 00:19:27,320

 

373
00:19:27,320 --> 00:19:29,509

 

374
00:19:29,509 --> 00:19:33,200

 

375
00:19:33,200 --> 00:19:35,330

 

376
00:19:35,330 --> 00:19:37,190

 

377
00:19:37,190 --> 00:19:38,659

 

378
00:19:38,659 --> 00:19:41,060

 

379
00:19:41,060 --> 00:19:43,730

 

380
00:19:43,730 --> 00:19:48,619

 

381
00:19:48,619 --> 00:19:51,980

 

382
00:19:51,980 --> 00:19:55,820

 

383
00:19:55,820 --> 00:19:57,980

 

384
00:19:57,980 --> 00:20:00,169

 

385
00:20:00,169 --> 00:20:01,999

 

386
00:20:01,999 --> 00:20:04,580

 

387
00:20:04,580 --> 00:20:08,840

 

388
00:20:08,840 --> 00:20:11,389

 

389
00:20:11,389 --> 00:20:15,289

 

390
00:20:15,289 --> 00:20:17,539

 

391
00:20:17,539 --> 00:20:21,470

 

392
00:20:21,470 --> 00:20:23,180

 

393
00:20:23,180 --> 00:20:25,009

 

394
00:20:25,009 --> 00:20:27,590

 

395
00:20:27,590 --> 00:20:31,039

 

396
00:20:31,039 --> 00:20:33,859

 

397
00:20:33,859 --> 00:20:36,019

 

398
00:20:36,019 --> 00:20:39,680

 

399
00:20:39,680 --> 00:20:43,540

 

400
00:20:43,540 --> 00:20:47,540

 

401
00:20:47,540 --> 00:20:58,520

 

402
00:20:58,520 --> 00:21:01,040

 

403
00:21:01,040 --> 00:21:02,810

 

404
00:21:02,810 --> 00:21:06,230

 

405
00:21:06,230 --> 00:21:08,090

 

406
00:21:08,090 --> 00:21:10,000

 

407
00:21:10,000 --> 00:21:13,370

 

408
00:21:13,370 --> 00:21:16,310

 

409
00:21:16,310 --> 00:21:18,530

 

410
00:21:18,530 --> 00:21:20,630

 

411
00:21:20,630 --> 00:21:22,600

 

412
00:21:22,600 --> 00:21:25,040

 

413
00:21:25,040 --> 00:21:27,410

 

414
00:21:27,410 --> 00:21:29,300

 

415
00:21:29,300 --> 00:21:31,760

 

416
00:21:31,760 --> 00:21:35,300

 

417
00:21:35,300 --> 00:21:37,910

 

418
00:21:37,910 --> 00:21:40,670

 

419
00:21:40,670 --> 00:21:42,110

 

420
00:21:42,110 --> 00:21:44,380

 

421
00:21:44,380 --> 00:21:51,070

 

422
00:21:51,070 --> 00:21:55,250

 

423
00:21:55,250 --> 00:21:58,010

 

424
00:21:58,010 --> 00:22:02,840

 

425
00:22:02,840 --> 00:22:04,910

 

426
00:22:04,910 --> 00:22:07,940

 

427
00:22:07,940 --> 00:22:11,270

 

428
00:22:11,270 --> 00:22:14,240

 

429
00:22:14,240 --> 00:22:17,900

 

430
00:22:17,900 --> 00:22:20,210

 

431
00:22:20,210 --> 00:22:22,400

 

432
00:22:22,400 --> 00:22:24,350

 

433
00:22:24,350 --> 00:22:30,860

 

434
00:22:30,860 --> 00:22:33,330

 

435
00:22:33,330 --> 00:22:35,240

 

436
00:22:35,240 --> 00:22:37,409

 

437
00:22:37,409 --> 00:22:40,320

 

438
00:22:40,320 --> 00:22:43,350

 

439
00:22:43,350 --> 00:22:46,019

 

440
00:22:46,019 --> 00:22:47,820

 

441
00:22:47,820 --> 00:22:49,590

 

442
00:22:49,590 --> 00:22:52,350

 

443
00:22:52,350 --> 00:22:55,889

 

444
00:22:55,889 --> 00:22:58,019

 

445
00:22:58,019 --> 00:23:00,180

 

446
00:23:00,180 --> 00:23:02,820

 

447
00:23:02,820 --> 00:23:05,060

 

448
00:23:05,060 --> 00:23:09,060

 

449
00:23:09,060 --> 00:23:10,889

 

450
00:23:10,889 --> 00:23:12,810

 

451
00:23:12,810 --> 00:23:15,060

 

452
00:23:15,060 --> 00:23:18,419

 

453
00:23:18,419 --> 00:23:23,850

 

454
00:23:23,850 --> 00:23:27,269

 

455
00:23:27,269 --> 00:23:31,740

 

456
00:23:31,740 --> 00:23:39,810

 

457
00:23:39,810 --> 00:23:44,009

 

458
00:23:44,009 --> 00:23:46,230

 

459
00:23:46,230 --> 00:23:48,180

 

460
00:23:48,180 --> 00:23:51,230

 

461
00:23:51,230 --> 00:23:54,029

 

462
00:23:54,029 --> 00:23:56,430

 

463
00:23:56,430 --> 00:23:58,080

 

464
00:23:58,080 --> 00:23:59,610

 

465
00:23:59,610 --> 00:24:02,850

 

466
00:24:02,850 --> 00:24:06,960

 

467
00:24:06,960 --> 00:24:08,789

 

468
00:24:08,789 --> 00:24:10,169

 

469
00:24:10,169 --> 00:24:12,360

 

470
00:24:12,360 --> 00:24:14,990

 

471
00:24:14,990 --> 00:24:18,590

 

472
00:24:18,590 --> 00:24:23,490

 

473
00:24:23,490 --> 00:24:26,249

 

474
00:24:26,249 --> 00:24:30,629

 

475
00:24:30,629 --> 00:24:35,009

 

476
00:24:35,009 --> 00:24:38,549

 

477
00:24:38,549 --> 00:24:40,379

 

478
00:24:40,379 --> 00:24:41,570

 

479
00:24:41,570 --> 00:24:47,440

 

480
00:24:47,440 --> 00:24:50,539

 

481
00:24:50,539 --> 00:24:53,629

 

482
00:24:53,629 --> 00:24:55,759

 

483
00:24:55,759 --> 00:24:59,720

 

484
00:24:59,720 --> 00:25:02,570

 

485
00:25:02,570 --> 00:25:05,810

 

486
00:25:05,810 --> 00:25:07,609

 

487
00:25:07,609 --> 00:25:21,470

 

488
00:25:21,470 --> 00:25:25,629

 

489
00:25:25,629 --> 00:25:28,659

 

490
00:25:28,659 --> 00:25:32,720

 

491
00:25:32,720 --> 00:25:37,129

 

492
00:25:37,129 --> 00:25:38,779

 

493
00:25:38,779 --> 00:25:40,460

 

494
00:25:40,460 --> 00:25:42,080

 

495
00:25:42,080 --> 00:25:45,950

 

496
00:25:45,950 --> 00:25:48,229

 

497
00:25:48,229 --> 00:25:50,720

 

498
00:25:50,720 --> 00:25:53,119

 

499
00:25:53,119 --> 00:25:56,299

 

500
00:25:56,299 --> 00:26:01,310

 

501
00:26:01,310 --> 00:26:08,330

 

502
00:26:08,330 --> 00:26:10,450

 

503
00:26:10,450 --> 00:26:12,799

 

504
00:26:12,799 --> 00:26:15,789

 

505
00:26:15,789 --> 00:26:18,680

 

506
00:26:18,680 --> 00:26:20,960

 

507
00:26:20,960 --> 00:26:22,430

 

508
00:26:22,430 --> 00:26:24,979

 

509
00:26:24,979 --> 00:26:27,200

 

510
00:26:27,200 --> 00:26:28,700

 

511
00:26:28,700 --> 00:26:31,129

 

512
00:26:31,129 --> 00:26:37,129

 

513
00:26:37,129 --> 00:26:40,759

 

514
00:26:40,759 --> 00:26:43,909

 

515
00:26:43,909 --> 00:26:46,070

 

516
00:26:46,070 --> 00:26:49,999

 

517
00:26:49,999 --> 00:26:51,980

 

518
00:26:51,980 --> 00:26:54,590

 

519
00:26:54,590 --> 00:26:55,370

 

520
00:26:55,370 --> 00:26:58,010

 

521
00:26:58,010 --> 00:26:59,930

 

522
00:26:59,930 --> 00:27:02,360

 

523
00:27:02,360 --> 00:27:04,970

 

524
00:27:04,970 --> 00:27:06,800

 

525
00:27:06,800 --> 00:27:10,520

 

526
00:27:10,520 --> 00:27:13,750

 

527
00:27:13,750 --> 00:27:16,430

 

528
00:27:16,430 --> 00:27:19,670

 

529
00:27:19,670 --> 00:27:23,360

 

530
00:27:23,360 --> 00:27:25,070

 

531
00:27:25,070 --> 00:27:28,670

 

532
00:27:28,670 --> 00:27:30,800

 

533
00:27:30,800 --> 00:27:32,300

 

534
00:27:32,300 --> 00:27:34,250

 

535
00:27:34,250 --> 00:27:36,350

 

536
00:27:36,350 --> 00:27:39,490

 

537
00:27:39,490 --> 00:27:42,170

 

538
00:27:42,170 --> 00:27:44,680

 

539
00:27:44,680 --> 00:27:47,390

 

540
00:27:47,390 --> 00:27:51,490

 

541
00:27:51,490 --> 00:27:54,560

 

542
00:27:54,560 --> 00:27:57,160

 

543
00:27:57,160 --> 00:28:00,020

 

544
00:28:00,020 --> 00:28:02,660

 

545
00:28:02,660 --> 00:28:05,780

 

546
00:28:05,780 --> 00:28:08,270

 

547
00:28:08,270 --> 00:28:10,190

 

548
00:28:10,190 --> 00:28:12,020

 

549
00:28:12,020 --> 00:28:13,430

 

550
00:28:13,430 --> 00:28:15,110

 

551
00:28:15,110 --> 00:28:19,490

 

552
00:28:19,490 --> 00:28:22,670

 

553
00:28:22,670 --> 00:28:25,190

 

554
00:28:25,190 --> 00:28:28,820

 

555
00:28:28,820 --> 00:28:31,420

 

556
00:28:31,420 --> 00:28:35,440

 

557
00:28:35,440 --> 00:28:38,570

 

558
00:28:38,570 --> 00:28:40,880

 

559
00:28:40,880 --> 00:28:43,700

 

560
00:28:43,700 --> 00:28:45,920

 

561
00:28:45,920 --> 00:28:47,450

 

562
00:28:47,450 --> 00:28:50,030

 

563
00:28:50,030 --> 00:28:55,640

 

564
00:28:55,640 --> 00:28:57,890

 

565
00:28:57,890 --> 00:29:03,740

 

566
00:29:03,740 --> 00:29:05,300

 

567
00:29:05,300 --> 00:29:08,180

 

568
00:29:08,180 --> 00:29:08,190

 

569
00:29:08,190 --> 00:29:08,780


570
00:29:08,780 --> 00:29:11,840

 

571
00:29:11,840 --> 00:29:14,540

 

572
00:29:14,540 --> 00:29:16,670

 

573
00:29:16,670 --> 00:29:18,890

 

574
00:29:18,890 --> 00:29:20,870

 

575
00:29:20,870 --> 00:29:22,580

 

576
00:29:22,580 --> 00:29:26,240

 

577
00:29:26,240 --> 00:29:28,910

 

578
00:29:28,910 --> 00:29:44,690

 

579
00:29:44,690 --> 00:29:46,730

 

580
00:29:46,730 --> 00:29:48,620

 

581
00:29:48,620 --> 00:29:51,350

 

582
00:29:51,350 --> 00:29:53,420

 

583
00:29:53,420 --> 00:29:55,370

 

584
00:29:55,370 --> 00:29:57,200

 

585
00:29:57,200 --> 00:29:59,690

 

586
00:29:59,690 --> 00:30:02,150

 

587
00:30:02,150 --> 00:30:05,090

 

588
00:30:05,090 --> 00:30:11,150

 

589
00:30:11,150 --> 00:30:17,840

 

590
00:30:17,840 --> 00:30:20,669

 

591
00:30:20,669 --> 00:30:36,980

 

592
00:30:36,980 --> 00:30:39,030

 

593
00:30:39,030 --> 00:30:40,590

 

594
00:30:40,590 --> 00:30:47,340

 

595
00:30:47,340 --> 00:30:49,289

 

596
00:30:49,289 --> 00:30:52,110

 

597
00:30:52,110 --> 00:30:53,669

 

598
00:30:53,669 --> 00:30:56,070

 

599
00:30:56,070 --> 00:30:58,710

 

600
00:30:58,710 --> 00:31:00,600

 

601
00:31:00,600 --> 00:31:14,780

 

602
00:31:14,780 --> 00:31:18,360

 

603
00:31:18,360 --> 00:31:20,370

 

604
00:31:20,370 --> 00:31:21,900

 

605
00:31:21,900 --> 00:31:23,820

 

606
00:31:23,820 --> 00:31:26,039

 

607
00:31:26,039 --> 00:31:28,740

 

608
00:31:28,740 --> 00:31:31,230

 

609
00:31:31,230 --> 00:31:35,310

 

610
00:31:35,310 --> 00:31:36,830

 

611
00:31:36,830 --> 00:31:39,690

 

612
00:31:39,690 --> 00:31:41,730

 

613
00:31:41,730 --> 00:31:45,360

 

614
00:31:45,360 --> 00:31:47,520

 

615
00:31:47,520 --> 00:31:51,960

 

616
00:31:51,960 --> 00:31:54,200

 

617
00:31:54,200 --> 00:31:56,280

 

618
00:31:56,280 --> 00:32:00,390

 

619
00:32:00,390 --> 00:32:02,070

 

620
00:32:02,070 --> 00:32:04,530

 

621
00:32:04,530 --> 00:32:07,140

 

622
00:32:07,140 --> 00:32:11,070

 

623
00:32:11,070 --> 00:32:14,460

 

624
00:32:14,460 --> 00:32:16,350

 

625
00:32:16,350 --> 00:32:21,510

 

626
00:32:21,510 --> 00:32:24,060

 

627
00:32:24,060 --> 00:32:26,120

 

628
00:32:26,120 --> 00:32:28,409

 

629
00:32:28,409 --> 00:32:32,430

 

630
00:32:32,430 --> 00:32:34,680

 

631
00:32:34,680 --> 00:32:37,650

 

632
00:32:37,650 --> 00:32:39,620

 

633
00:32:39,620 --> 00:32:43,200

 

634
00:32:43,200 --> 00:32:45,060

 

635
00:32:45,060 --> 00:32:49,049

 

636
00:32:49,049 --> 00:32:49,059

 

637
00:32:49,059 --> 00:32:50,080


638
00:32:50,080 --> 00:32:52,810

 

639
00:32:52,810 --> 00:32:55,359

 

640
00:32:55,359 --> 00:32:58,089

 

641
00:32:58,089 --> 00:33:00,969

 

642
00:33:00,969 --> 00:33:03,430

 

643
00:33:03,430 --> 00:33:05,200

 

644
00:33:05,200 --> 00:33:07,719

 

645
00:33:07,719 --> 00:33:12,219

 

646
00:33:12,219 --> 00:33:14,139

 

647
00:33:14,139 --> 00:33:15,820

 

648
00:33:15,820 --> 00:33:19,479

 

649
00:33:19,479 --> 00:33:25,839

 

650
00:33:25,839 --> 00:33:27,299

 

651
00:33:27,299 --> 00:33:32,729

 

652
00:33:32,729 --> 00:33:35,529

 

653
00:33:35,529 --> 00:33:37,289

 

654
00:33:37,289 --> 00:33:40,089

 

655
00:33:40,089 --> 00:33:44,229

 

656
00:33:44,229 --> 00:33:46,810

 

657
00:33:46,810 --> 00:33:48,459

 

658
00:33:48,459 --> 00:33:50,829

 

659
00:33:50,829 --> 00:33:54,159

 

660
00:33:54,159 --> 00:33:56,289

 

661
00:33:56,289 --> 00:33:58,180

 

662
00:33:58,180 --> 00:34:01,690

 

663
00:34:01,690 --> 00:34:04,959

 

664
00:34:04,959 --> 00:34:06,820

 

665
00:34:06,820 --> 00:34:09,819

 

666
00:34:09,819 --> 00:34:12,250

 

667
00:34:12,250 --> 00:34:14,049

 

668
00:34:14,049 --> 00:34:15,549

 

669
00:34:15,549 --> 00:34:19,869

 

670
00:34:19,869 --> 00:34:22,269

 

671
00:34:22,269 --> 00:34:24,789

 

672
00:34:24,789 --> 00:34:26,649

 

673
00:34:26,649 --> 00:34:29,019

 

674
00:34:29,019 --> 00:34:30,730

 

675
00:34:30,730 --> 00:34:33,369

 

676
00:34:33,369 --> 00:34:35,710

 

677
00:34:35,710 --> 00:34:37,510

 

678
00:34:37,510 --> 00:34:39,190

 

679
00:34:39,190 --> 00:34:41,230

 

680
00:34:41,230 --> 00:34:42,879

 

681
00:34:42,879 --> 00:34:46,569

 

682
00:34:46,569 --> 00:34:48,460

 

683
00:34:48,460 --> 00:34:51,399

 

684
00:34:51,399 --> 00:34:53,889

 

685
00:34:53,889 --> 00:34:56,289

 

686
00:34:56,289 --> 00:34:58,420

 

687
00:34:58,420 --> 00:34:59,950

 

688
00:34:59,950 --> 00:35:02,890

 

689
00:35:02,890 --> 00:35:03,880

 

690
00:35:03,880 --> 00:35:07,029

 

691
00:35:07,029 --> 00:35:10,989

 

692
00:35:10,989 --> 00:35:12,759

 

693
00:35:12,759 --> 00:35:15,069

 

694
00:35:15,069 --> 00:35:16,479

 

695
00:35:16,479 --> 00:35:20,349

 

696
00:35:20,349 --> 00:35:23,289

 

697
00:35:23,289 --> 00:35:27,099

 

698
00:35:27,099 --> 00:35:30,849

 

699
00:35:30,849 --> 00:35:34,269

 

700
00:35:34,269 --> 00:35:37,359

 

701
00:35:37,359 --> 00:35:40,420

 

702
00:35:40,420 --> 00:35:42,910

 

703
00:35:42,910 --> 00:35:47,499

 

704
00:35:47,499 --> 00:35:49,569

 

705
00:35:49,569 --> 00:35:51,670

 

706
00:35:51,670 --> 00:35:54,130

 

707
00:35:54,130 --> 00:35:56,620

 

708
00:35:56,620 --> 00:35:59,049

 

709
00:35:59,049 --> 00:36:02,170

 

710
00:36:02,170 --> 00:36:07,089

 

711
00:36:07,089 --> 00:36:08,859

 

712
00:36:08,859 --> 00:36:12,880

 

713
00:36:12,880 --> 00:36:15,819

 

714
00:36:15,819 --> 00:36:18,579

 

715
00:36:18,579 --> 00:36:21,819

 

716
00:36:21,819 --> 00:36:23,979

 

717
00:36:23,979 --> 00:36:25,660

 

718
00:36:25,660 --> 00:36:28,390

 

719
00:36:28,390 --> 00:36:30,579

 

720
00:36:30,579 --> 00:36:34,289

 

721
00:36:34,289 --> 00:36:36,849

 

722
00:36:36,849 --> 00:36:38,109

 

723
00:36:38,109 --> 00:36:42,309

 

724
00:36:42,309 --> 00:36:45,549

 

725
00:36:45,549 --> 00:36:47,710

 

726
00:36:47,710 --> 00:36:51,549

 

727
00:36:51,549 --> 00:36:57,220

 

728
00:36:57,220 --> 00:37:00,549

 

729
00:37:00,549 --> 00:37:02,710

 

730
00:37:02,710 --> 00:37:06,609

 

731
00:37:06,609 --> 00:37:09,430

 

732
00:37:09,430 --> 00:37:11,470

 

733
00:37:11,470 --> 00:37:14,470

 

734
00:37:14,470 --> 00:37:17,650

 

735
00:37:17,650 --> 00:37:19,150

 

736
00:37:19,150 --> 00:37:37,870

 

737
00:37:37,870 --> 00:37:40,329

 

738
00:37:40,329 --> 00:37:42,309

 

739
00:37:42,309 --> 00:37:44,230

 

740
00:37:44,230 --> 00:37:45,819

 

741
00:37:45,819 --> 00:37:49,390

 

742
00:37:49,390 --> 00:37:50,920

 

743
00:37:50,920 --> 00:37:52,720

 

744
00:37:52,720 --> 00:37:54,279

 

745
00:37:54,279 --> 00:37:57,069

 

746
00:37:57,069 --> 00:38:03,220

 

747
00:38:03,220 --> 00:38:06,910

 

748
00:38:06,910 --> 00:38:08,980

 

749
00:38:08,980 --> 00:38:12,730

 

750
00:38:12,730 --> 00:38:16,299

 

751
00:38:16,299 --> 00:38:18,640

 

752
00:38:18,640 --> 00:38:22,289

 

753
00:38:22,289 --> 00:38:27,010

 

754
00:38:27,010 --> 00:38:28,750

 

755
00:38:28,750 --> 00:38:32,440

 

756
00:38:32,440 --> 00:38:34,960

 

757
00:38:34,960 --> 00:38:37,480

 

758
00:38:37,480 --> 00:38:40,630

 

759
00:38:40,630 --> 00:38:43,839

 

760
00:38:43,839 --> 00:38:46,839

 

761
00:38:46,839 --> 00:38:49,150

 

762
00:38:49,150 --> 00:38:52,480

 

763
00:38:52,480 --> 00:38:57,339

 

764
00:38:57,339 --> 00:39:00,279

 

765
00:39:00,279 --> 00:39:03,069

 

766
00:39:03,069 --> 00:39:05,620

 

767
00:39:05,620 --> 00:39:10,750

 

768
00:39:10,750 --> 00:39:14,710

 

769
00:39:14,710 --> 00:39:16,180

 

770
00:39:16,180 --> 00:39:18,370

 

771
00:39:18,370 --> 00:39:20,109

 

772
00:39:20,109 --> 00:39:23,019

 

773
00:39:23,019 --> 00:39:25,510

 

774
00:39:25,510 --> 00:39:27,430

 

775
00:39:27,430 --> 00:39:29,049

 

776
00:39:29,049 --> 00:39:31,420

 

777
00:39:31,420 --> 00:39:35,440

 

778
00:39:35,440 --> 00:39:37,150

 

779
00:39:37,150 --> 00:39:41,620

 

780
00:39:41,620 --> 00:39:44,109

 

781
00:39:44,109 --> 00:39:47,589

 

782
00:39:47,589 --> 00:39:49,780

 

783
00:39:49,780 --> 00:39:53,260

 

784
00:39:53,260 --> 00:39:56,260

 

785
00:39:56,260 --> 00:39:58,270

 

786
00:39:58,270 --> 00:40:01,569

 

787
00:40:01,569 --> 00:40:05,260

 

788
00:40:05,260 --> 00:40:08,020

 

789
00:40:08,020 --> 00:40:10,630

 

790
00:40:10,630 --> 00:40:12,250

 

791
00:40:12,250 --> 00:40:14,950

 

792
00:40:14,950 --> 00:40:16,809

 

793
00:40:16,809 --> 00:40:19,990

 

794
00:40:19,990 --> 00:40:30,309

 

795
00:40:30,309 --> 00:40:33,400

 

796
00:40:33,400 --> 00:40:36,010

 

797
00:40:36,010 --> 00:40:38,049

 

798
00:40:38,049 --> 00:40:40,750

 

799
00:40:40,750 --> 00:40:44,859

 

800
00:40:44,859 --> 00:40:47,020

 

801
00:40:47,020 --> 00:40:50,260

 

802
00:40:50,260 --> 00:40:53,680

 

803
00:40:53,680 --> 00:40:58,510

 

804
00:40:58,510 --> 00:41:00,099

 

805
00:41:00,099 --> 00:41:08,060

 

806
00:41:08,060 --> 00:41:10,900

 

807
00:41:10,900 --> 00:41:13,370

 

808
00:41:13,370 --> 00:41:15,410

 

809
00:41:15,410 --> 00:41:18,380

 

810
00:41:18,380 --> 00:41:21,110

 

811
00:41:21,110 --> 00:41:22,970

 

812
00:41:22,970 --> 00:41:28,190

 

813
00:41:28,190 --> 00:41:34,180

 

814
00:41:34,180 --> 00:41:36,759

 

815
00:41:36,759 --> 00:41:40,539

 

816
00:41:40,539 --> 00:41:42,759

 

817
00:41:42,759 --> 00:41:44,109

 

818
00:41:44,109 --> 00:41:52,509

 

819
00:41:52,509 --> 00:41:55,089

 

820
00:41:55,089 --> 00:41:59,140

 

821
00:41:59,140 --> 00:42:01,210

 

822
00:42:01,210 --> 00:42:03,279

 

823
00:42:03,279 --> 00:42:05,160

 

824
00:42:05,160 --> 00:42:09,400

 

825
00:42:09,400 --> 00:42:11,650

 

826
00:42:11,650 --> 00:42:16,809

 

827
00:42:16,809 --> 00:42:21,970

 

828
00:42:21,970 --> 00:42:26,620

 

829
00:42:26,620 --> 00:42:29,829

 

830
00:42:29,829 --> 00:42:33,940

 

831
00:42:33,940 --> 00:42:35,650

 

832
00:42:35,650 --> 00:42:37,210

 

833
00:42:37,210 --> 00:42:41,589

 

834
00:42:41,589 --> 00:42:45,160

 

835
00:42:45,160 --> 00:42:47,349

 

836
00:42:47,349 --> 00:42:48,180

 

837
00:42:48,180 --> 00:42:52,359

 

838
00:42:52,359 --> 00:42:54,099

 

839
00:42:54,099 --> 00:42:56,859

 

840
00:42:56,859 --> 00:42:59,109

 

841
00:42:59,109 --> 00:43:01,359

 

842
00:43:01,359 --> 00:43:07,599

 

843
00:43:07,599 --> 00:43:09,339

 

844
00:43:09,339 --> 00:43:12,519

 

845
00:43:12,519 --> 00:43:18,700

 

846
00:43:18,700 --> 00:43:21,700

 

847
00:43:21,700 --> 00:43:24,040

 

848
00:43:24,040 --> 00:43:27,360

 

849
00:43:27,360 --> 00:43:31,000

 

850
00:43:31,000 --> 00:43:32,590

 

851
00:43:32,590 --> 00:43:34,390

 

852
00:43:34,390 --> 00:43:40,420

 

853
00:43:40,420 --> 00:43:42,790

 

854
00:43:42,790 --> 00:43:46,690

 

855
00:43:46,690 --> 00:43:49,300

 

856
00:43:49,300 --> 00:43:52,240

 

857
00:43:52,240 --> 00:43:56,830

 

858
00:43:56,830 --> 00:43:59,710

 

859
00:43:59,710 --> 00:44:02,410

 

860
00:44:02,410 --> 00:44:05,200

 

861
00:44:05,200 --> 00:44:07,120

 

862
00:44:07,120 --> 00:44:10,960

 

863
00:44:10,960 --> 00:44:20,530

 

864
00:44:20,530 --> 00:44:23,290

 

865
00:44:23,290 --> 00:44:26,110

 

866
00:44:26,110 --> 00:44:28,600

 

867
00:44:28,600 --> 00:44:30,850

 

868
00:44:30,850 --> 00:44:33,400

 

869
00:44:33,400 --> 00:44:35,040

 

870
00:44:35,040 --> 00:44:45,550

 

871
00:44:45,550 --> 00:44:52,600

 

872
00:44:52,600 --> 00:45:02,700

 

873
00:45:02,700 --> 00:45:07,370

 

874
00:45:07,370 --> 00:45:10,829

 

875
00:45:10,829 --> 00:45:13,859

 

876
00:45:13,859 --> 00:45:17,099

 

877
00:45:17,099 --> 00:45:19,620

 

878
00:45:19,620 --> 00:45:26,099

 

879
00:45:26,099 --> 00:45:27,329

 

880
00:45:27,329 --> 00:45:29,279

 

881
00:45:29,279 --> 00:45:32,099

 

882
00:45:32,099 --> 00:45:34,049

 

883
00:45:34,049 --> 00:45:37,079

 

884
00:45:37,079 --> 00:45:39,930

 

885
00:45:39,930 --> 00:45:41,700

 

886
00:45:41,700 --> 00:45:43,440

 

887
00:45:43,440 --> 00:45:45,930

 

888
00:45:45,930 --> 00:45:47,430

 

889
00:45:47,430 --> 00:45:51,630

 

890
00:45:51,630 --> 00:45:53,099

 

891
00:45:53,099 --> 00:45:54,440

 

892
00:45:54,440 --> 00:45:56,670

 

893
00:45:56,670 --> 00:45:58,380

 

894
00:45:58,380 --> 00:46:00,029

 

895
00:46:00,029 --> 00:46:03,089

 

896
00:46:03,089 --> 00:46:05,220

 

897
00:46:05,220 --> 00:46:06,779

 

898
00:46:06,779 --> 00:46:08,579

 

899
00:46:08,579 --> 00:46:11,099

 

900
00:46:11,099 --> 00:46:15,750

 

901
00:46:15,750 --> 00:46:19,500

 

902
00:46:19,500 --> 00:46:21,750

 

903
00:46:21,750 --> 00:46:22,829

 

904
00:46:22,829 --> 00:46:27,829

 

905
00:46:27,829 --> 00:46:31,650

 

906
00:46:31,650 --> 00:46:34,470

 

907
00:46:34,470 --> 00:46:35,849

 

908
00:46:35,849 --> 00:46:37,289

 

909
00:46:37,289 --> 00:46:40,370

 

910
00:46:40,370 --> 00:46:44,319

 

911
00:46:44,319 --> 00:46:49,339

 

912
00:46:49,339 --> 00:46:51,560

 

913
00:46:51,560 --> 00:46:52,730

 

914
00:46:52,730 --> 00:46:54,770

 

915
00:46:54,770 --> 00:46:56,329

 

916
00:46:56,329 --> 00:46:59,300

 

917
00:46:59,300 --> 00:47:03,560

 

918
00:47:03,560 --> 00:47:07,400

 

919
00:47:07,400 --> 00:47:17,510

 

920
00:47:17,510 --> 00:47:22,490

 

921
00:47:22,490 --> 00:47:25,849

 

922
00:47:25,849 --> 00:47:28,220

 

923
00:47:28,220 --> 00:47:29,569

 

924
00:47:29,569 --> 00:47:31,970

 

925
00:47:31,970 --> 00:47:33,950

 

926
00:47:33,950 --> 00:47:39,500

 

927
00:47:39,500 --> 00:47:41,690

 

928
00:47:41,690 --> 00:47:43,730

 

929
00:47:43,730 --> 00:47:54,230

 

930
00:47:54,230 --> 00:47:56,390

 

931
00:47:56,390 --> 00:47:58,790

 

932
00:47:58,790 --> 00:48:01,339

 

933
00:48:01,339 --> 00:48:02,900

 

934
00:48:02,900 --> 00:48:09,559

 

935
00:48:09,559 --> 00:48:09,569

 

936
00:48:09,569 --> 00:48:10,220


937
00:48:10,220 --> 00:48:12,770

 

938
00:48:12,770 --> 00:48:15,010

 

939
00:48:15,010 --> 00:48:17,839

 

940
00:48:17,839 --> 00:48:21,559

 

941
00:48:21,559 --> 00:48:23,420

 

942
00:48:23,420 --> 00:48:25,849

 

943
00:48:25,849 --> 00:48:31,760

 

944
00:48:31,760 --> 00:48:34,160

 

945
00:48:34,160 --> 00:48:37,400

 

946
00:48:37,400 --> 00:48:41,059

 

947
00:48:41,059 --> 00:48:42,559

 

948
00:48:42,559 --> 00:48:43,849

 

949
00:48:43,849 --> 00:48:45,079

 

950
00:48:45,079 --> 00:48:46,670

 

951
00:48:46,670 --> 00:48:49,069

 

952
00:48:49,069 --> 00:48:51,400

 

953
00:48:51,400 --> 00:48:54,200

 

954
00:48:54,200 --> 00:48:56,010

 

955
00:48:56,010 --> 00:49:00,440

 

956
00:49:00,440 --> 00:49:06,330

 

957
00:49:06,330 --> 00:49:06,340

 

958
00:49:06,340 --> 00:49:08,270


959
00:49:08,270 --> 00:49:11,520

 

960
00:49:11,520 --> 00:49:16,650

 

961
00:49:16,650 --> 00:49:22,280

 

962
00:49:22,280 --> 00:49:28,410

 

963
00:49:28,410 --> 00:49:39,450

 

964
00:49:39,450 --> 00:49:45,990

 

965
00:49:45,990 --> 00:49:47,940

 

966
00:49:47,940 --> 00:49:52,500

 

967
00:49:52,500 --> 00:49:53,190

 

968
00:49:53,190 --> 00:50:00,510

 

969
00:50:00,510 --> 00:50:03,740

 

970
00:50:03,740 --> 00:50:11,690

 

971
00:50:11,690 --> 00:50:22,470

 

972
00:50:22,470 --> 00:50:24,330

 

973
00:50:24,330 --> 00:50:27,750

 

974
00:50:27,750 --> 00:50:29,609

 

975
00:50:29,609 --> 00:50:33,960

 

976
00:50:33,960 --> 00:50:39,880

 

977
00:50:39,880 --> 00:50:42,700

 

978
00:50:42,700 --> 00:50:52,269

 

979
00:50:52,269 --> 00:50:57,220

 

980
00:50:57,220 --> 00:51:01,930

 

981
00:51:01,930 --> 00:51:04,269

 

982
00:51:04,269 --> 00:51:08,440

 

983
00:51:08,440 --> 00:51:11,079

 

984
00:51:11,079 --> 00:51:15,130

 

985
00:51:15,130 --> 00:51:18,579

 

986
00:51:18,579 --> 00:51:22,150

 

987
00:51:22,150 --> 00:51:25,839

 

988
00:51:25,839 --> 00:51:27,579

 

989
00:51:27,579 --> 00:51:29,589

 

990
00:51:29,589 --> 00:51:33,039

 

991
00:51:33,039 --> 00:51:35,500

 

992
00:51:35,500 --> 00:51:41,230

 

993
00:51:41,230 --> 00:51:45,009

 

994
00:51:45,009 --> 00:51:49,269

 

995
00:51:49,269 --> 00:51:51,609

 

996
00:51:51,609 --> 00:51:53,289

 

997
00:51:53,289 --> 00:51:58,390

 

998
00:51:58,390 --> 00:52:03,460

 

999
00:52:03,460 --> 00:52:06,940

 

1000
00:52:06,940 --> 00:52:13,210

 

1001
00:52:13,210 --> 00:52:18,400

 

1002
00:52:18,400 --> 00:52:21,460

 

1003
00:52:21,460 --> 00:52:24,370

 

1004
00:52:24,370 --> 00:52:31,200

 

1005
00:52:31,200 --> 00:52:33,640

 

1006
00:52:33,640 --> 00:52:37,269

 

1007
00:52:37,269 --> 00:52:40,299

 

1008
00:52:40,299 --> 00:52:42,549

 

1009
00:52:42,549 --> 00:52:47,079

 

1010
00:52:47,079 --> 00:52:49,480

 

1011
00:52:49,480 --> 00:52:52,480

 

1012
00:52:52,480 --> 00:52:53,260

 

1013
00:52:53,260 --> 00:52:55,720

 

1014
00:52:55,720 --> 00:52:59,740

 

1015
00:52:59,740 --> 00:53:01,900

 

1016
00:53:01,900 --> 00:53:04,300

 

1017
00:53:04,300 --> 00:53:06,820

 

1018
00:53:06,820 --> 00:53:11,050

 

1019
00:53:11,050 --> 00:53:13,840

 

1020
00:53:13,840 --> 00:53:18,340

 

1021
00:53:18,340 --> 00:53:21,970

 

1022
00:53:21,970 --> 00:53:24,640

 

1023
00:53:24,640 --> 00:53:26,920

 

1024
00:53:26,920 --> 00:53:32,980

 

1025
00:53:32,980 --> 00:53:35,170

 

1026
00:53:35,170 --> 00:53:39,430

 

1027
00:53:39,430 --> 00:53:41,830

 

1028
00:53:41,830 --> 00:53:43,720

 

1029
00:53:43,720 --> 00:53:46,150

 

1030
00:53:46,150 --> 00:53:48,850

 

1031
00:53:48,850 --> 00:53:52,930

 

1032
00:53:52,930 --> 00:53:54,460

 

1033
00:53:54,460 --> 00:53:58,599

 

1034
00:53:58,599 --> 00:54:00,660

 

1035
00:54:00,660 --> 00:54:03,760

 

1036
00:54:03,760 --> 00:54:06,040

 

1037
00:54:06,040 --> 00:54:08,770

 

1038
00:54:08,770 --> 00:54:12,190

 

1039
00:54:12,190 --> 00:54:13,810

 

1040
00:54:13,810 --> 00:54:18,040

 

1041
00:54:18,040 --> 00:54:22,450

 

1042
00:54:22,450 --> 00:54:24,940

 

1043
00:54:24,940 --> 00:54:26,710

 

1044
00:54:26,710 --> 00:54:30,640

 

1045
00:54:30,640 --> 00:54:36,130

 

1046
00:54:36,130 --> 00:54:38,500

 

1047
00:54:38,500 --> 00:54:41,380

 

1048
00:54:41,380 --> 00:54:44,230

 

1049
00:54:44,230 --> 00:54:46,930

 

1050
00:54:46,930 --> 00:54:49,210

 

1051
00:54:49,210 --> 00:54:52,480

 

1052
00:54:52,480 --> 00:54:56,680

 

1053
00:54:56,680 --> 00:55:02,530

 

1054
00:55:02,530 --> 00:55:04,930

 

1055
00:55:04,930 --> 00:55:06,319

 

1056
00:55:06,319 --> 00:55:08,599

 

1057
00:55:08,599 --> 00:55:10,579

 

1058
00:55:10,579 --> 00:55:15,019

 

1059
00:55:15,019 --> 00:55:18,079

 

1060
00:55:18,079 --> 00:55:19,549

 

1061
00:55:19,549 --> 00:55:23,179

 

1062
00:55:23,179 --> 00:55:26,719

 

1063
00:55:26,719 --> 00:55:31,249

 

1064
00:55:31,249 --> 00:55:32,799

 

1065
00:55:32,799 --> 00:55:34,579

 

1066
00:55:34,579 --> 00:55:35,839

 

1067
00:55:35,839 --> 00:55:39,289

 

1068
00:55:39,289 --> 00:55:42,949

 

1069
00:55:42,949 --> 00:55:45,759

 

1070
00:55:45,759 --> 00:55:49,640

 

1071
00:55:49,640 --> 00:55:53,239

 

1072
00:55:53,239 --> 00:55:56,599

 

1073
00:55:56,599 --> 00:55:59,949

 

1074
00:55:59,949 --> 00:56:02,989

 

1075
00:56:02,989 --> 00:56:06,559

 

1076
00:56:06,559 --> 00:56:09,289

 

1077
00:56:09,289 --> 00:56:11,900

 

1078
00:56:11,900 --> 00:56:15,319

 

1079
00:56:15,319 --> 00:56:17,479

 

1080
00:56:17,479 --> 00:56:20,809

 

1081
00:56:20,809 --> 00:56:23,929

 

1082
00:56:23,929 --> 00:56:25,759

 

1083
00:56:25,759 --> 00:56:28,099

 

1084
00:56:28,099 --> 00:56:40,210

 

1085
00:56:40,210 --> 00:56:42,680

 

1086
00:56:42,680 --> 00:56:44,990

 

1087
00:56:44,990 --> 00:56:46,640

 

1088
00:56:46,640 --> 00:56:54,020

 

1089
00:56:54,020 --> 00:56:56,180

 

1090
00:56:56,180 --> 00:57:00,350

 

1091
00:57:00,350 --> 00:57:08,030

 

1092
00:57:08,030 --> 00:57:09,920

 

1093
00:57:09,920 --> 00:57:13,040

 

1094
00:57:13,040 --> 00:57:14,660

 

1095
00:57:14,660 --> 00:57:16,990

 

1096
00:57:16,990 --> 00:57:28,540

 

1097
00:57:28,540 --> 00:57:34,040

 

1098
00:57:34,040 --> 00:57:37,670

 

1099
00:57:37,670 --> 00:57:40,820

 

1100
00:57:40,820 --> 00:57:43,760

 

1101
00:57:43,760 --> 00:57:47,030

 

1102
00:57:47,030 --> 00:57:51,290

 

1103
00:57:51,290 --> 00:57:53,780

 

1104
00:57:53,780 --> 00:57:55,910

 

1105
00:57:55,910 --> 00:57:57,740

 

1106
00:57:57,740 --> 00:58:01,880

 

1107
00:58:01,880 --> 00:58:04,880

 

1108
00:58:04,880 --> 00:58:06,380

 

1109
00:58:06,380 --> 00:58:09,050

 

1110
00:58:09,050 --> 00:58:11,960

 

1111
00:58:11,960 --> 00:58:14,150

 

1112
00:58:14,150 --> 00:58:16,010

 

1113
00:58:16,010 --> 00:58:19,460

 

1114
00:58:19,460 --> 00:58:23,660

 

1115
00:58:23,660 --> 00:58:24,700

 

1116
00:58:24,700 --> 00:58:34,160

 

1117
00:58:34,160 --> 00:58:36,440

 

1118
00:58:36,440 --> 00:58:45,760

 

1119
00:58:45,760 --> 00:58:52,370

 

1120
00:58:52,370 --> 00:58:54,289

 

1121
00:58:54,289 --> 00:58:56,120

 

1122
00:58:56,120 --> 00:58:57,890

 

1123
00:58:57,890 --> 00:59:02,480

 

1124
00:59:02,480 --> 00:59:05,720

 

1125
00:59:05,720 --> 00:59:07,519

 

1126
00:59:07,519 --> 00:59:10,569

 

1127
00:59:10,569 --> 00:59:14,210

 

1128
00:59:14,210 --> 00:59:15,650

 

1129
00:59:15,650 --> 00:59:19,279

 

1130
00:59:19,279 --> 00:59:20,809

 

1131
00:59:20,809 --> 00:59:23,000

 

1132
00:59:23,000 --> 00:59:25,670

 

1133
00:59:25,670 --> 00:59:27,260

 

1134
00:59:27,260 --> 00:59:29,630

 

1135
00:59:29,630 --> 00:59:32,120

 

1136
00:59:32,120 --> 00:59:33,589

 

1137
00:59:33,589 --> 00:59:41,029

 

1138
00:59:41,029 --> 00:59:43,250

 

1139
00:59:43,250 --> 00:59:45,319

 

1140
00:59:45,319 --> 00:59:47,569

 

1141
00:59:47,569 --> 00:59:50,569

 

1142
00:59:50,569 --> 00:59:52,609

 

1143
00:59:52,609 --> 00:59:54,829

 

1144
00:59:54,829 --> 00:59:57,829

 

1145
00:59:57,829 --> 01:00:00,079

 

1146
01:00:00,079 --> 01:00:03,859

 

1147
01:00:03,859 --> 01:00:05,420

 

1148
01:00:05,420 --> 01:00:08,420

 

1149
01:00:08,420 --> 01:00:12,170

 

1150
01:00:12,170 --> 01:00:14,150

 

1151
01:00:14,150 --> 01:00:15,950

 

1152
01:00:15,950 --> 01:00:18,319

 

1153
01:00:18,319 --> 01:00:23,960

 

1154
01:00:23,960 --> 01:00:26,240

 

1155
01:00:26,240 --> 01:00:29,180

 

1156
01:00:29,180 --> 01:00:31,430

 

1157
01:00:31,430 --> 01:00:32,839

 

1158
01:00:32,839 --> 01:00:34,279

 

1159
01:00:34,279 --> 01:00:36,980

 

1160
01:00:36,980 --> 01:00:38,809

 

1161
01:00:38,809 --> 01:00:40,670

 

1162
01:00:40,670 --> 01:00:45,200

 

1163
01:00:45,200 --> 01:00:47,960

 

1164
01:00:47,960 --> 01:00:49,910

 

1165
01:00:49,910 --> 01:00:52,010

 

1166
01:00:52,010 --> 01:00:55,040

 

1167
01:00:55,040 --> 01:00:56,480

 

1168
01:00:56,480 --> 01:00:59,900

 

1169
01:00:59,900 --> 01:01:02,960

 

1170
01:01:02,960 --> 01:01:04,460

 

1171
01:01:04,460 --> 01:01:07,400

 

1172
01:01:07,400 --> 01:01:11,270

 

1173
01:01:11,270 --> 01:01:13,250

 

1174
01:01:13,250 --> 01:01:14,930

 

1175
01:01:14,930 --> 01:01:17,810

 

1176
01:01:17,810 --> 01:01:23,450

 

1177
01:01:23,450 --> 01:01:26,990

 

1178
01:01:26,990 --> 01:01:28,760

 

1179
01:01:28,760 --> 01:01:31,280

 

1180
01:01:31,280 --> 01:01:43,359

 

1181
01:01:43,359 --> 01:01:47,270

 

1182
01:01:47,270 --> 01:01:49,550

 

1183
01:01:49,550 --> 01:01:51,109

 

1184
01:01:51,109 --> 01:01:52,430

 

1185
01:01:52,430 --> 01:01:54,560

 

1186
01:01:54,560 --> 01:01:56,080

 

1187
01:01:56,080 --> 01:01:59,270

 

1188
01:01:59,270 --> 01:02:04,970

 

1189
01:02:04,970 --> 01:02:16,620

 

1190
01:02:16,620 --> 01:02:18,850

 

1191
01:02:18,850 --> 01:02:21,760

 

1192
01:02:21,760 --> 01:02:23,080

 

1193
01:02:23,080 --> 01:02:24,730

 

1194
01:02:24,730 --> 01:02:27,850

 

1195
01:02:27,850 --> 01:02:28,480

 

1196
01:02:28,480 --> 01:02:30,460

 

1197
01:02:30,460 --> 01:02:32,650

 

1198
01:02:32,650 --> 01:02:34,510

 

1199
01:02:34,510 --> 01:02:37,150

 

1200
01:02:37,150 --> 01:02:38,590

 

1201
01:02:38,590 --> 01:02:46,240

 

1202
01:02:46,240 --> 01:02:50,710

 

1203
01:02:50,710 --> 01:02:53,200

 

1204
01:02:53,200 --> 01:02:55,650

 

1205
01:02:55,650 --> 01:02:58,690

 

1206
01:02:58,690 --> 01:03:00,670

 

1207
01:03:00,670 --> 01:03:04,810

 

1208
01:03:04,810 --> 01:03:06,760

 

1209
01:03:06,760 --> 01:03:10,870

 

1210
01:03:10,870 --> 01:03:13,690

 

1211
01:03:13,690 --> 01:03:17,620

 

1212
01:03:17,620 --> 01:03:18,910

 

1213
01:03:18,910 --> 01:03:18,920

 

1214
01:03:18,920 --> 01:03:33,750


1215
01:03:33,750 --> 01:03:36,730

 

1216
01:03:36,730 --> 01:03:38,890

 

1217
01:03:38,890 --> 01:03:41,530

 

1218
01:03:41,530 --> 01:03:43,240

 

1219
01:03:43,240 --> 01:03:45,490

 

1220
01:03:45,490 --> 01:03:56,040

 

1221
01:03:56,040 --> 01:04:04,320

 

1222
01:04:04,320 --> 01:04:06,840

 

1223
01:04:06,840 --> 01:04:08,940

 

1224
01:04:08,940 --> 01:04:11,430

 

1225
01:04:11,430 --> 01:04:13,970

 

1226
01:04:13,970 --> 01:04:16,380

 

1227
01:04:16,380 --> 01:04:18,090

 

1228
01:04:18,090 --> 01:04:19,590

 

1229
01:04:19,590 --> 01:04:24,330

 

1230
01:04:24,330 --> 01:04:26,160

 

1231
01:04:26,160 --> 01:04:28,140

 

1232
01:04:28,140 --> 01:04:31,200

 

1233
01:04:31,200 --> 01:04:35,790

 

1234
01:04:35,790 --> 01:04:36,570

 

1235
01:04:36,570 --> 01:04:39,270

 

1236
01:04:39,270 --> 01:04:41,280

 

1237
01:04:41,280 --> 01:04:44,340

 

1238
01:04:44,340 --> 01:04:46,530

 

1239
01:04:46,530 --> 01:04:48,810

 

1240
01:04:48,810 --> 01:04:55,560

 

1241
01:04:55,560 --> 01:04:57,570

 

1242
01:04:57,570 --> 01:05:00,510

 

1243
01:05:00,510 --> 01:05:02,580

 

1244
01:05:02,580 --> 01:05:06,180

 

1245
01:05:06,180 --> 01:05:08,760

 

1246
01:05:08,760 --> 01:05:10,380

 

1247
01:05:10,380 --> 01:05:13,200

 

1248
01:05:13,200 --> 01:05:14,550

 

1249
01:05:14,550 --> 01:05:18,000

 

1250
01:05:18,000 --> 01:05:20,150

 

1251
01:05:20,150 --> 01:05:23,220

 

1252
01:05:23,220 --> 01:05:26,010

 

1253
01:05:26,010 --> 01:05:30,150

 

1254
01:05:30,150 --> 01:05:32,100

 

1255
01:05:32,100 --> 01:05:34,290

 

1256
01:05:34,290 --> 01:05:38,400

 

1257
01:05:38,400 --> 01:05:40,530

 

1258
01:05:40,530 --> 01:05:42,900

 

1259
01:05:42,900 --> 01:05:47,280

 

1260
01:05:47,280 --> 01:05:50,220

 

1261
01:05:50,220 --> 01:05:52,290

 

1262
01:05:52,290 --> 01:05:55,710

 

1263
01:05:55,710 --> 01:05:57,240

 

1264
01:05:57,240 --> 01:06:00,200

 

1265
01:06:00,200 --> 01:06:03,510

 

1266
01:06:03,510 --> 01:06:05,250

 

1267
01:06:05,250 --> 01:06:08,250

 

1268
01:06:08,250 --> 01:06:11,040

 

1269
01:06:11,040 --> 01:06:13,950

 

1270
01:06:13,950 --> 01:06:15,990

 

1271
01:06:15,990 --> 01:06:18,960

 

1272
01:06:18,960 --> 01:06:23,940

 

1273
01:06:23,940 --> 01:06:25,920

 

1274
01:06:25,920 --> 01:06:28,050

 

1275
01:06:28,050 --> 01:06:29,609

 

1276
01:06:29,609 --> 01:06:31,260

 

1277
01:06:31,260 --> 01:06:34,980

 

1278
01:06:34,980 --> 01:06:36,900

 

1279
01:06:36,900 --> 01:06:39,420

 

1280
01:06:39,420 --> 01:06:40,830

 

1281
01:06:40,830 --> 01:06:43,160

 

1282
01:06:43,160 --> 01:06:45,480

 

1283
01:06:45,480 --> 01:06:48,960

 

1284
01:06:48,960 --> 01:06:50,010

 

1285
01:06:50,010 --> 01:07:02,150

 

1286
01:07:02,150 --> 01:07:05,579

 

1287
01:07:05,579 --> 01:07:07,170

 

1288
01:07:07,170 --> 01:07:10,349

 

1289
01:07:10,349 --> 01:07:12,180

 

1290
01:07:12,180 --> 01:07:14,970

 

1291
01:07:14,970 --> 01:07:16,680

 

1292
01:07:16,680 --> 01:07:18,359

 

1293
01:07:18,359 --> 01:07:20,190

 

1294
01:07:20,190 --> 01:07:31,880

 

1295
01:07:31,880 --> 01:07:34,020

 

1296
01:07:34,020 --> 01:07:36,420

 

1297
01:07:36,420 --> 01:07:39,870

 

1298
01:07:39,870 --> 01:07:41,670

 

1299
01:07:41,670 --> 01:07:43,920

 

1300
01:07:43,920 --> 01:07:51,180

 

1301
01:07:51,180 --> 01:07:53,190

 

1302
01:07:53,190 --> 01:08:00,810

 

1303
01:08:00,810 --> 01:08:03,770

 

1304
01:08:03,770 --> 01:08:06,690

 

1305
01:08:06,690 --> 01:08:09,359

 

1306
01:08:09,359 --> 01:08:11,160

 

1307
01:08:11,160 --> 01:08:15,750

 

1308
01:08:15,750 --> 01:08:17,789

 

1309
01:08:17,789 --> 01:08:20,910

 

1310
01:08:20,910 --> 01:08:23,729

 

1311
01:08:23,729 --> 01:08:25,530

 

1312
01:08:25,530 --> 01:08:29,130

 

1313
01:08:29,130 --> 01:08:30,599

 

1314
01:08:30,599 --> 01:08:33,240

 

1315
01:08:33,240 --> 01:08:37,740

 

1316
01:08:37,740 --> 01:08:39,870

 

1317
01:08:39,870 --> 01:08:44,190

 

1318
01:08:44,190 --> 01:08:46,920

 

1319
01:08:46,920 --> 01:08:50,519

 

1320
01:08:50,519 --> 01:08:53,610

 

1321
01:08:53,610 --> 01:08:55,320

 

1322
01:08:55,320 --> 01:08:58,320

 

1323
01:08:58,320 --> 01:09:01,280

 

1324
01:09:01,280 --> 01:09:04,800

 

1325
01:09:04,800 --> 01:09:07,170

 

1326
01:09:07,170 --> 01:09:08,820

 

1327
01:09:08,820 --> 01:09:10,320

 

1328
01:09:10,320 --> 01:09:11,700

 

1329
01:09:11,700 --> 01:09:14,820

 

1330
01:09:14,820 --> 01:09:15,930

 

1331
01:09:15,930 --> 01:09:18,180

 

1332
01:09:18,180 --> 01:09:22,439

 

1333
01:09:22,439 --> 01:09:25,349

 

1334
01:09:25,349 --> 01:09:26,970

 

1335
01:09:26,970 --> 01:09:30,120

 

1336
01:09:30,120 --> 01:09:41,820

 

1337
01:09:41,820 --> 01:09:43,499

 

1338
01:09:43,499 --> 01:09:47,010

 

1339
01:09:47,010 --> 01:09:49,769

 

1340
01:09:49,769 --> 01:09:50,999

 

1341
01:09:50,999 --> 01:09:53,670

 

1342
01:09:53,670 --> 01:09:55,320

 

1343
01:09:55,320 --> 01:10:02,250

 

1344
01:10:02,250 --> 01:10:05,640

 

1345
01:10:05,640 --> 01:10:08,640

 

1346
01:10:08,640 --> 01:10:14,220

 

1347
01:10:14,220 --> 01:10:16,380

 

1348
01:10:16,380 --> 01:10:19,979

 

1349
01:10:19,979 --> 01:10:23,580

 

1350
01:10:23,580 --> 01:10:27,630

 

1351
01:10:27,630 --> 01:10:30,720

 

1352
01:10:30,720 --> 01:10:34,439

 

1353
01:10:34,439 --> 01:10:36,630

 

1354
01:10:36,630 --> 01:10:38,820

 

1355
01:10:38,820 --> 01:10:40,680

 

1356
01:10:40,680 --> 01:10:44,310

 

1357
01:10:44,310 --> 01:10:48,030

 

1358
01:10:48,030 --> 01:10:51,420

 

1359
01:10:51,420 --> 01:10:54,870

 

1360
01:10:54,870 --> 01:10:57,360

 

1361
01:10:57,360 --> 01:10:59,459

 

1362
01:10:59,459 --> 01:11:04,890

 

1363
01:11:04,890 --> 01:11:06,810

 

1364
01:11:06,810 --> 01:11:10,020

 

1365
01:11:10,020 --> 01:11:12,270

 

1366
01:11:12,270 --> 01:11:14,729

 

1367
01:11:14,729 --> 01:11:18,180

 

1368
01:11:18,180 --> 01:11:20,880

 

1369
01:11:20,880 --> 01:11:21,900

 

1370
01:11:21,900 --> 01:11:24,240

 

1371
01:11:24,240 --> 01:11:27,450

 

1372
01:11:27,450 --> 01:11:29,790

 

1373
01:11:29,790 --> 01:11:32,910

 

1374
01:11:32,910 --> 01:11:35,760

 

1375
01:11:35,760 --> 01:11:37,530

 

1376
01:11:37,530 --> 01:11:40,700

 

1377
01:11:40,700 --> 01:11:44,610

 

1378
01:11:44,610 --> 01:11:45,960

 

1379
01:11:45,960 --> 01:11:50,120

 

1380
01:11:50,120 --> 01:11:52,410

 

1381
01:11:52,410 --> 01:11:54,540

 

1382
01:11:54,540 --> 01:11:58,110

 

1383
01:11:58,110 --> 01:12:01,230

 

1384
01:12:01,230 --> 01:12:03,870

 

1385
01:12:03,870 --> 01:12:07,860

 

1386
01:12:07,860 --> 01:12:13,950

 

1387
01:12:13,950 --> 01:12:15,600

 

1388
01:12:15,600 --> 01:12:18,240

 

1389
01:12:18,240 --> 01:12:21,120

 

1390
01:12:21,120 --> 01:12:25,520

 

1391
01:12:25,520 --> 01:12:29,970

 

1392
01:12:29,970 --> 01:12:35,430

 

1393
01:12:35,430 --> 01:12:36,990

 

1394
01:12:36,990 --> 01:12:39,900

 

1395
01:12:39,900 --> 01:12:42,510

 

1396
01:12:42,510 --> 01:12:47,040

 

1397
01:12:47,040 --> 01:12:49,530

 

1398
01:12:49,530 --> 01:12:53,670

 

1399
01:12:53,670 --> 01:12:56,340

 

1400
01:12:56,340 --> 01:12:59,100

 

1401
01:12:59,100 --> 01:13:01,410

 

1402
01:13:01,410 --> 01:13:02,910

 

1403
01:13:02,910 --> 01:13:08,760

 

1404
01:13:08,760 --> 01:13:13,590

 

1405
01:13:13,590 --> 01:13:15,390

 

1406
01:13:15,390 --> 01:13:19,170

 

1407
01:13:19,170 --> 01:13:21,960

 

1408
01:13:21,960 --> 01:13:24,180

 

1409
01:13:24,180 --> 01:13:26,400

 

1410
01:13:26,400 --> 01:13:27,930

 

1411
01:13:27,930 --> 01:13:31,980

 

1412
01:13:31,980 --> 01:13:33,540

 

1413
01:13:33,540 --> 01:13:37,320

 

1414
01:13:37,320 --> 01:13:40,170

 

1415
01:13:40,170 --> 01:13:43,020

 

1416
01:13:43,020 --> 01:13:43,680

 

1417
01:13:43,680 --> 01:13:45,810

 

1418
01:13:45,810 --> 01:13:48,390

 

1419
01:13:48,390 --> 01:13:51,060

 

1420
01:13:51,060 --> 01:13:54,360

 

1421
01:13:54,360 --> 01:13:57,480

 

1422
01:13:57,480 --> 01:14:00,270

 

1423
01:14:00,270 --> 01:14:03,780

 

1424
01:14:03,780 --> 01:14:07,170

 

1425
01:14:07,170 --> 01:14:12,530

 

1426
01:14:12,530 --> 01:14:15,780

 

1427
01:14:15,780 --> 01:14:18,900

 

1428
01:14:18,900 --> 01:14:24,210

 

1429
01:14:24,210 --> 01:14:26,430

 

1430
01:14:26,430 --> 01:14:30,060

 

1431
01:14:30,060 --> 01:14:32,100

 

1432
01:14:32,100 --> 01:14:33,690

 

1433
01:14:33,690 --> 01:14:36,330

 

1434
01:14:36,330 --> 01:14:39,060

 

1435
01:14:39,060 --> 01:14:42,270

 

1436
01:14:42,270 --> 01:14:44,970

 

1437
01:14:44,970 --> 01:14:47,010

 

1438
01:14:47,010 --> 01:14:48,570

 

1439
01:14:48,570 --> 01:14:53,160

 

1440
01:14:53,160 --> 01:14:56,340

 

1441
01:14:56,340 --> 01:15:02,610

 

1442
01:15:02,610 --> 01:15:05,070

 

1443
01:15:05,070 --> 01:15:09,510

 

1444
01:15:09,510 --> 01:15:13,680

 

1445
01:15:13,680 --> 01:15:17,490

 

1446
01:15:17,490 --> 01:15:20,390

 

1447
01:15:20,390 --> 01:15:23,130

 

1448
01:15:23,130 --> 01:15:26,730

 

1449
01:15:26,730 --> 01:15:30,810

 

1450
01:15:30,810 --> 01:15:40,919

 

1451
01:15:40,919 --> 01:15:44,220

 

1452
01:15:44,220 --> 01:15:46,229

 

1453
01:15:46,229 --> 01:15:48,180

 

1454
01:15:48,180 --> 01:15:51,090

 

1455
01:15:51,090 --> 01:15:54,180

 

1456
01:15:54,180 --> 01:15:57,689

 

1457
01:15:57,689 --> 01:15:59,939

 

1458
01:15:59,939 --> 01:16:07,530

 

1459
01:16:07,530 --> 01:16:12,660

 

1460
01:16:12,660 --> 01:16:15,180

 

1461
01:16:15,180 --> 01:16:17,550

 

1462
01:16:17,550 --> 01:16:20,189

 

1463
01:16:20,189 --> 01:16:23,850

 

1464
01:16:23,850 --> 01:16:26,280

 

1465
01:16:26,280 --> 01:16:29,520

 

1466
01:16:29,520 --> 01:16:31,919

 

1467
01:16:31,919 --> 01:16:34,530

 

1468
01:16:34,530 --> 01:16:36,270

 

1469
01:16:36,270 --> 01:16:38,189

 

1470
01:16:38,189 --> 01:16:41,120

 

1471
01:16:41,120 --> 01:16:43,800

 

1472
01:16:43,800 --> 01:16:46,410

 

1473
01:16:46,410 --> 01:16:55,120

 

1474
01:16:55,120 --> 01:16:57,640

 

1475
01:16:57,640 --> 01:17:00,040

 

1476
01:17:00,040 --> 01:17:01,540

 

1477
01:17:01,540 --> 01:17:03,760

 

1478
01:17:03,760 --> 01:17:06,400

 

1479
01:17:06,400 --> 01:17:09,400

 

1480
01:17:09,400 --> 01:17:12,370

 

1481
01:17:12,370 --> 01:17:15,880

 

1482
01:17:15,880 --> 01:17:21,010

 

1483
01:17:21,010 --> 01:17:23,560

 

1484
01:17:23,560 --> 01:17:25,630

 

1485
01:17:25,630 --> 01:17:27,760

 

1486
01:17:27,760 --> 01:17:29,140

 

1487
01:17:29,140 --> 01:17:31,270

 

1488
01:17:31,270 --> 01:17:33,640

 

1489
01:17:33,640 --> 01:17:36,580

 

1490
01:17:36,580 --> 01:17:40,930

 

1491
01:17:40,930 --> 01:17:42,670

 

1492
01:17:42,670 --> 01:17:44,770

 

1493
01:17:44,770 --> 01:17:46,900

 

1494
01:17:46,900 --> 01:17:54,300

 

1495
01:17:54,300 --> 01:17:57,850

 

1496
01:17:57,850 --> 01:18:00,160

 

1497
01:18:00,160 --> 01:18:03,100

 

1498
01:18:03,100 --> 01:18:04,900

 

1499
01:18:04,900 --> 01:18:06,790

 

1500
01:18:06,790 --> 01:18:08,830

 

1501
01:18:08,830 --> 01:18:13,930

 

1502
01:18:13,930 --> 01:18:15,100

 

1503
01:18:15,100 --> 01:18:17,710

 

1504
01:18:17,710 --> 01:18:19,840

 

1505
01:18:19,840 --> 01:18:21,970

 

1506
01:18:21,970 --> 01:18:24,490

 

1507
01:18:24,490 --> 01:18:28,540

 

1508
01:18:28,540 --> 01:18:29,980

 

1509
01:18:29,980 --> 01:18:32,260

 

1510
01:18:32,260 --> 01:18:34,810

 

1511
01:18:34,810 --> 01:18:36,490

 

1512
01:18:36,490 --> 01:18:38,440

 

1513
01:18:38,440 --> 01:18:40,060

 

1514
01:18:40,060 --> 01:18:41,560

 

1515
01:18:41,560 --> 01:18:44,080

 

1516
01:18:44,080 --> 01:18:44,090

 

1517
01:18:44,090 --> 01:18:53,359


1518
01:18:53,359 --> 01:18:53,369

 

1519
01:18:53,369 --> 01:18:55,429