{"id":395015,"date":"2024-06-29T11:57:53","date_gmt":"2024-06-29T11:57:53","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=395015"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=395015","title":{"rendered":"<span>Algorithms in Go: Bit Manipulation<\/span>"},"content":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-1\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<p>This article is a part of <a href=\"https:\/\/habr.com\/en\/post\/545986\/\">Algorithms in Go<\/a> series where we discuss common algorithmic problems and their solution patterns.<\/p>\n<p>  <\/p>\n<p>In this edition, we take a closer look at bit manipulations. Bit operations can be extremely powerful and useful in an entire class of algorithmic problems, including problems that at first glance does not have to do anything with bits.<\/p>\n<p>  <\/p>\n<p>Let&#8217;s consider the following problem: six friends meet in the bar and decide who pays for the next round. They would like to select a random person among them for that. How can they do a random selection using only a single coin?<\/p>\n<p>  <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/yc\/nz\/lr\/ycnzlrd8b5cr5sie3ozgihwyfbg.png\" data-src=\"https:\/\/habrastorage.org\/webt\/yc\/nz\/lr\/ycnzlrd8b5cr5sie3ozgihwyfbg.png\"\/><\/p>\n<p>  <\/p>\n<p>The solution to this problem is not particularly obvious (for me:), so let&#8217;s simplify a problem for a moment to develop our understanding. How would we do the selection if there were only three friends? In other words, how would we &#171;mimic&#187; a three-sided coin with a two-sided coin?<\/p>\n<p><a name=\"habracut\"><\/a>  <\/p>\n<p>Well, we can throw the coin twice and enlist all possible options:<\/p>\n<p>  <\/p>\n<ul>\n<li><em>tails<\/em> and <em>tails<\/em>: Joey<\/li>\n<li><em>tails<\/em> and <em>heads<\/em>: Phoebe<\/li>\n<li><em>heads<\/em> and <em>tails<\/em>: Rachel<\/li>\n<li><em>heads<\/em> and <em>heads<\/em>: no-op, do the selection again<\/li>\n<\/ul>\n<p>  <\/p>\n<p>Now, this looks suspiciously close to a binary encoding. <\/p>\n<p>  <\/p>\n<ul>\n<li><em>0<\/em> and <em>0<\/em>: Joey<\/li>\n<li><em>0<\/em> and <em>1<\/em>: Phoebe<\/li>\n<li><em>1<\/em> and <em>0<\/em>: Rachel<\/li>\n<li><em>1<\/em> and <em>1<\/em>: no-op, do the selection again<\/li>\n<\/ul>\n<p>  <\/p>\n<p>So in general, we need to conduct enough trials to encode all the options. If we get an invalid outcome, we repeat the process. <\/p>\n<p>  <\/p>\n<p>The signature for the function will look as follows:<\/p>\n<p>  <\/p>\n<pre><code class=\"go\">type Choice string  \/\/ 6 possible choices for six friends. var choices = []Choice{\"Joey\", \"Phoebe\", \"Rachel\", \"Chandler\", \"Ross\", \"Monica\"}  \/\/ select a random friend from the list of choices. func Select() Choice {     ... }<\/code><\/pre>\n<p>  <\/p>\n<p>Let&#8217;s start with the tests before implementing the actual solution. How can we test a random generator? First, we need to ensure that we have a uniform distribution, i.e. that each possible choice can be selected with the same probability. It is not possible to test this claim on a single trial. However, we can check this statistically. We do a series of trials and count how many times each friend was chosen. After all trials, each friend must have been chosen approximately the same number of times. In our test, we conduct 10,000 trials and allow a delta of ten percent. <\/p>\n<p>  <\/p>\n<pre><code class=\"go\">func TestUniformity(t *testing.T) {     n := 10_000 \/\/ 10,000 trials     buckets := make([]int, len(choices))     for i := 0; i &lt; n; i++ {         trial := Select()         buckets[trial-1]++     }     delta := 0.1 \/\/ 10 percent     diff := delta * float64(buckets[0])     \/\/ expected range of the results     min, max := float64(buckets[0])-diff, float64(buckets[0])+diff      for _, value := range buckets[1:] {         assert.Greater(t, float64(value), min)         assert.Less(t, float64(value), max)     } }<\/code><\/pre>\n<p>  <\/p>\n<p>However, this test alone is not sufficient. Let&#8217;s write a mock generator that passes this test but actually does not produce random numbers.<\/p>\n<p>  <\/p>\n<pre><code class=\"go\">func mockGenerator() func() Choice {     state := -1     f := func() Choice {         state = (state + 1) % 6         return choices[state]     }     return f }<\/code><\/pre>\n<p>  <\/p>\n<p>This generator returns a selection function that produces the same sequence <code>[\"Joey\", \"Phoebe\", \"Rachel\", \"Chandler\", \"Ros\", \"Monica\"]<\/code> in a circle. The distribution is uniform, however, it is not random. <\/p>\n<p>  <\/p>\n<p>Let&#8217;s add one more test that detects the circles in the output. We define the size of the window and then split the output. If each window contains exactly the same sequence, then we find a circle. If not, we adjust the size of the window and repeat the process. If we reach the size of the window of 1 and didn&#8217;t find the circle, then the test passes.<\/p>\n<p>  <\/p>\n<pre><code class=\"go\">func TestCircle(t *testing.T) {     trials := make([]Choice, 0, 10000)     for i := 0; i &lt; 10000; i++ {         trials = append(trials, Select())     }      for size := 100; size >= 1; size-- {         first := trials[:size]         circle := true         for start := size; start+size &lt;= len(trials); start = start + size {             next := trials[start : start+size]             if !cmp.Equal(first, next) {                 circle = false                 break             } else {                 circle = true             }         }         assert.False(t, circle, size)     } }<\/code><\/pre>\n<p>  <\/p>\n<p>Note, that in our case each window will be represented as a slice of <code>Choice<\/code>. In Golang, the equality operation is not defined on slices, therefore we use a helper library <code>github.com\/google\/go-cmp\/cmp<\/code>.<\/p>\n<p>  <\/p>\n<p>Our mock generator won&#8217;t pass the second test, as it produces the circled sequence. <\/p>\n<p>  <\/p>\n<p>Now we can proceed to the actual implementation of the function. How many trials would we need to conduct? In other words, how many bits do we need to encode all possible choices. Each bite can have two possible values <code>0<\/code> or <code>1<\/code>, therefore, a sequence of bytes can represent 2<sup>n<\/sup> values, where <code>n<\/code> is the number of bytes. <\/p>\n<p>  <\/p>\n<blockquote><p>numberOfChoices = 2<sup>n<\/sup><br \/>  n = log<sub>2<\/sub>(numberOfChoices)<\/p><\/blockquote>\n<p>Therefore, we require at least <code>n<\/code> bytes (or trials). We need to round up this number to the closest integer. Some outcomes won&#8217;t be meaningful: i.e. if have three friends, then we need at least two bytes. However, we can encode four values with two bytes, therefore, we will need to repeat the selection if we get the invalid result.<\/p>\n<p>  <\/p>\n<p>So we can outline our algorithm:<\/p>\n<p>  <\/p>\n<ol>\n<li>Calculate the number of bytes <code>n<\/code> needed to represent all possible choices.<\/li>\n<li>Generate the sequence of bytes of size <code>n<\/code> at random. <\/li>\n<li>Convert the sequence of byte to a decimal number.<\/li>\n<li>Check whether the number has a meaning, i.e. whether this number has an associated choice. If the check was successful, return the number. Otherwise, repeat the process. <\/li>\n<\/ol>\n<p>  <\/p>\n<pre><code class=\"go\">func Select() Choice {     numberOfChoices := len(choices)     raw := math.Log2(float64(numberOfChoices))     n := int(math.Ceil(raw))                         var choice []int     for i := 0; i &lt; n; i++ {         trial := rand.Intn(2) \/\/ select at random `0` or `1`         choice = append(choice, trial)     }      var str string     for _, c := range choice {         str += strconv.Itoa(c)     }          \/\/ convert to a decimal     dec, err := strconv.ParseInt(str, 2, 0)     if err != nil {         panic(err)     }      if int(dec) >= numberOfChoices {         return Select()     }      return choices[dec] }<\/code><\/pre>\n<p>  <\/p>\n<p>Here we used a standard library function <code>ParseInt<\/code> to convert a string representation of a binary number to a decimal. We can avoid the double conversation from a binary integer to a string and then back a decimal integer, and do the direct conversion:<\/p>\n<p>  <\/p>\n<pre><code class=\"go\">var choice int for i := 0; i &lt; n; i++ {     trial := rand.Intn(2)     choice = choice*2 + trial }<\/code><\/pre>\n<p>  <\/p>\n<p>The rest of the function remains the same. Let&#8217;s write a simple benchmark to see whether the change made any difference. <\/p>\n<p>  <\/p>\n<pre><code class=\"go\">func Benchmark(b *testing.B) {     for i := 0; i &lt; b.N; i++ {         a := Select()         _ = a     } }  func Benchmark1(b *testing.B) {     for i := 0; i &lt; b.N; i++ {     a := Select1()     _ = a     } }<\/code><\/pre>\n<p>  <\/p>\n<p>The second version is two times faster than the first one.<\/p>\n<p>  <\/p>\n<p>Can we do better than that?<\/p>\n<p>  <\/p>\n<p>Let&#8217;s take a closer look at our task. We need to make <code>n<\/code> choices (choosing between <code>0<\/code> and <code>1<\/code>), where <code>n<\/code> is the number of bits. To do so we use a <code>for<\/code> loop and at every iteration, we add one bit of information to our final result. When we have selected all the required bits, we got a sequence of bits. This sequence of bits can be represented as a decimal number. This number, in turn, represents a particular friend that has been chosen to pay the bill. <\/p>\n<p>  <\/p>\n<p>We can employ left shift operation to build up the resulting decimal number. We start with <code>out<\/code> equal to zero, and at every iteration we shift <code>out<\/code> to the left by one bit, making space for the next bit. Then we select the next bit at random and assign it to variable <code>next<\/code>. After that we apply union operation to <code>out<\/code> and <code>next<\/code>, so updated <code>out<\/code> now also takes into account the currently selected bit. We repeat this process until we have selected enough bits to represent all friends, i.e. <code>2 ** bits<\/code> must become equal or larger than <code>len(choice)<\/code>. As function <code>math.Pow<\/code> in Golang defined only for floats, the above condition can be more succinctly represented using another left shift operation <code>(1 &lt;&lt; bits) &lt; len(choices)<\/code><\/p>\n<p>  <\/p>\n<pre><code class=\"go\">var bits, out int for (1 &lt;&lt; bits) &lt; len(choices) {     next := rand.Intn(2)     out = (out &lt;&lt; 1) | next     bits++ }<\/code><\/pre>\n<p>  <\/p>\n<p>In case if resulting <code>out<\/code> does not have a meaning, i.e. it does not represent any friend, we need to repeat the process again. <\/p>\n<p>  <\/p>\n<pre><code class=\"go\">func Select2() Choice {     for {         var bits, out int         for (1 &lt;&lt; bits) &lt; len(choices) {             next := rand.Intn(2)             out = (out &lt;&lt; 1) | next             bits++         }         if out &lt; len(choices) {             return choices[out]         }     } }<\/code><\/pre>\n<p>  <\/p>\n<p>According to the benchmark, this version is two times faster than our second version.<\/p>\n<p>  <\/p>\n<p>In this post, we implemented a random generator employing bit operations. More algorithmic patterns such as <a href=\"https:\/\/habr.com\/en\/post\/543618\/\">Matrix Spiral<\/a> or <a href=\"https:\/\/habr.com\/en\/post\/541130\/\">Dutch National Flag<\/a> can be found in the series <a href=\"https:\/\/habr.com\/en\/post\/545986\/\">Algorithms in Go<\/a>.<\/p>\n<\/div>\n<\/div>\n<\/div>\n<p><!----><!----><\/div>\n<p><!----><!----><br \/> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/articles\/551732\/\"> https:\/\/habr.com\/ru\/articles\/551732\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-1\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<p>This article is a part of <a href=\"https:\/\/habr.com\/en\/post\/545986\/\">Algorithms in Go<\/a> series where we discuss common algorithmic problems and their solution patterns.<\/p>\n<p>  <\/p>\n<p>In this edition, we take a closer look at bit manipulations. Bit operations can be extremely powerful and useful in an entire class of algorithmic problems, including problems that at first glance does not have to do anything with bits.<\/p>\n<p>  <\/p>\n<p>Let&#8217;s consider the following problem: six friends meet in the bar and decide who pays for the next round. They would like to select a random person among them for that. How can they do a random selection using only a single coin?<\/p>\n<p>  <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/yc\/nz\/lr\/ycnzlrd8b5cr5sie3ozgihwyfbg.png\" data-src=\"https:\/\/habrastorage.org\/webt\/yc\/nz\/lr\/ycnzlrd8b5cr5sie3ozgihwyfbg.png\"\/><\/p>\n<p>  <\/p>\n<p>The solution to this problem is not particularly obvious (for me:), so let&#8217;s simplify a problem for a moment to develop our understanding. How would we do the selection if there were only three friends? In other words, how would we &#171;mimic&#187; a three-sided coin with a two-sided coin?<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-395015","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/395015","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=395015"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/395015\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=395015"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=395015"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=395015"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}