lowbit求二进制表示下所有是1的位

发布时间：2020-12-14 04:24:37 所属栏目：大数据来源：网络整理

导读：主要思想是，对于非负整数n，输出n最低位的1所在位，并不断把n赋值成n-(n-n)，直至n=0。为了提高效率，我们使用Hash代替取log，并且利用一个数学技巧：对于任意在[0,35]中的k，2^k%37互不相等，且恰好取遍整数1~36。 1 #include iostream 2 3 using namespa

主要思想是，对于非负整数n，输出n最低位的1所在位，并不断把n赋值成n-(n&-n)，直至n=0。

为了提高效率，我们使用Hash代替取log，并且利用一个数学技巧：对于任意在[0,35]中的k，2^k%37互不相等，且恰好取遍整数1~36。

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 int H[37];
 6 
 7 int main() {
 8     for (int i = 0; i < 36; ++i)
 9         H[(1ll << i) % 37] = i;
10     int n;
11     while (cin >> n) {
12         while (n > 0) {
13             cout << H[(n & -n) % 37] << ‘ ‘;
14             n -= n & -n;
15         }
16         cout << endl;
17     }
18     return 0;
19 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!