{"id":108,"date":"2013-12-04T00:30:11","date_gmt":"2013-12-04T08:30:11","guid":{"rendered":"https:\/\/www.falatic.com\/?p=108"},"modified":"2013-12-04T00:30:11","modified_gmt":"2013-12-04T08:30:11","slug":"python-and-bitwise-rotation","status":"publish","type":"post","link":"https:\/\/www.falatic.com\/index.php\/108\/python-and-bitwise-rotation","title":{"rendered":"Python and Bitwise Rotation"},"content":{"rendered":"<p>The other day I found myself wondering how to perform bitwise rotations in Python, particular bit rotations (circular shifts). There&#8217;s lots of complex ways to do it &#8211;\u00a0<a href=\"http:\/\/pythonhosted.org\/bitstring\/index.html\" target=\"_blank\">bitstring<\/a>, <a href=\"https:\/\/pypi.python.org\/pypi\/bitarray\/\" target=\"_blank\">bitarray<\/a>, and others &#8211; but I wanted a more compact and efficient method.<\/p>\n<p>Turns out it&#8217;s relatively easy&#8230; <a href=\"http:\/\/en.wikipedia.org\/wiki\/Circular_shift\" target=\"_blank\">the C idiom for bitwise rotation<\/a> is a good starting point, but I&#8217;ve extended it to handle an arbitrary unsigned bit string (one that is first truncated to fit in the width of the virtual &#8220;register&#8221; we&#8217;re shifting in &#8211; just so it doesn&#8217;t go totally bonkers if it gets an &#8220;impossible&#8221; value). It&#8217;s also\u00a0robust enough to handle excessive rotations (where a value only <em>n<\/em> bits long is rotated more than <em>n<\/em> bits).<\/p>\n<p>Here it is along with some test code:<\/p>\n<pre class=\"brush: python; title: ; notranslate\" title=\"\">\r\n###########################################################################\r\n# Rotating bits (tested with Python 2.7)\r\n\r\nfrom __future__ import print_function   # PEP 3105\r\n\r\n# max bits &gt; 0 == width of the value in bits (e.g., int_16 -&gt; 16)\r\n\r\n# Rotate left: 0b1001 --&gt; 0b0011\r\nrol = lambda val, r_bits, max_bits: \\\r\n    (val &lt;&lt; r_bits%max_bits) &amp; (2**max_bits-1) | \\\r\n    ((val &amp; (2**max_bits-1)) &gt;&gt; (max_bits-(r_bits%max_bits)))\r\n\r\n# Rotate right: 0b1001 --&gt; 0b1100\r\nror = lambda val, r_bits, max_bits: \\\r\n    ((val &amp; (2**max_bits-1)) &gt;&gt; r_bits%max_bits) | \\\r\n    (val &lt;&lt; (max_bits-(r_bits%max_bits)) &amp; (2**max_bits-1))\r\n\r\nmax_bits = 16  # For fun, try 2, 17 or other arbitrary (positive!) values\r\n\r\nprint()\r\nfor i in xrange(0, max_bits*2-1):\r\n    value = 0xC000\r\n    newval = rol(value, i, max_bits)\r\n    print(&quot;0x%08x &lt;&lt; 0x%02x --&gt; 0x%08x&quot; % (value, i, newval))\r\n\r\nprint()\r\nfor i in xrange(0, max_bits*2-1):\r\n    value = 0x0003\r\n    newval = ror(value, i, max_bits)\r\n    print(&quot;0x%08x &gt;&gt; 0x%02x --&gt; 0x%08x&quot; % (value, i, newval))\r\n\r\n###########################################################################\r\n<\/pre>\n<!-- wpsso rrssb get buttons: buttons on archive option not enabled -->\n","protected":false},"excerpt":{"rendered":"<p>The other day I found myself wondering how to perform bitwise rotations in Python, particular bit rotations (circular shifts). There&#8217;s lots of complex ways to do it &#8211;\u00a0bitstring, bitarray, and <a href=\"https:\/\/www.falatic.com\/index.php\/108\/python-and-bitwise-rotation\" class=\"more-link\">[&hellip;]<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"Layout":"","footnotes":"","_links_to":"","_links_to_target":""},"categories":[86],"tags":[100],"class_list":["entry","author-marty","post-108","post","type-post","status-publish","format-standard","category-software-and-hardware-development","tag-python"],"_links":{"self":[{"href":"https:\/\/www.falatic.com\/index.php\/wp-json\/wp\/v2\/posts\/108","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.falatic.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.falatic.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.falatic.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.falatic.com\/index.php\/wp-json\/wp\/v2\/comments?post=108"}],"version-history":[{"count":0,"href":"https:\/\/www.falatic.com\/index.php\/wp-json\/wp\/v2\/posts\/108\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.falatic.com\/index.php\/wp-json\/wp\/v2\/media?parent=108"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.falatic.com\/index.php\/wp-json\/wp\/v2\/categories?post=108"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.falatic.com\/index.php\/wp-json\/wp\/v2\/tags?post=108"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}