bitshifting

vimeo

Shift is an array of machines shifting bits and bytes informed by simple and highly repetitive algorithms. Shift pays attention to its environment through the ever-watchful eye of a built-in camera and responds to movement.

Changes in state are expressed through audio and visual abstractions. An algorithm is a process or a set of rules. Here, the algorithms are shaped by Andreas Schlegel, Benson Chong Thong Pin, Felix Sng, Jiahao Ma Darrick, Marvin Liang Yong Jie, Mike Chen, Muhammad Dhiya Bin Rahman, Sid Lim Xian Hao.

Materials; custom software Tools; Processing, Supercollider Hardware; 8 iMacs, 4 speakers, 1 mixer, 1 ethernet switch Dimension; 5 x 3 x 2m , Year; 2011

XBee: LED/Buzzer Code Analysis Part 5 - Bitshifting/Binary math

First - thanks to @FeltonChris and @RoyEltham for their patience in helping me understand this as well as the many twitter suggestions. So the frequency that we put into FRQA/B (in the main code) seems to actually be a calculated frequency. Ultimately, this portion of the code is an “optimized way” of doing Result (or FRQA/B) = freq * (2^32) / clkfreq.  But since Spin doesn’t have multiplication or division, there are tricksy ways to use addition, subtraction, and bitshifting to do the same thing.  So this code starts by saying:

Repeat the following loop 33 times.  Bitshift Result left by 1. 

Let’s talk a little about this idea of bitshifting.  Bit shifting is just adding an extra “place” or 0 according to the code.  Here we’re bitshifting by 1 (<<= 1) If we had a 4 bit number:

  • 0001 (equals 1) and shifted to the left, it would look like this:
  • 0010 (equals 2) and shifted to the left, it would look like this:
  • 0100 (equals 4) and shifted to the left, it would look like this:
  • 1000 (equals 8) and shifted to the left, it would look like this:
  • 0000 and shifted to the left, it would look like this:
  • 0000 - notice what happens now?
  • Did you also notice that <<= 1 equates x*2?

And with a 32-bit number.  Let’s assume it’s 32-1s

  • 11111111_11111111_11111111_11111111 shifted to the left:
  • 11111111_11111111_11111111_11111110 ….do this 33 times and you’ll end up with result always equaling 32 0’s.

Because Result (an automatic local variable) isn’t defined, it starts out as 0.  0 bitshifted left is still 0.  It stays 0 unless freq is equal to or greater (=>) than clkfreq (the number of clock cycles for 1 second but also the clock frequency of the chip).  If it is equal to or greater than clkfreq, then subtract clkfreq from freq (-=).  And then post increment the result (result++) which means result = result + 1. 

Now this bitshifting/subtraction stuff is supposed to represent freq * (2^32) / clkfreq.  I initially had no clue as to how you get division out of subtraction, but let’s look at an example of long division.

When your dividend (what’s getting divided) is large enough, your divisor (what it’s divided by) is able to “go into it” - like 7 not being able to go into 1, but being able to go into 1.0. Then 7 is subtracted from 1.0 and the process repeats.

  • In our code example, this is where “if freq => clkfreq” and where clkfreq is the divisor and freq is what’s getting divided.  When freq is greater than or equal to clkfreq, clkfreq is subtracted from freq (like subtracting 7 from 1.0).
  • Now you might wonder how we got subtraction out of division.  But essentially, what you are constantly doing is subtracting the divisor (clkfreq) from each iteration. 

Just as we mentioned, when doing long division, if your dividend is NOT large enough, you put a period and then as many zeros as you need and solve until you get a remainder of 0. So you see in the above math example how instead of stopping at 0.142, we solved until 7 went perfectly into whatever resulting number came from the subtraction step to get 0.1428.

  • This is similar to this example of adding bits ++ style.  When you do this ++, it adds an additional binary spot to the end (0010 to 0011). 

You might also notice that freq * 2^32.  You’ll also notice that this function goes through 33 times.  So each time, freq <<= 1 which, remember, also equates freq * 2 and then in going through 33 times, you’ll see that freq * 2 * 2 * 2 * 2 (for 32 times).

@feltonchris was kind enough to write the code out and show each step:

Given a clkfreq of 80_000_000 (or 80MHz) and freq of 2048, let’s use what this code is supposed to do mathematically:

  • FRQA/B = freq * 2^32 / clkfreq
  • FRQA/B = 2048 * 2^32 / 80_000_000 = 109951

Per the code, result at the end = 109951! 

Let’s go through a couple lines of the code to see how it’d look.  Note, it’s kind of like..simultaneous bitshifting/decimal adding.  It doesn’t seem to be standard as to whether it looks like bits or decimals.:

  • Iteration 16: freq 0108435456  result 0000000001
  • Result is bitshifted to 0000000002 (%00000000010 from %00000000001)
  • Is freq 0_108_435_456 => 80_000_000? Yep!
  • 0108435456 - 80000000 = 28435456
  • Result ++ to 0000000003
  • Freq <<= 1 = (28435456 * 2) = 0056870912
  • Iteration 17: freq 0056870912  result 0000000003
  • Result is bitshifted to 0000000006 (%00000000110 from %00000000011)
  • Is freq 56_870_912 => 80_000_000? Nope!
  • Freq <<= 1 = 0113741824
  • Iteration 18: freq 0113741824  result 0000000006
  • Result is bitshifted to 00000000012 (%00000001100 from %00000000110)
  • Is freq 0_113_741_824 => 80_000_000? Yep!
  • 0113741824 - 80000000 = 33741824
  • Result ++ to 0000000013
  • Freq <<= 1 = (33741824 * 2) = 67483648

Now Roy says that 109951 is what is placed in FRQ and it will get added to PHSA every clock cycle… and PHSA will wrap 2048 times over 1 second

  • 2^32 = 4294967296 
  • (109951 * 80_000_000)/2^32 (to get wrapped times per sec)) = 2048

PHEW! and Tracy Allen over at the Parallax forums was able to give a great example with different numbers to explain the magic of binary math and how this code achieves what it does: http://forums.parallax.com/showthread.php?138066-Going-through-XBee-Tutorial&p=1079201&viewfull=1#post1079201 - Thanks!!

@atdiy/@tymkrs