{"id":3144,"date":"2018-07-14T20:44:13","date_gmt":"2018-07-15T03:44:13","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=3144"},"modified":"2018-07-14T20:44:24","modified_gmt":"2018-07-15T03:44:24","slug":"leetcode-868-binary-gap","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/bit\/leetcode-868-binary-gap\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 868. Binary Gap"},"content":{"rendered":"

Problem<\/h1>\n

Given a positive\u00a0integer\u00a0N<\/code>, find and return the longest distance between two consecutive 1’s in the binary representation of\u00a0N<\/code>.<\/p>\n

If there aren’t two consecutive 1’s, return\u00a00<\/span>.<\/p>\n

Example 1:<\/strong><\/p>\n

Input: <\/strong>22<\/span>\r\nOutput: <\/strong>2\r\nExplanation: <\/strong>\r\n22 in binary is 0b10110.\r\nIn the binary representation of 22, there are three ones, and two consecutive pairs of 1's.\r\nThe first consecutive pair of 1's have distance 2.\r\nThe second consecutive pair of 1's have distance 1.\r\nThe answer is the largest of these two distances, which is 2.\r\n<\/pre>\n
Example 2:<\/strong><\/p>\n
Input: <\/strong>5<\/span>\r\nOutput: <\/strong>2<\/span>\r\nExplanation: <\/strong>\r\n5 in binary is 0b101.\r\n<\/pre>\n
Example 3:<\/strong><\/p>\n
Input: <\/strong>6<\/span>\r\nOutput: <\/strong>1<\/span>\r\nExplanation: <\/strong>\r\n6 in binary is 0b110.\r\n<\/pre>\n
Example 4:<\/strong><\/p>\n
Input: <\/strong>8<\/span>\r\nOutput: <\/strong>0<\/span>\r\nExplanation: <\/strong>\r\n8 in binary is 0b1000.\r\nThere aren't any consecutive pairs of 1's in the binary representation of 8, so we return 0.\\\r\n<\/pre>\n
Note:<\/strong><\/p>\n
    \n
  • 1 <= N <= 10^9<\/code><\/li>\n<\/ul>\n
    Solution: Bit<\/strong><\/h1>\n
    Time complexity: O(logN)<\/p>\n
    Space complexity: O(1)<\/p>\n
    C++<\/p>\n
    \/\/ Author: Huahua\r\n\/\/ Running time: 4 ms\r\nclass Solution {\r\npublic:\r\n  int binaryGap(int N) {\r\n    int l = -1;\r\n    int ans = 0;\r\n    for (int i = 0; i < 31; ++i)\r\n      if (N & (1 << i)) {\r\n        if (l >= 0)\r\n          ans = max(ans, i - l);\r\n        l = i;\r\n      }\r\n    return ans;\r\n  }\r\n};<\/pre>\n
     <\/p>\n","protected":false},"excerpt":{"rendered":"
    Problem Given a positive\u00a0integer\u00a0N, find and return the longest distance between two consecutive 1’s in the binary representation of\u00a0N. If there aren’t two consecutive 1’s,…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[126],"tags":[39,16,222],"class_list":["post-3144","post","type-post","status-publish","format-standard","hentry","category-bit","tag-binary","tag-bit","tag-easy","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3144","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=3144"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3144\/revisions"}],"predecessor-version":[{"id":3146,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3144\/revisions\/3146"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3144"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3144"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3144"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}