{"id":4974,"date":"2019-03-16T23:29:32","date_gmt":"2019-03-17T06:29:32","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4974"},"modified":"2019-03-16T23:31:22","modified_gmt":"2019-03-17T06:31:22","slug":"leetcode-1012-complement-of-base-10-integer","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/bit\/leetcode-1012-complement-of-base-10-integer\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1012. Complement of Base 10 Integer"},"content":{"rendered":"\n

Every non-negative integer N<\/code> has a binary representation.  For example, 5<\/code> can be represented as \"101\"<\/code> in binary, 11<\/code> as \"1011\"<\/code> in binary, and so on.  Note that except for N = 0<\/code>, there are no leading zeroes in any binary representation.<\/p>\n\n\n\n

The complement<\/em> of a binary representation is the number in binary you get when changing every 1<\/code> to a 0<\/code> and 0<\/code> to a 1<\/code>.  For example, the complement of \"101\"<\/code> in binary is \"010\"<\/code> in binary.<\/p>\n\n\n\n

For a given number N<\/code> in base-10, return the complement of it’s binary representation as a base-10 integer.<\/p>\n\n\n\n

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

Input: <\/strong>5\nOutput: <\/strong>2\nExplanation: <\/strong>5 is \"101\" in binary, with complement \"010\" in binary, which is 2 in base-10.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input: <\/strong>7\nOutput: <\/strong>0\nExplanation: <\/strong>7 is \"111\" in binary, with complement \"000\" in binary, which is 0 in base-10.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input: <\/strong>10\nOutput: <\/strong>5\nExplanation: <\/strong>10 is \"1010\" in binary, with complement \"0101\" in binary, which is 5 in base-10.\n<\/pre>\n\n\n\n
Note:<\/strong><\/p>\n\n\n\n
  1. 0 <= N < 10^9<\/code><\/li><\/ol>\n\n\n\n
    Solution: Bit<\/strong><\/h2>\n\n\n\n
    Find the smallest binary number c that is all 1s, (e.g. “111”, “11111”) that is greater or equal to N.
    ans = C ^ N or C – N<\/p>\n\n\n\n
    Time complexity: O(log(n))
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua, running time: 4 ms, 8 MB\nclass Solution {\npublic:\n  int bitwiseComplement(int N) {\n    int c = 1;\n    while (c < N) \n      c = (c << 1) | 1;\n    return N ^ c;    \n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Every non-negative integer N has a binary representation.  For example, 5 can be represented as “101” in binary, 11 as “1011” in binary, and so on.  Note that except for N = 0, there are no…<\/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":[16,222,459],"class_list":["post-4974","post","type-post","status-publish","format-standard","hentry","category-bit","tag-bit","tag-easy","tag-ologn","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4974","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=4974"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4974\/revisions"}],"predecessor-version":[{"id":4976,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4974\/revisions\/4976"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4974"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4974"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4974"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}