{"id":503,"date":"2013-06-18T12:28:36","date_gmt":"2013-06-18T19:28:36","guid":{"rendered":"http:\/\/192.168.1.2\/wordpress\/?p=503"},"modified":"2013-07-26T14:46:54","modified_gmt":"2013-07-26T21:46:54","slug":"ctci-ch-5-3","status":"publish","type":"post","link":"http:\/\/cywang.no-ip.org\/wordpress\/?p=503","title":{"rendered":"CTCI: Ch. 5-3"},"content":{"rendered":"<p>\n\t<strong>Given a positive integer, print the next smallest and the next largest number that have the same number of 1 bits in their binary representation.<\/strong>\n<\/p>\n<p>\n\t<!--more-->\n<\/p>\n<pre class=\"brush:cpp;\">\r\nunsigned int checkOnes(int num)\r\n{\r\n    int count = 0;\r\n    while(num &gt; 0)\r\n    {\r\n        if(num % 2 == 1)\r\n            count++;\r\n            \r\n        num = num &gt;&gt; 1;\r\n    }\r\n    return count;\r\n}\r\nunsigned int getNextSmallest_BruteForce(unsigned int num)\r\n{\r\n    int originalOnes = checkOnes(num);\r\n    while(num &gt;0)\r\n    {\r\n        if( originalOnes == checkOnes(++num))\r\n            break;\r\n    }\r\n    return num;\r\n}\r\nunsigned int getNextLargest_BruteForce(unsigned int num)\r\n{\r\n    int originalOnes = checkOnes(num);\r\n    while(num &gt;0)\r\n    {\r\n        if( originalOnes == checkOnes(--num))\r\n            break;\r\n    }\r\n    return num;\r\n}\r\nunsigned int getNextLargest(unsigned int num)\r\n{\r\n    \/\/Find first 0\r\n    int firstZero = 0;\r\n    int count1 = 0;\r\n    int count0 = 0;\r\n    unsigned int tmp = num;\r\n    while(tmp &gt; 0)\r\n    {\r\n        \r\n        if(tmp % 2 == 0)\r\n        {\r\n            count0++;\r\n            break;\r\n        }\r\n        else\r\n        {\r\n            count1++;\r\n            firstZero++;\r\n            tmp = tmp &gt;&gt; 1;\r\n        }\r\n    }\r\n    tmp = tmp &gt;&gt; 1;\r\n    int oneNextFirstZero = firstZero+1;\r\n    while(tmp &gt; 0)\r\n    {\r\n        \r\n        if(tmp % 2 == 1)\r\n        {\r\n            count1++;\r\n            break;\r\n        }\r\n        else\r\n        {\r\n            count0++;\r\n            oneNextFirstZero++;\r\n            tmp = tmp &gt;&gt; 1;\r\n        }\r\n    }\r\n    \/\/Set 0s from 0~oneNextFirstZero\r\n    num = (num &gt;&gt; (oneNextFirstZero+1))&lt;&lt;(oneNextFirstZero+1);\r\n    count0--; \/\/bit oneNextFirstZero has been set to 0;\r\n    \r\n    unsigned int allOnes = ~0;\r\n    allOnes = ~(allOnes &lt;&lt; count1);\r\n    allOnes &lt;&lt;= count0;\r\n    return num | allOnes;\r\n}\r\n\r\nunsigned int getNextSmallest(unsigned int num)\r\n{\r\n    \/\/Find first 1\r\n    int firstOne = 0;\r\n    int count1 = 0;\r\n    int count0 = 0;\r\n    unsigned int tmp = num;\r\n    while(tmp &gt; 0)\r\n    {\r\n        \r\n        if(tmp % 2 == 1)\r\n        {\r\n            count1++;\r\n            break;\r\n        }\r\n        else\r\n        {\r\n            count0++;\r\n            firstOne++;\r\n            tmp = tmp &gt;&gt; 1;\r\n        }\r\n    }\r\n    tmp = tmp &gt;&gt; 1;\r\n    int zeroNextFirstOne = firstOne + 1;\r\n    while(tmp &gt; 0)\r\n    {\r\n        \r\n        if(tmp % 2 == 0)\r\n        {\r\n            count0++;\r\n            break;\r\n        }\r\n        else\r\n        {\r\n            zeroNextFirstOne++;\r\n            count1++;\r\n            tmp = tmp &gt;&gt; 1;\r\n        }\r\n    }\r\n    if( (count1 + count0) == 32 || (count0+count1) == 0)\r\n        return -1;\r\n    \/\/Set zeroNextFirstOne to 1\r\n    num = (1&lt;&lt;zeroNextFirstOne) | num;\r\n\r\n    num = (num &gt;&gt; (count0 + count1 -1 )) &lt;&lt; (count0 + count1 -1);\r\n    unsigned int mask;\r\n    \/\/One 1 has been set, thus count1-1\r\n    mask = (1 &lt;&lt; (count1-1)) -1;\r\n    \r\n    return num | mask;\r\n}<\/pre>\n<p>\n\t&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Given a positive integer, print the next smallest and the next largest number that have the same number of 1 bits in their binary representation.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_exactmetrics_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":""},"categories":[23,6],"tags":[],"class_list":["post-503","post","type-post","status-publish","format-standard","hentry","category-chapter-5-bit-manipulation","category-cracking-the-coding-interview"],"_links":{"self":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/503","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=503"}],"version-history":[{"count":3,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/503\/revisions"}],"predecessor-version":[{"id":518,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/503\/revisions\/518"}],"wp:attachment":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=503"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=503"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=503"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}