{"id":8888,"date":"2021-11-28T19:30:37","date_gmt":"2021-11-29T03:30:37","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8888"},"modified":"2021-11-28T19:44:26","modified_gmt":"2021-11-29T03:44:26","slug":"leetcode-191-number-of-1-bits","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/bit\/leetcode-191-number-of-1-bits\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 191. Number of 1 Bits"},"content":{"rendered":"\n<p>Write a function that takes an unsigned integer and returns the number of &#8216;1&#8217; bits it has (also known as the&nbsp;<a href=\"http:\/\/en.wikipedia.org\/wiki\/Hamming_weight\" target=\"_blank\" rel=\"noreferrer noopener\">Hamming weight<\/a>).<\/p>\n\n\n\n<p><strong>Note:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer&#8217;s internal binary representation is the same, whether it is signed or unsigned.<\/li><li>In Java, the compiler represents the signed integers using&nbsp;<a href=\"https:\/\/en.wikipedia.org\/wiki\/Two%27s_complement\" target=\"_blank\" rel=\"noreferrer noopener\">2&#8217;s complement notation<\/a>. Therefore, in&nbsp;<strong>Example 3<\/strong>, the input represents the signed integer.&nbsp;<code>-3<\/code>.<\/li><\/ul>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 00000000000000000000000000001011\n<strong>Output:<\/strong> 3\n<strong>Explanation:<\/strong> The input binary string <strong>00000000000000000000000000001011<\/strong> has a total of three '1' bits.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 00000000000000000000000010000000\n<strong>Output:<\/strong> 1\n<strong>Explanation:<\/strong> The input binary string <strong>00000000000000000000000010000000<\/strong> has a total of one '1' bit.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 11111111111111111111111111111101\n<strong>Output:<\/strong> 31\n<strong>Explanation:<\/strong> The input binary string <strong>11111111111111111111111111111101<\/strong> has a total of thirty one '1' bits.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>The input must be a&nbsp;<strong>binary string<\/strong>&nbsp;of length&nbsp;<code>32<\/code>.<\/li><\/ul>\n\n\n\n<p><strong>Follow up:<\/strong>&nbsp;If this function is called many times, how would you optimize it?<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Bit Operation<\/strong><\/h2>\n\n\n\n<p>Use n &amp; 1 to get the lowest bit of n. <br>Use n &gt;&gt;= 1 to right shift n for 1 bit, e.g. removing the last bit.<\/p>\n\n\n\n<p>Time complexity: O(logn)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\/\/ Author: Huahua\nclass Solution {\npublic:\n  int hammingWeight(uint32_t n) {\n    int ans = 0;\n    while (n) {\n      ans += n & 1;\n      n >>= 1;\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Write a function that takes an unsigned integer and returns the number of &#8216;1&#8217; bits it has (also known as the&nbsp;Hamming weight). Note: Note that&#8230;<\/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],"class_list":["post-8888","post","type-post","status-publish","format-standard","hentry","category-bit","tag-bit","tag-easy","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8888","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=8888"}],"version-history":[{"count":5,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8888\/revisions"}],"predecessor-version":[{"id":8897,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8888\/revisions\/8897"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8888"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8888"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8888"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}