下次自动登录
现在的位置:
& 综合 & 正文
Java算法总结：输入一个整数，求该整数的二进制表示中有多少个1
求一个整数的二进制中1的个数。
题目：输入一个整数，求该整数的二进制表达中有多少个1。例如输入10，由于其二进制表示为1010，有两个1，因此输出2。
分析：这是一道很基本的考查位运算的面试题。包括微软在内的很多公司都曾采用过这道题。
一个很基本的想法是：我们先判断整数的最右边一位是不是1。接着把整数右移一位，原来处于右边第二位的数字现在被移到第一位了，再判断是不是1。这样每次移动一位，直到这个整数变成0为止。现在的问题变成怎样判断一个整数的最右边一位是不是1了。很简单，如果它和整数1作与运算。由于1除了最右边一位以外，其他所有位都为0。因此如果与运算的结果为1，表示整数的最右边一位是1，否则是0。
1int NumberOf1_Solution1(int i)
int count = 0;
i = i && 1;
可能有读者会问，整数右移一位在数学上是和除以2是等价的。那可不可以把上面的代码中的右移运算符换成除以2呢？答案是最好不要换成除法。因为除法的效率比移位运算要低的多，在实际编程中如果可以应尽可能地用移位运算符代替乘除法。
这个思路当输入i是正数时没有问题，但当输入的i是一个负数时，不但不能得到正确的1的个数，还将导致死循环。以负数0x为例，右移一位的时候，并不是简单地把最高位的1移到第二位变成0x，而是0xC0000000。这是因为移位前是个负数，仍然要保证移位后是个负数，因此移位后的最高位会设为1。如果一直做右移运算，最终这个数字就会变成0xFFFFFFFF而陷入死循环。
为了避免死循环，我们可以不右移输入的数字i。首先i和1做与运算，判断i的最低位是不是为1。接着把1左移一位得到2，再和i做与运算，就能判断i的次高位是不是1……这样反复左移，每次都能判断i的其中一位是不是1。基于此，我们得到如下代码：
1 int NumberOf1_Solution2(int i)
int count = 0;
unsigned int flag = 1;
while(flag)
if(i & flag)
flag = flag && 1;
另外一种思路是如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减去1，那么原来处在整数最右边的1就会变成0，原来在1后面的所有的0都会变成1。其余的所有位将不受到影响。举个例子：一个二进制数1100，从右边数起的第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成1，而前面的1保持不变，因此得到结果是1011。
我们发现减1的结果是把从最右边一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。如00。也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0。那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。
这种思路对应的代码如下：
1int NumberOf1_Solution3(int i)
3 int count=0;
4 while (i)
7 i = (i-1)&
扩展：如何用一个语句判断一个整数是不是二的整数次幂？
PS：n&(n-1)==0;//二进制数只有一位位1，则该数是2的整数次幂.简单查表，相对来说效率也不错。
1 int countBits(int value)
int count=0;
int bits4[]={0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
while(value!=0)
count+=bits4[value&0xf];
value&&=4;
&&&&推荐文章:
【上篇】【下篇】计算一个整数有的二进制表示中多少个 1 - 知乎专栏
{"debug":false,"apiRoot":"","paySDK":"/api/js","wechatConfigAPI":"/api/wechat/jssdkconfig","name":"production","instance":"column","tokens":{"X-XSRF-TOKEN":null,"X-UDID":null,"Authorization":"oauth c3cef7c66aa9e6a1e3160e20"}}
{"database":{"Post":{"":{"title":"计算一个整数有的二进制表示中多少个 1","author":"charles-wang-42","content":"计算一个整数有的二进制表示中多少个 1 17:30:23很早以前记着有这么一个技巧，计算一个整数的二进制表示多少个 1 。template &typename T&\nint count(T a) {\n
int ret = 0;\n
for (T x = a; x; x &= ~(x - 1) ^ x) {\n
return ret;\n}\n例如输出结果0x0 -& 0\n 0x1 -& 1\n 0x2 -& 1\n 0x3 -& 2\n 0x4 -& 1\n 0x5 -& 2\n 0x6 -& 2\n 0x7 -& 3\n 0x8 -& 1\n 0x9 -& 2\n 0xa -& 2\n 0xb -& 3\n 0xc -& 2\n 0xd -& 3\n 0xe -& 3\n 0xf -& 4\n这个是怎么工作的呢？如果 a 是零，程序返回零。这个很容易看得出来。 如果不是零，那么假设 x 可以表示成为 b1 b2 b3 b4 1 0 0 0 ... 结尾有 N 个 0 ，一个 1 。 b1 ... b4 有可能是 0 或者 1那么 x-1 可以表示成为 b1 b2 b3 b4 0 1 1 1 ... 。(x-1)^x 可以表示成为 ... 因为 b1 ^ b1 = 0 无论 b1 是 0 or 1 。这样的我们得到一个 mask ， x&= ~mask 就可以消除掉 x 最低位的一个 1 。于是不停地重复，需要重复几次，就说明有多少个 1 。于是我们的返回值就是简单计数器，计算循环了多少次。这个严格上来说，效率比较高。因为循环次数是 1 的个数。这个技巧属于完全无用的技巧，如果从可读性的角度来说，下面的代码的可读性更好。template &typename T&\nint count2(T a) {\n
int ret = 0;\n
T pin = 1;\n
for (size_t i = 0; i & sizeof(T); ++i, pin&&=1){\n
if(pin&a) ret++;\n
return ret;\n}\n对于喜欢装 13 的，抗击打能力比较强的，不怕挨揍的，的那些人，可以考虑在生产代码里面采用第一种姿势。后果自负。","updated":"T10:20:39.000Z","canComment":false,"commentPermission":"anyone","commentCount":0,"collapsedCount":0,"likeCount":0,"state":"published","isLiked":false,"slug":"","isTitleImageFullScreen":false,"rating":"none","titleImage":"","links":{"comments":"/api/posts//comments"},"reviewers":[],"topics":[{"url":"/topic/","id":"","name":"C / C++"}],"adminClosedComment":false,"titleImageSize":{"width":0,"height":0},"href":"/api/posts/","excerptTitle":"","column":{"slug":"wcy123","name":"wcy123 专栏"},"tipjarState":"inactivated","annotationAction":[],"sourceUrl":"","pageCommentsCount":0,"snapshotUrl":"","publishedTime":"T18:20:39+08:00","url":"/p/","lastestLikers":[],"summary":" 计算一个整数有的二进制表示中多少个
17:30:23很早以前记着有这么一个技巧，计算一个整数的二进制表示多少个 1 。template &typename T&\nint count(T a) {\n int ret = 0;\n for (T x = x &= ~(x - 1…","reviewingCommentsCount":0,"meta":{"previous":{"isTitleImageFullScreen":false,"rating":"none","titleImage":"","links":{"comments":"/api/posts//comments"},"topics":[{"url":"/topic/","id":"","name":"C++"}],"adminClosedComment":false,"href":"/api/posts/","excerptTitle":"","author":{"bio":"个人主页被 58 人浏览","isFollowing":false,"hash":"6bceabf72fd07bbe09e009b","uid":16,"isOrg":false,"slug":"charles-wang-42","isFollowed":false,"description":"你好","name":"wcy123","profileUrl":"/people/charles-wang-42","avatar":{"id":"54f291a568dc765e215ebe4eb86c705b","template":"/{id}_{size}.jpg"},"isOrgWhiteList":false},"content":" 20:21:24介绍本文试图通过迭代编程，一点一点改进一个关于 list 操作的程序。基本结构struct List {\n
int value;\n
struct List * next;\n};\n这是一个单链表结构。#include &iostream& \nusing namespace std;\n\nstruct List {\n
int value;\n
struct List * next;\n};\n\nList * MakeList (int value, List * next) {\n
return new List{value, next};\n}\n\nostream& operator&&(ostream& out, const List* head) {\n
out && \"(\";\n
for(auto i = head; i ; i = i-&next){\n
out && \" \" && i-&value;\n
out && \")\";\n
return out;\n}\n\nint main(int argc, char *argv[])\n{\n
List * lst = MakeList(1, MakeList(2, MakeList(3, nullptr)));\n
cout && lst && endl;\n
return 0;\n}\n输出结果( 1 2 3)\n使用构造函数上面的程序没有使用构造函数，使用构造函数，看起来更加清晰。#include &iostream& \nusing namespace std;\n\nclass List {\n
List(): head_(nullptr) {};\n
void push_front(int value) {\n
head_ = new Cons(value, head_);\n
bool empty() {\n
return head_ == nullptr;\n
private:\n
struct Cons{\n
Cons(int value, Cons* next) : value_(value), next_(next) {}\n
int value_;\n
struct Cons* next_;\n
Cons * head_;\n
friend ostream& operator&&(ostream& out, const List& lst);\n};\n\nostream& operator&&(ostream& out, const List& lst) {\n
out && \"(\";\n
for (auto i = lst.head_; i; i = i-&next_) {\n
out && \" \" && i-&value_;\n
out && \")\";\n
return out;\n}\n\nint main(int argc, char* argv[]) {\n
List lst;\n
lst.push_front(1);\n
lst.push_front(2);\n
lst.push_front(3);\n
cout && lst && endl;\n
return 0;\n}\n输出结果( 3 2 1)\nCons 名字来源于 Lisp 系列语言。防止内存泄露上面的程序明显有内存泄露，我们使用智能指针，来防止内存泄露。#include &iostream& \n#include &memory& \nusing namespace std;\n\nclass List {\n
List() : head_(nullptr){};\n
void push_front(int value) {\n
head_ = make_unique&Cons&(value, std::move(head_));\n
bool empty() { return head_ == nullptr; }\n\n
private:\n
struct Cons {\n
Cons(int value, unique_ptr&Cons&&& next)\n
: value_(value), next_(std::move(next)) {}\n
int value_;\n
unique_ptr&Cons& next_;\n
unique_ptr&Cons& head_;\n
friend ostream& operator&&(ostream& out, const List& lst);\n};\n\nostream& operator&&(ostream& out, const List& lst) {\n
out && \"(\";\n
for (auto i = lst.head_.get(); i; i = i-&next_.get()) {\n
out && \" \" && i-&value_;\n
out && \")\";\n
return out;\n}\n\nint main(int argc, char* argv[]) {\n
List lst;\n
lst.push_front(1);\n
lst.push_front(2);\n
lst.push_front(3);\n
cout && lst && endl;\n
return 0;\n}\n输出结果( 3 2 1)\n很遗憾， make_unique 是 c++14 的内容，如果必须使用 c++11 ，那么就需要我们自己实现一下这个函数。#if __cplusplus &= 201103L namespace std {\n
template&typename T, typename ...Args&\n
unique_ptr&T& make_unique(Args &&...args) {\n
return std::unique_ptr&T&(new T(std::forward&Args&(args)...));\n
}\n}\n使用了 unique_ptr ，我们失去了一个功能，两个 list 不能共享同一段尾巴。也许这是一个好的交换，当两个 list 共享同一段尾巴的时候，需要使用 shared_ptr ，而 unique_ptr 的开销和裸指针一样，效率很高。在大多数情况下，我们不需要这种共享数据。从其他 container 构造一个 list#include &iostream& \n#include &memory& \n#include &vector& \nusing namespace std;\n\nclass List {\n
List() : head_(nullptr){};\n\n
template &typename Iter&\n
List(Iter begin, Iter end) : head_() {\n
for (auto it = begin; it != end; ++it) {\n
push_front(*it);\n
List(const std::initializer_list&int&& c) : List(c.begin(), c.end()) {}\n\n
template &typename Container&\n
List(const Container& c) : List(c.begin(), c.end()) {}\n\n
void push_front(int value) {\n
head_ = make_unique&Cons&(value, std::move(head_));\n
bool empty() { return head_ == nullptr; }\n\n
private:\n
struct Cons {\n
Cons(int value, unique_ptr&Cons&&& next)\n
: value_(value), next_(std::move(next)) {}\n
int value_;\n
unique_ptr&Cons& next_;\n
unique_ptr&Cons& head_;\n
friend ostream& operator&&(ostream& out, const List& lst);\n};\n\nostream& operator&&(ostream& out, const List& lst) {\n
out && \"(\";\n
for (auto i = lst.head_.get(); i; i = i-&next_.get()) {\n
out && \" \" && i-&value_;\n
out && \")\";\n
return out;\n}\n\nint main(int argc, char* argv[]) {\n
auto lst1 = List{1, 2, 3};\n
cout && lst1 && endl;\n\n
vector&int& v1 = {4, 5, 6};\n
auto lst2 = List(v1);\n
cout && lst2 && endl;\n
return 0;\n}\n输出结果( 3 2 1)\n( 6 5 4)\n这里用到了 c++11 的 delegating constructors, 也就是一个构造函数，调用另一个构造函数。高效的 append 操作上面的例子中，我们看到列表顺序是反的。我们要顺序的追加操作，而不是从 head 插入。这个是写本文的出发点。前面都是铺垫。本文参考在 linux 的内核代码代码中的方法。首先我们来一个简单实现。void push_back(int value) {\n
if (!head_) {\n
head_ = make_unique&Cons&(value, nullptr);\n
} else {\n
Cons* p = nullptr;\n
for (p = head_.get(); p-&next_; p = p-&next_.get()) {\n
p-&next_ = make_unique&Cons&(value, nullptr);\n
}\n这个方法有两个问题，一个是多了一个 if 判断语句，一个是多了 for 循环语句。好的代码风格是尽量没有if for 这些语句。性能也有一点问题，每插入一个元素，都要遍历一次列表。linux kernel 的源代码里面用间接指针，struct Cons ** tail_ ，很巧妙的实现了这个功能。我们先简单理解没有智能指针的版本。当列表为空的时候tail_ == &head_;\nhead_ == NULL;\n当有一个元素的时候。Cons e1 = {1, nullptr};\nhead_ == &e1;\ntail_ == &head_-&next;\n当有两个元素的时候。Cons e2 = {2, nullptr};\nCons e1 = {1, &e2};\nhead_ == &e1;\ntail_ == &head_-&next-&next;\n依次类推。增加一个间接指针之后，当我们遍历列表的时候，我们不但知道列表元素，而且还知道我们从哪里过来的。tail_ 永远不会是指向一个无效地址。 assert(*tail_ != nullptr);当列表为空的时候，*tail_ == &head ，即指向 head_ 的地址。当列表不为空的时候， *tail_ == &last.next ，即指向最后一个元素的 next 的地址。我们要追加一个元素的时候。(*tail_) = &new_entry;\ntail_ = &new_enty.next_;\n就可以了。为什么呢？如果列表为空，(*tail_)=&new_entry 导致 head_ = &new_entry如果列表不为空，(*tail_) = &new_entry 导致 last.next_ = &new_entry然后，tail_ = &new_entry.next_ 保证 tail_ 一直指向列表最后一个元素的 next 的地址。下面是带有智能指针的代码。#include &iostream& \n#include &memory& \n#include &vector& \nusing namespace std;\n\nclass List {\n
List() : head_(nullptr), tail_(&head_){};\n\n
template &typename Iter&\n
List(Iter begin, Iter end) : head_(), tail_(&head_) {\n
for (auto it = begin; it != end; ++it) {\n
push_back(*it);\n
List(const std::initializer_list&int&& c) : List(c.begin(), c.end()) {}\n\n
template &typename Container&\n
List(const Container& c) : List(c.begin(), c.end()) {}\n\n
void push_front(int value) {\n
head_ = make_unique&Cons&(value, std::move(head_));\n
void push_back(int value) {\n
(*tail_) = make_unique&Cons&(value, nullptr);\n
tail_ = &(*tail_)-&next_;\n
void remove(int value) {\n
(*tail_) = make_unique&Cons&(value, nullptr);\n
tail_ = &(*tail_)-&next_;\n
bool empty() { return head_ == nullptr; }\n\n
private:\n
struct Cons {\n
Cons(int value, unique_ptr&Cons&&& next)\n
: value_(value), next_(std::move(next)) {}\n
int value_;\n
unique_ptr&Cons& next_;\n
unique_ptr&Cons& head_;\n
unique_ptr&Cons& * tail_;\n
friend ostream& operator&&(ostream& out, const List& lst);\n};\n\nostream& operator&&(ostream& out, const List& lst) {\n
out && \"(\";\n
for (auto i = lst.head_.get(); i; i = i-&next_.get()) {\n
out && \" \" && i-&value_;\n
out && \")\";\n
return out;\n}\n\nint main(int argc, char* argv[]) {\n
auto lst1 = List{1, 2, 3};\n
cout && lst1 && endl;\n\n
vector&int& v1 = {4, 5, 6};\n
auto lst2 = List(v1);\n
cout && lst2 && endl;\n
return 0;\n}\n输出结果( 1 2 3)\n( 4 5 6)\n其中关键代码是void push_back(int value) {\n
(*tail_) = make_unique&Cons&(value, nullptr);\n
tail_ = &(*tail_)-&next_;\n
}\n删除一个元素先来一个普通版本。void remove(int value) {\n
Cons * p = nullptr;\n
for (auto i = head_.get(); i; p = i, i = i-&next_.get()) {\n
if (i-&value_ == value) {\n
p-&next_ = std::move(i-&next_);\n
}\n这个版本是有 bug 的，如果删除的是第一个元素，就挂了，因为 p 是 nullptr.void remove(int value) {\n
Cons * p = nullptr;\n
for (auto i = head_.get(); i; p = i, i = i-&next_.get()) {\n
if (i-&value_ == value) {\n
if (p != nullptr) {\n
p-&next_ = std::move(i-&next_);\n
} else {\n
head_ = std::move(head_-&next_);\n
}\n这个版本工作，但是多了一个 if 判断，让代码看起来不是那么的帅气。利用间接指针，我们可以帅气的解决这个问题。void remove(int value) {\n
for (auto i = &head_; *i; i = &((*i)-&next_)) {\n
if ((*i)-&value_ == value) {\n
(*i) = std::move((*i)-&next_);\n
}\n这个代码为什么能工作？ 和 tail_ 类似，在遍历的过程中 i 是一个间接指针。i 是指向遍历的对象指针的指针。*i 永远不会为 nullptr当列表为空的时候， *i 指向头指针的地址。 assert(i == &head) , assert(*i == nullptr) assert(head == nullptr当列表不为空的时候，*i 指向前一个元素的 next 的地址。 assert(i == &previous_element.next) ，也就是说， *i 是当前元素的地址， (*i)-&value 是当前元素的值。移动到下一个元素的时候，i = &((*i)-&next_ ，保证 i 一直指向前一个元素的 next 地址。当列表不空的时候，*i = (*i)-&next_ ，就是说，修改前一个元素的 next 值，让他指向当前元素的下一个元素，(*i)-&next ，这样就把当前元素给跳过去了。完成了删除的操作。当列表为空的时候，循环立即结束。#include &iostream& \n#include &memory& \n#include &vector& \nusing namespace std;\n\nclass List {\n
List() : head_(nullptr), tail_(&head_){};\n\n
template &typename Iter&\n
List(Iter begin, Iter end) : head_(), tail_(&head_) {\n
for (auto it = begin; it != end; ++it) {\n
push_back(*it);\n
List(const std::initializer_list&int&& c) : List(c.begin(), c.end()) {}\n\n
template &typename Container&\n
List(const Container& c) : List(c.begin(), c.end()) {}\n\n
void push_front(int value) {\n
head_ = make_unique&Cons&(value, std::move(head_));\n
void push_back(int value) {\n
(*tail_) = make_unique&Cons&(value, nullptr);\n
tail_ = &(*tail_)-&next_;\n
void remove(int value) {\n
for (auto i = &head_; *i; i = &((*i)-&next_)) {\n
if ((*i)-&value_ == value) {\n
(*i) = std::move((*i)-&next_);\n
bool empty() { return head_ == nullptr; }\n\n
private:\n
struct Cons {\n
Cons(int value, unique_ptr&Cons&&& next)\n
: value_(value), next_(std::move(next)) {}\n
int value_;\n
unique_ptr&Cons& next_;\n
unique_ptr&Cons& head_;\n
unique_ptr&Cons& * tail_;\n
friend ostream& operator&&(ostream& out, const List& lst);\n};\n\nostream& operator&&(ostream& out, const List& lst) {\n
out && \"(\";\n
for (auto i = lst.head_.get(); i; i = i-&next_.get()) {\n
out && \" \" && i-&value_;\n
out && \")\";\n
return out;\n}\n\nint main(int argc, char* argv[]) {\n
auto lst1 = List{1, 2, 3};\n
lst1.remove(1);\n
cout && lst1 && endl;\n\n
auto lst2 = List{1, 2, 3};\n
lst2.remove(3);\n
cout && lst2 && endl;\n\n
return 0;\n}\n输出结果( 2 3)\n( 1 2)","state":"published","sourceUrl":"","pageCommentsCount":0,"canComment":false,"snapshotUrl":"","slug":,"publishedTime":"T18:08:47+08:00","url":"/p/","title":"用c/c++ 编写一个 list 操作程序","summary":" 20:21:24介绍本文试图通过迭代编程，一点一点改进一个关于 list 操作的程序。基本结构struct List {\\n struct List *\n};这是一个单链表结构。#include &iostream& \\n\nstruc…","reviewingCommentsCount":0,"meta":{"previous":null,"next":null},"commentPermission":"anyone","commentsCount":0,"likesCount":0},"next":null},"annotationDetail":null,"commentsCount":0,"likesCount":0,"FULLINFO":true}},"User":{"charles-wang-42":{"isFollowed":false,"name":"wcy123","headline":"你好","avatarUrl":"/54f291a568dc765e215ebe4eb86c705b_s.jpg","isFollowing":false,"type":"people","slug":"charles-wang-42","bio":"个人主页被 58 人浏览","hash":"6bceabf72fd07bbe09e009b","uid":16,"isOrg":false,"description":"你好","profileUrl":"/people/charles-wang-42","avatar":{"id":"54f291a568dc765e215ebe4eb86c705b","template":"/{id}_{size}.jpg"},"isOrgWhiteList":false,"badge":{"identity":null,"bestAnswerer":null}}},"Comment":{},"favlists":{}},"me":{},"global":{},"columns":{"wcy123":{"following":false,"canManage":false,"href":"/api/columns/wcy123","name":"wcy123 专栏","creator":{"slug":"charles-wang-42"},"url":"/wcy123","slug":"wcy123","avatar":{"id":"e0c158e6ab9b0437ccfa5910050ffb9f","template":"/{id}_{size}.jpg"}}},"columnPosts":{},"postComments":{},"postReviewComments":{"comments":[],"newComments":[],"hasMore":true},"favlistsByUser":{},"favlistRelations":{},"promotions":{},"switches":{"couldAddVideo":false},"draft":{"titleImage":"","titleImageSize":{},"isTitleImageFullScreen":false,"canTitleImageFullScreen":false,"title":"","titleImageUploading":false,"error":"","content":"","draftLoading":false,"globalLoading":false,"pendingVideo":{"resource":null,"error":null}},"config":{"userNotBindPhoneTipString":{}},"recommendPosts":{"articleRecommendations":[],"columnRecommendations":[]},"env":{"isAppView":false,"appViewConfig":{"content_padding_top":128,"content_padding_bottom":56,"content_padding_left":16,"content_padding_right":16,"title_font_size":22,"body_font_size":16,"is_dark_theme":false,"can_auto_load_image":true,"app_info":"OS=iOS"},"isApp":false},"sys":{}}&>&&>&&>&&>&统计整数的二进制表示形式中有几个1（java实现）
统计整数的二进制表示形式中有几个1（java实现）
上传大小：1KB
统计整数的二进制表示形式中有几个1（java实现），代码中有三种方法，分别是利用除、余的方法，位运算，以及利用“与”运算的方法。其中第三种方法效率最高，二进制数中有几个1，算法中的循环内的运算就执行几次。
综合评分：0（0位用户评分）
所需积分：1
下载次数：2
审核通过送C币
创建者：cpongo1
创建者：f_feng3
创建者：f_feng3
课程推荐相关知识库
上传者其他资源上传者专辑
开发技术热门标签
VIP会员动态
spring mvc+mybatis+mysql+maven+bootstrap 整合实现增删查改简单实例.zip
CSDN&vip年卡&4000万程序员的必选
统计整数的二进制表示形式中有几个1（java实现）
会员到期时间：剩余下载次数：
积分不足！
资源所需积分
当前拥有积分
您可以选择
程序员的必选
绿色安全资源
资源所需积分
当前拥有积分
VIP年卡全年1200次免积分下载
你当前的下载分为234。
统计整数的二进制表示形式中有几个1（java实现）
会员到期时间：
剩余下载次数：
你还不是VIP会员
开通VIP会员权限，免积分下载
你下载资源过于频繁，请输入验证码
你下载资源过于频繁，请输入验证码
您因违反CSDN下载频道规则而被锁定帐户，如有疑问，请联络:!
若举报审核通过，可奖励20下载分
被举报人：
举报的资源分：
请选择类型
资源无法下载
资源无法使用
标题与实际内容不符
含有危害国家安全内容
含有反动色情等内容
含广告内容
版权问题，侵犯个人或公司的版权
*详细原因：面试笔试题（3）
算法/数据结构~（34）
题目：输入一个整数，求该整数的二进制表达中有多少个1。例如输入10，由于其二进制表示为1010，有两个1，因此输出2。
分析：这是一道很基本的考查位运算的面试题。包括微软在内的很多公司都曾采用过这道题。
一个很基本的想法是，我们先判断整数的最右边一位是不是1。接着把整数右移一位，原来处于右边第二位的数字现在被移到第一位了，再判断是不是1。这样每次移动一位，直到这个整数变成0为止。现在的问题变成怎样判断一个整数的最右边一位是不是1了。很简单，如果它和整数1作与运算。由于1除了最右边一位以外，其他所有位都为0。因此如果与运算的结果为1，表示整数的最右边一位是1，否则是0。
得到的代码如下：
///////////////////////////////////////////////////////////////////////
// Get how many 1s in an integer's binary expression
///////////////////////////////////////////////////////////////////////
int&NumberOf1_Solution1(int&i)
&&&&&&int&count = 0;
&&&&&&while(i)
&&&&&&&&&&&&if(i & 1)
&&&&&&&&&&&&&&&&&&count ++;
&&&&&&&&&&&&i = i && 1;
&&&&&&return&
可能有读者会问，整数右移一位在数学上是和除以2是等价的。那可不可以把上面的代码中的右移运算符换成除以2呢？答案是最好不要换成除法。因为除法的效率比移位运算要低的多，在实际编程中如果可以应尽可能地用移位运算符代替乘除法。
这个思路当输入i是正数时没有问题，但当输入的i是一个负数时，不但不能得到正确的1的个数，还将导致死循环。以负数0x为例，右移一位的时候，并不是简单地把最高位的1移到第二位变成0x，而是0xC0000000。这是因为移位前是个负数，仍然要保证移位后是个负数，因此移位后的最高位会设为1。如果一直做右移运算，最终这个数字就会变成0xFFFFFFFF而陷入死循环。
为了避免死循环，我们可以不右移输入的数字i。首先i和1做与运算，判断i的最低位是不是为1。接着把1左移一位得到2，再和i做与运算，就能判断i的次高位是不是1……这样反复左移，每次都能判断i的其中一位是不是1。基于此，我们得到如下代码：
///////////////////////////////////////////////////////////////////////
// Get how many 1s in an integer's binary expression
///////////////////////////////////////////////////////////////////////
int&NumberOf1_Solution2(int&i)
&&&&&&int&count = 0;
&&&&&&unsigned&int&flag = 1;
&&&&&&while(flag)
&&&&&&&&&&&&if(i & flag)
&&&&&&&&&&&&&&&&&&count ++;
&&&&&&&&&&&&flag = flag && 1;
&&&&&&return&
另外一种思路是如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减去1，那么原来处在整数最右边的1就会变成0，原来在1后面的所有的0都会变成1。其余的所有位将不受到影响。举个例子：一个二进制数1100，从右边数起的第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成1，而前面的1保持不变，因此得到结果是1011。
我们发现减1的结果是把从最右边一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。如00。也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0。那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。
这种思路对应的代码如下：
///////////////////////////////////////////////////////////////////////
// Get how many 1s in an integer's binary expression
///////////////////////////////////////////////////////////////////////
int&NumberOf1_Solution3(int&i)
&&&&&&int&count = 0;
&&&&&&while&(i)
&&&&&&&&&&&&++
&&&&&&&&&&&&i = (i - 1) &
&&&&&&return&
扩展：如何用一个语句判断一个整数是不是二的整数次幂？
PS：n&(n-1)==0;//二进制数只有一位位1，则该数是2的整数次幂.
简单查表，相对来说效率也不错。
int countBits(int value){&
&&&&&&int count=0;
&&&&&&int bits4[]={0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
&&&&&&while(value!=0){
&&&&&&&&&&&&count+=bits4[value&0xf];
&&&&&&value&&=4;
======================================================
这是一道《编程之美－微软技术面试心得》中的题目，问题描述如下：
对于一个字节(8bit)的变量,求其二进制表示中“1”的个数,要求算法的执行效率尽可能地高。
《编程之美》中给出了五种解法，但是实际上从 Wikipedia 上我们可以找到。
这道题的本质相当于求二进制数的 Hamming 权重，或者说是该二进制数与 0 的 Hamming 距离，这两个概念在信息论和编码理论中是相当有名的。在二进制的情况下，它们也经常被叫做 population count 或者 popcount 问题，比如 gcc 中就提供了一个内建函数：
int __builtin_popcount (unsigned int x)
输出整型数二进制中 1 的个数。但是 GCC 的 __builtin_popcount 的实现主要是基于查表法做的，跟编程之美中解法 5 是一样的。Wikipedia 上的解法是基于分治法来做的，构造非常巧妙，通过有限次简单地算术运算就能求得结果，特别适合那些受存储空间限制的算法中使用：
/* ===========================================================================
* Problem:&
*&& The fastest way to count how many 1s in a 32-bits integer.
* Algorithm:
*&& The problem equals to calculate the Hamming weight of a 32-bits integer,
*&& or the Hamming distance between a 32-bits integer and 0. In binary cases,
*&& it is also called the population count, or popcount.[1]
*&& The best solution known are based on adding counts in a tree pattern
*&& (divide and conquer). Due to space limit, here is an example for a
*&& 8-bits binary number A=]
* | Expression&&&&&&&&&&& | Binary&& | Decimal | Comment&&&&&&&&&&&&&&&&&&& |
* | A&&&&&&&&&&&&&&&&&&&& |
|&&&&&&&& | the original number&&&&&&& |
* | B = A & &&&&& |
| 1,0,1,0 | every other bit from A&&&& |
* | C = (A&&1) &
| 0,1,1,0 | remaining bits from A&&&&& |
* | D = B + C&&&&&&&&&&&& |
| 1,1,2,0 | # of 1s in each 2-bit of A |&
* | E = D & &&&&& |
| 1,0&&&& | every other count from D&& |
* | F = (D&&2) &
| 1,2&&&& | remaining counts from D&&& |
* | G = E + F&&&&&&&&&&&& |
| 2,2&&&& | # of 1s in each 4-bit of A |
* | H = G & &&&&& |
| 2&&&&&& | every other count from G&& |
* | I = (G&&4) &
| 2&&&&&& | remaining counts from G&&& |
* | J = H + I&&&&&&&&&&&& |
| 4&&&&&& | No. of 1s in A&&&&&&&&&&&& |
* Hence A have 4 1s.
* [1] http://en.wikipedia.org/wiki/Hamming_weight
* 这个算法的设计思想用的是二分法，两两一组相加，之后四个四个一组相加，接着八个八个，最后就得到各位之和了。
*&设原整数值为x，
*&第一步：把x的32个bit分成16组（第32bit和第31bit一组，第30bit和第29bit一组……以此类推），然后将每一组的两bit上的值（因为是二进制数，所以要么是0要么是1）相加并把结果还放在这两bit的位置上，这样，得到结果整数x1，x1的二进制（32bit）可以分为16组，每一组的数值就是原来整数x在那两bit上1的个数。
*&第二步：把第一步得到的结果x1的32bit，分成8组(第32、31、30、29bit一组，第28、27、26、25bit一组……以此类推)，然后每一组的四bit上的值相加并把结果还放在这四bit的位置上，这样，又得到结果整数x2，x2的二进制可以分为8组，每一组的数值就是原来整数x在那四bit上的1的个数。
*&这样一直分组计算下去，最终，把两个16bit上1的个数相加，得到原来整数x的32bit上1的个数。
===========================================================================
#include &stdio.h&
typedef&unsigned&int&UINT32;
const&UINT32 m1& =&0x;&&//
const&UINT32 m2& =&0x;&&//
const&UINT32 m4& =&0x0f0f0f0f;&&//
const&UINT32 m8& =&0x00ff00ff;&&//
const&UINT32 m16 =&0x0000ffff;&&//
const&UINT32 h01 =&0x;&&// the sum of 256 to the power of 0, 1, 2, 3
/* This is a naive implementation, shown for comparison, and to help in&
* understanding the better functions. It uses 20 arithmetic operations
* (shift, add, and). */
int&popcount_1(UINT32 x)
& x = (x & m1) + ((x &&&1) & m1);
& x = (x & m2) + ((x &&&2) & m2);
& x = (x & m4) + ((x &&&4) & m4);
& x = (x & m8) + ((x &&&8) & m8);
& x = (x & m16) + ((x &&&16) & m16);
&&return&x;
/* This uses fewer arithmetic operations than any other known implementation
* on machines with slow multiplication. It uses 15 arithmetic operations. */
int&popcount_2(UINT32 x)
& x -= (x &&&1) & m1;&&&&&&&&&&&&&//put count of each 2 bits into those 2 bits
& x = (x & m2) + ((x &&&2) & m2);&//put count of each 4 bits into those 4 bits&
& x = (x + (x &&&4)) & m4;&&&&&&&&//put count of each 8 bits into those 8 bits&
& x += x &&&8;&&&&&&&&&&&//put count of each 16 bits into their lowest 8 bits
& x += x &&&16;&&&&&&&&&&//put count of each 32 bits into their lowest 8 bits
&&return&x &&0x1f;
/* This uses fewer arithmetic operations than any other known implementation
* on machines with fast multiplication. It uses 12 arithmetic operations,&
* one of which is a multiply. */
int&popcount_3(UINT32 x)
& x -= (x &&&1) & m1;&&&&&&&&&&&&&//put count of each 2 bits into those 2 bits
& x = (x & m2) + ((x &&&2) & m2);&//put count of each 4 bits into those 4 bits&
& x = (x + (x &&&4)) & m4;&&&&&&&&//put count of each 8 bits into those 8 bits&
&&return&(x * h01) &&&24;&&// left 8 bits of x + (x&&8) + (x&&16) + (x&&24)
int&main()
&&int&i =&0x1ff12ee2;&
& printf(&i = %d = 0x%x/n&, i, i);
& printf(&popcount_1(%d) = %d/n&, i, popcount_1(i));
& printf(&popcount_2(%d) = %d/n&, i, popcount_2(i));
& printf(&popcount_3(%d) = %d/n&, i, popcount_3(i));
&&/* If compiled with other compiler than gcc, comment the line bellow. */
& printf(&GCC's& __builtin_popcount(%d) = %d/n&, i,& __builtin_popcount(i));
&&return&0;
以上内容来源于
===========================================================
HAKMEM算法：
int Count(unsigned x)
&&& n = (x && 1) & ;&&&&
&&& x = x -&&&
&&& n = (n && 1) & ;&&&
&&& x = x -&&&&
&&& x = (x + (x && 3)) & ;&&&
&&& x = modu(x, 63);&&
说明：首先是将二进制各位三个一组，求出每组中1的个数，然后相邻两组归并，得到六个一组的1的个数，最后很巧妙的用除63取余得到了结果。
因为2^6 = 64，也就是说 x_0 + x_1 * 64 + x_2 * 64 * 64 = x_0 + x_1 + x_2 (mod 63)，这里的等号表示同余。
这个程序只需要十条左右指令，而且不访存，速度很快。
本文来自CSDN博客：
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：346769次
积分：4532
积分：4532
排名：第6279名
原创：93篇
转载：164篇
评论：69条
(1)(1)(1)(2)(1)(1)(6)(1)(1)(1)(1)(1)(1)(3)(4)(8)(5)(2)(5)(6)(1)(7)(12)(9)(10)(3)(6)(2)(1)(4)(1)(5)(4)(6)(1)(3)(6)(21)(8)(2)(7)(5)(10)(10)(27)(15)(7)(3)(8)(3)