{"id":1013,"date":"2014-05-12T07:00:00","date_gmt":"2014-05-12T07:00:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/2014\/05\/12\/enumerating-bit-sequences-with-isolated-zero-bits-via-the-fibonacci-recurrence\/"},"modified":"2014-05-12T07:00:00","modified_gmt":"2014-05-12T07:00:00","slug":"enumerating-bit-sequences-with-isolated-zero-bits-via-the-fibonacci-recurrence","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20140512-00\/?p=1013","title":{"rendered":"Enumerating bit sequences with isolated zero-bits via the Fibonacci recurrence"},"content":{"rendered":"

\nToday’s Little Program enumerates bit sequences of a particular\nlength subject to the constraint that you cannot have consecutive 0-bits.\nThis may sound kind of arbitrary, but it is\n\nimportant in magnetic media storage<\/a>,\nbecause you cannot go too long without a\nflux reversal (traditionally represented by a 1);\notherwise,\nthe read head’s clock starts to drift and gets out of sync\nwith the data.\n(The read head uses flux reversals both for signaling and for\nclock synchronization.)\n<\/p>\n

\nLet’s say that an allowable<\/i> bit sequence is one that contains\nno consecutive 0-bits.\n<\/p>\n

\nThe recurrence for enumerating these types of constrained bit\nsequence is the Fibonacci recurrence:\n<\/p>\n

\nF<\/var>(n<\/var>) = F<\/var>(n<\/var> − 1) + F<\/var>(n<\/var> − 2)\n<\/p><\/blockquote>\n

\nThe way to see this is to study the last digit in an allowable bit sequence.\n<\/p>\n

\nIf the last digit is a 1, then if you delete it, you have\nan allowable bit sequence that is one digit shorter.\nConversely, you can take any allowable\nbit sequence of length n<\/var> − 1\nand tack a 1 onto it, and you’ll have an allowable sequence.\n<\/p>\n

\nIf the last digit is a 0, then if you delete it, you also have\nan allowable bit sequence that is one digit shorter,\nbut not all allowable bit sequences of length n<\/var> − 1\ncan be reached in this way.\nAllowable bit sequences that end in 0 cannot be reached\nbecause adding another 0 would result in two consecutive 0-bits,\nwhich is disallowed.\nTherefore, the last digit of the truncated bit sequence must be 1,\nand what you really have is an allowable bit sequence of length\nn<\/var> − 2, followed by a hard-coded 1.\n<\/p>\n

\nOkay, now that we understand the enumerative justification for\nthe recurrence, we can proceed to write the code that generates\nit.\n<\/p>\n

\nfunction GCR(n, f) {\n if (n == 0) { f(\"\"); return; }\n if (n < 0) { return; }\n GCR(n-1, function(s) { f(s + \"1\"); });\n GCR(n-2, function(s) { f(s + \"10\"); });\n}\nGCR(8, console.log);\n<\/pre>\n
\nThe test run calculates all 8-bit allowable sequences.\nBut wait, there’s a bug:\nIt shows only the sequences that begin with a 1.\n<\/p>\n
\nIf you’re Steve Wozniak, then this bug is a feature,\nbecause the Apple II floppy drive also required the\nfirst bit to be set, so our bug exactly matches the hardware\nrequirements.\n<\/p>\n
\nBut let’s fix our bug. Where did it come from?\n<\/p>\n
\nOur recursive step missed a base case:\nThe single-digit bit sequence 0 is allowable,\nbut we rejected it because we thought that it needed\nto be separated from the null string by a 1,\nto protect against the null string ending in 0.\nBut the null string doesn’t end in zero, so this protection\nwas unnecessary.\n<\/p>\n
\nRepairing our base case:\n<\/p>\n
\nfunction GCR(n, f) {\n if (n == 0) { f(\"\"); return; }\n if (n == 1) { f(\"0\"); f(\"1\"); return; }\n GCR(n-1, function(s) { f(s + \"1\"); });\n GCR(n-2, function(s) { f(s + \"10\"); });\n}\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
Today’s Little Program enumerates bit sequences of a particular length subject to the constraint that you cannot have consecutive 0-bits. This may sound kind of arbitrary, but it is important in magnetic media storage, because you cannot go too long without a flux reversal (traditionally represented by a 1); otherwise, the read head’s clock starts […]<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-1013","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
Today’s Little Program enumerates bit sequences of a particular length subject to the constraint that you cannot have consecutive 0-bits. This may sound kind of arbitrary, but it is important in magnetic media storage, because you cannot go too long without a flux reversal (traditionally represented by a 1); otherwise, the read head’s clock starts […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/1013","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=1013"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/1013\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=1013"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=1013"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=1013"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}