{"id":3420,"date":"2023-10-31T13:37:57","date_gmt":"2023-10-31T08:07:57","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=3420"},"modified":"2023-10-31T13:37:59","modified_gmt":"2023-10-31T08:07:59","slug":"xor-of-two-numbers","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/xor-of-two-numbers\/","title":{"rendered":"XOR of Two Numbers"},"content":{"rendered":"\n<div class=\"gutentoc tocactive nostyle\" style=\"max-width:400px\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#approach-1-naive-approach\">Approach 1 (Naive Approach)<\/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=\"#approach-2-using-other-bitwise-operators\">Approach 2 (Using other bitwise operators):<\/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=\"#approach-3using-the-xor-and-sum-property\">Approach 3(Using the XOR-AND-SUM Property)<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code---using-xor-amp-sum\">C++ Code &#8211; Using XOR &amp; SUM<\/a><\/li><li><a href=\"#java-code---using-xor-amp-sum-\">Java Code &#8211; Using XOR &amp; SUM <\/a><\/li><li><a href=\"#python-code---using-xor-amp-sum-\">Python Code &#8211; Using XOR &amp; SUM <\/a><\/li><li><a href=\"#complexity-analysis\">Complexity Analysis<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given 2 numbers, find their bitwise XOR, <strong>without<\/strong> using the bitwise XOR operator.<\/p>\n\n\n\n<p id=\"sample-test-cases\"><strong>Sample Test Cases<\/strong><\/p>\n\n\n\n<p><strong>Input 1:<\/strong> x = 3, y = 5<br><strong>Output 1:<\/strong> 6<br><strong>Explanation 1:<\/strong><\/p>\n\n\n\n<p>x = 011<br>y = 101<br>R = 110 = 6 (Taking the bitwise XOR)<\/p>\n\n\n\n<p><strong>Input 2:<\/strong> x = 1, y = 2<br><strong>Output 2:<\/strong> 3<br><strong>Explanation 2:<\/strong><\/p>\n\n\n\n<p>x = 001<br>y = 010<br>R = 011 = 3 (Taking the bitwise XOR)<\/p>\n\n\n\n<h2 id=\"approach-1-naive-approach\">Approach 1 (Naive Approach)<\/h2>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"912\"  height=\"619\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3422 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 912px) 100vw, 912px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1.png 912w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-300x204.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-768x521.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-380x258.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-550x373.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-800x543.png 800w\" ><\/figure>\n\n\n\n<p>In the naive approach, we can just simulate what the XOR operation does, i.e,<\/p>\n\n\n\n<ul><li>If the bits at the ith position are the same we put 0 at that position.<\/li><li>Else if the bits at the ith position are different we put 1 at that position.<\/li><\/ul>\n\n\n\n<p>We can easily do this by traversing over all the bits of the result and setting each bit of the result as told above. The implementation is done considering the numbers as 32-bit integers.<\/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 getXOR(int x, int y) {\n  int ans = 0;\n  for (int i = 0; i &lt;= 31; i++) {\n    if (((1 LL &lt;&lt; i) &amp; x) != ((1 LL &lt;&lt; i) &amp; y)) {\n      ans |= (1 LL &lt;&lt; i);\n    }\n  }\n  return ans;\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 getXOR(int x, int y) {\n  int res = 0;\n  for (int i = 0; i &lt;= 31; i++) {\n    if (((1 &lt;&lt; i) &amp; x) != ((1 &lt;&lt; i) &amp; y)) {\n      res |= (1 &lt;&lt; i);\n    }\n  }\n  return res;\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 getXOR(x, y):\n    res = 0\n    for i in range(32):\n        if ((1 &lt;&lt; i) &amp; x) != ((1 &lt;&lt; i) &amp; y):\n            res |= 1 &lt;&lt; i\n    return res<\/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(log<sub>2<\/sub>(n))<\/li><li>Space Complexity: O(1)<\/li><\/ul>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"approach-2-using-other-bitwise-operators\">Approach 2 (Using other bitwise operators):<\/h2>\n\n\n\n<p>We can optimize the above solution by simulating the XOR operation without using the for loop as follows:<\/p>\n\n\n\n<ul><li>We find all the bits where either x\u2019s or y\u2019s bits are set (Bitwise <strong>OR<\/strong> of the numbers).<\/li><li>We need to remove those set bits where both x and y are set (<strong> ~x OR ~y<\/strong>).<\/li><li>Bitwise <strong>AND<\/strong> of the above expressions gives the desired result.<\/li><\/ul>\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=\"\">int getXOR(int x, int y) {\n  return (x | y) &amp; (~x | ~y);\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 x, int y) {\n  return (x | y) &amp; (~x | ~y);\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(x, y):\n    return (x | y) &amp; (~x | ~y)<\/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<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"approach-3using-the-xor-and-sum-property\">Approach 3(Using the XOR-AND-SUM Property)<\/h2>\n\n\n\n<p>We can calculate the XOR of 2 numbers using the well-known property of XOR,<\/p>\n\n\n\n<p><strong>a + b = (a ^ b) + 2 * (a &amp; b)<\/strong><\/p>\n\n\n\n<h3 id=\"c-code---using-xor-amp-sum\"><span id=\"c-code-using-xor-sum\">C++ Code &#8211; Using XOR &amp; SUM<\/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=\"\">int getXOR(int x, int y) {\n  return (x + y) - 2 * (x &amp; y);\n}<\/pre>\n\n\n\n<h3 id=\"java-code---using-xor-amp-sum-\"><span id=\"java-code-using-xor-sum\">Java Code &#8211; Using XOR &amp; SUM <\/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 int getXOR(int x, int y) {\n  return (x + y) - 2 * (x &amp; y);\n}<\/pre>\n\n\n\n<h3 id=\"python-code---using-xor-amp-sum-\"><span id=\"python-code-using-xor-sum\">Python Code &#8211; Using XOR &amp; SUM <\/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 getXOR(x, y):\n    return (x + y) - 2 * (x &amp; y)<\/pre>\n\n\n\n<h3 id=\"complexity-analysis\">Complexity Analysis<\/h3>\n\n\n\n<ul><li>Time Complexity: O(1)<\/li><li>Space Complexity: O(1)<\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given 2 numbers, find their bitwise XOR, without using the bitwise XOR operator. Sample Test Cases&hellip;\n","protected":false},"author":5,"featured_media":3425,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","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":[537],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3420"}],"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=3420"}],"version-history":[{"count":4,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3420\/revisions"}],"predecessor-version":[{"id":25941,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3420\/revisions\/25941"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3425"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=3420"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=3420"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=3420"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}