{"id":4305,"date":"2021-11-26T11:31:18","date_gmt":"2021-11-26T06:01:18","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=4305"},"modified":"2021-11-26T11:31:19","modified_gmt":"2021-11-26T06:01:19","slug":"bit-manipulation","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/bit-manipulation\/","title":{"rendered":"Bit Manipulation (Complete Guide)"},"content":{"rendered":"\n<div class=\"gutentoc tocactive nostyle\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"text_open\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#what-is-bit-manipulation\">What is Bit Manipulation?<\/a><\/li><li><a href=\"#check-if-a-number-is-a-power-of-2\">Check if a number is a power of 2:<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><li><a href=\"#complexity-analysis\">Complexity Analysis<\/a><\/li><\/ul><li><a href=\"#swapping-2-numbers-using-bitwise-operators\">Swapping 2 Numbers using Bitwise Operators:<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation\">C++ Implementation<\/a><\/li><li><a href=\"#java-implementation\">Java Implementation<\/a><\/li><li><a href=\"#python-implementation\">Python Implementation<\/a><\/li><li><a href=\"#complexity-analysis\">Complexity Analysis<\/a><\/li><\/ul><li><a href=\"#xor-of-numbers-from-1-n\">XOR of numbers from [1, n]:<\/a><\/li><li><a href=\"#c-code\">C++ Code<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><li><a href=\"#complexity-analysis\">Complexity Analysis<\/a><\/li><\/ul><li><a href=\"#finding-the-msb-in-a-fixed-size-integer\">Finding the MSB in a Fixed-Size Integer<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation\">C++ Implementation<\/a><\/li><li><a href=\"#java-implementation\">Java Implementation<\/a><\/li><li><a href=\"#python-implementation\">Python Implementation<\/a><\/li><li><a href=\"#complexity-analysis\">Complexity Analysis<\/a><\/li><\/ul><li><a href=\"#faqs\">FAQs<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"what-is-bit-manipulation\">What is Bit Manipulation?<\/h2>\n\n\n\n<p><strong>Bit Manipulation<\/strong> is a collection of techniques that allows us to solve various problems by leveraging the <strong>binary representation<\/strong> of a number and its bits. Here, in this article, some interesting bit manipulation techniques and algorithms are described below:<\/p>\n\n\n\n<h2 id=\"check-if-a-number-is-a-power-of-2\">Check if a number is a power of 2:<\/h2>\n\n\n\n<p>A nice Bit Manipulation based approach to solve this problem is to observe the fact that all powers of two have only <strong>1 bit (MSB)<\/strong> set in their binary representation. So, when we subtract 1 from any power of 2, the set bit gets unset, and all the bits coming after it, gets set. Performing the <strong>bitwise AND<\/strong> of these two numbers, we should get the result as zero, if the original number was a power of 2.<\/p>\n\n\n\n<p>An <strong>edge case<\/strong> to consider in this approach is that this approach will not work if <strong>n = 0<\/strong>, so we need to handle this case separately.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"512\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-4476 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-19-1024x512.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-19-1024x512.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-19-300x150.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-19-768x384.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-19-380x190.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-19-550x275.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-19-800x400.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-19-1160x580.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-19.png 1200w\" ><\/figure>\n\n\n\n<h3 id=\"c-code\">C++ Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">bool checkIfPowerOf2(int n) {\n  n = abs(n);\n  return n &amp;amp;&amp;amp; (!(n &amp;amp; (n - 1)));\n}<\/pre>\n\n\n\n<h3 id=\"java-code\"><span id=\"java-code-2\">Java Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public static boolean checkIfPowerOf2(int n) {\n  n = Math.abs(n);\n  return (n > 0) &amp;amp;&amp;amp; (((n &amp;amp; (n - 1)) == 0));\n}<\/pre>\n\n\n\n<h3 id=\"python-code\"><span id=\"python-code-2\">Python Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def checkIfPowerOf2(n):\n    n = abs(n)\n    return n and (not (n &amp;amp; (n - 1)))<\/pre>\n\n\n\n<h3 id=\"complexity-analysis\"><span id=\"complexity-analysis-2\">Complexity Analysis<\/span><\/h3>\n\n\n\n<ul><li>Time Complexity: O(1)<\/li><li>Space Complexity: O(1)<\/li><\/ul>\n\n\n\n<h2 id=\"swapping-2-numbers-using-bitwise-operators\">Swapping 2 Numbers using Bitwise Operators:<\/h2>\n\n\n\n<p>We can swap 2 numbers without using the 3rd variable, by using the <strong>bitwise XOR <\/strong>operator.\u00a0 Note that the bitwise XOR of 2 numbers returns a number that has those bits set, which are <strong>unset in one of the numbers and set in the other number.<\/strong> Using this number, if XOR it with our original numbers in reverse order, we will be able to recover back our original numbers, but now in <strong>swapped<\/strong> condition.<\/p>\n\n\n\n<h3 id=\"c-implementation\"><span id=\"c-implementation-2\">C++ Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">void swap(int &amp;amp;a, int &amp;amp;b) {\n    cout &amp;lt;&amp;lt; \"Before Swapping:\" &amp;lt;&amp;lt; endl;\n    cout &amp;lt;&amp;lt; a &amp;lt;&amp;lt; \" \" &amp;lt;&amp;lt; b &amp;lt;&amp;lt; endl;\n    a ^= b;\n    b ^= a;\n    a ^= b;\n    cout &amp;lt;&amp;lt; \"After Swapping:\" &amp;lt;&amp;lt; endl;\n    cout &amp;lt;&amp;lt; a &amp;lt;&amp;lt; \" \" &amp;lt;&amp;lt; b &amp;lt;&amp;lt; endl;\n<\/pre>\n\n\n\n<h3 id=\"java-implementation\"><span id=\"java-implementation-2\">Java Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public static void swap(int a, int b) {\n        System.out.println(\"Before Swapping:\");\n        System.out.println(a + \" \" + b);\n        a ^= b;\n        b ^= a;\n        a ^= b;\n        System.out.println(\"After Swapping:\");\n        System.out.println(a + \" \" + b);\n    }<\/pre>\n\n\n\n<h3 id=\"python-implementation\"><span id=\"python-implementation-2\">Python Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def swap(a, b):\n    print(\"Before Swapping:\")\n    print(a, b)\n    a ^= b\n    b ^= a\n    a ^= b\n    print(\"After Swapping:\")\n    print(a, b)<\/pre>\n\n\n\n<h3 id=\"complexity-analysis\"><span id=\"complexity-analysis-3\">Complexity Analysis<\/span><\/h3>\n\n\n\n<ul><li>Time Complexity: O(1)<\/li><li>Space Complexity: O(1)<\/li><\/ul>\n\n\n\n<h2 id=\"xor-of-numbers-from-1-n\">XOR of numbers from [1, n]:<\/h2>\n\n\n\n<p>The XOR of all numbers in the range <strong>[1, n]<\/strong> can be efficiently calculated using the following formula:<\/p>\n\n\n\n<ul><li>If <strong>n % 4 = 0<\/strong>, the answer is <strong>n<\/strong>.<\/li><li>If <strong>n % 4 = 1<\/strong>, the answer is <strong>1<\/strong>.<\/li><li>If <strong>n % 4 = 2<\/strong>, the answer is <strong>n + 1<\/strong>.<\/li><li>If <strong>n % 4 = 3<\/strong>, the answer is <strong>0<\/strong>.<\/li><\/ul>\n\n\n\n<p>This formula can be observed by<strong> brute-forcing<\/strong> the answers for some small <strong>n<\/strong> and then finding the pattern in the answers.<\/p>\n\n\n\n<h2 id=\"c-code\"><span id=\"c-code-2\">C++ Code<\/span><\/h2>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int getXOR(int n) {\n    if(n % 4 == 0) {\n        return n;\n    }\n    else if(n % 4 == 1) {\n        return 1;\n    }\n    else if(n % 4 == 2) {\n        return ++n;\n    }\n    else {\n        return 0;\n    }\n}<\/pre>\n\n\n\n<h3 id=\"java-code\">Java Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public static int getXOR(int n) {\n        if(n % 4 == 0) {\n            return n;\n        }\n        else if(n % 4 == 1) {\n            return 1;\n        }\n        else if(n % 4 == 2) {\n            return ++n;\n        }\n        else {\n            return 0;\n        }\n    }<\/pre>\n\n\n\n<h3 id=\"python-code\">Python Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def getXOR(n):\n    if n % 4 == 0:\n        return n\n    elif n % 4 == 1:\n        return 1\n    elif n % 4 == 2:\n        return n + 1\n    else:\n        return 0<\/pre>\n\n\n\n<h3 id=\"complexity-analysis\"><span id=\"complexity-analysis-4\">Complexity Analysis<\/span><\/h3>\n\n\n\n<ul><li><strong>Time Complexity:<\/strong> O(1)<\/li><li><strong>Space Complexity:<\/strong> O(1)<\/li><\/ul>\n\n\n\n<h2 id=\"finding-the-msb-in-a-fixed-size-integer\">Finding the MSB in a Fixed-Size Integer<\/h2>\n\n\n\n<p>Suppose that we are dealing with 32-bit integers. The approach here is to <strong>set all the bits<\/strong> of the number, and then add 1 to it, so that only a bit, which appears after the <strong>MSB<\/strong> is set. Then we can just <strong>divide the number by 2<\/strong>, and return the answer.<\/p>\n\n\n\n<h3 id=\"c-implementation\">C++ Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int setBit(int n) {\n  n |= (n >> 1);\n  n |= (n >> 2);\n  n |= (n >> 4);\n  n |= (n >> 8);\n  n |= (n >> 16);\n  n++;\n  n >>= 1;\n  return n;\n<\/pre>\n\n\n\n<h3 id=\"java-implementation\">Java Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public static int setBit(int n) {\n  n |= (n >> 1);\n  n |= (n >> 2);\n  n |= (n >> 4);\n  n |= (n >> 8);\n  n |= (n >> 16);\n  n++;\n  n >>= 1;\n  return n;\n}<\/pre>\n\n\n\n<h3 id=\"python-implementation\">Python Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def setBit(n):\n    n |= (n >> 1);\n    n |= (n >> 2);\n    n |= (n >> 4);\n    n |= (n >> 8);\n    n |= (n >> 16);\n    n += 1;\n    n >>= 1;\n    return n;<\/pre>\n\n\n\n<h3 id=\"complexity-analysis\">Complexity Analysis<\/h3>\n\n\n\n<ul><li><strong>Time Complexity:<\/strong> O(1)<\/li><li><strong>Space Complexity:<\/strong> O(1)<\/li><\/ul>\n\n\n\n<h2 id=\"faqs\">FAQs<\/h2>\n\n\n\n<p><strong>Q. What is meant by a bit being set or unset?<\/strong><br>A. If a bit has value 1, it is said to be set, else it is said to be unset.<\/p>\n\n\n\n<p><strong>Q. How many bits are present in a number\u2019s binary representation?<\/strong><br>A. <strong>floor<\/strong>(<strong>log<sub>2<\/sub>n) + 1<\/strong> bits are present in a number\u2019s binary representation.<\/p>\n","protected":false},"excerpt":{"rendered":"What is Bit Manipulation? Bit Manipulation is a collection of techniques that allows us to solve various problems&hellip;\n","protected":false},"author":5,"featured_media":4477,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[615],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4305"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=4305"}],"version-history":[{"count":4,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4305\/revisions"}],"predecessor-version":[{"id":4478,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4305\/revisions\/4478"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/4477"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=4305"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=4305"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=4305"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}